Blog

PicoCTF 2018 Writeup: Bit Flip Attack

31.01.2019

The problem:

Uh oh, the login page is more secure… I think. http://2018shell.picoctf.com:12004

This was admittedly quite a hard one to crack. It follows up from a previous challenge. You can log in with any username and password combination. It then shows you a python object holding user data:

Cookie: {'admin': 0, 'password': 'verysecurepass', 'username': 'user'}

The goal is obviously to change the admin value from 0 to 1. But unlike the previous challenge, in this one, the cookie has been encrypted, so we can’t just change the value.

Luckily, the challenge gives us the source code that does the encryption. However, the encryption secret_key is removed.

After some googleing, I found that the particular algorithm they use is vulnerable to something called a bit-flipping attack. This attack is possible when we know both the plain text and encrypted text.

The algorithm, AES CBC, which stands for Advanced Encryption Standard Cypther Block Chaining (what a mouthful), works as follows:

You split your data into blocks. In our example the block size is set to 16 bytes. Then generate a block of random numbers, called the initialization vector iv.

Then xor your first data block with the iv. Call the result X. On X, run the AES algorithm (how this works is not really relevant). This will get you the first block of data. All subsequent blocks are encrypted the same way, except instead of xoring with the iv, they xor with the previous block’s X. Then prepend all of your blocks with iv, and you have your message, with the following structure:

iv block1 block2 block3 ... block n

Decryption works analogously: Reverse AES on the block, then xor with the iv for the first block, or X for all others.

So where’s the problem? Well, you might notice that the iv is sent to the user. When decrypting, the first block is xored with the iv to obtain the data. But we (with our cookie) provide the iv. That means we can change the IV in such a way that xoring it with the first block gives us the data we want.

The following picture will explain why this only works for the first block:

Notice that the IV only changes data in the first block, whereas changing any bits in any other block will result in that part of the ciphertext being garbage, because changing a single byte will completely change the result of running AES.

So how do we know what we have to change the IV to? We know our initialization vector is 16 bytes, meaning we can control the first 16 bytes of our string. We want to change:

{'admin': 0, 'pa

to:

{'admin': 1, 'pa

So let’s xor them to see which bits are different. To do so, let’s write some python code:

def xor(a, b):
    out = []
    for i in range(0, len(a)):
        out.append(ord(a[i]) ^ ord(b[i]))
    return out

Then:

> act_string = "{'admin': 0, 'pa"
> des_string = "{'admin': 1, 'pa"
> " ".join([ hex(x) for x in xor(act_string, des_string)])
0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x1 0x0 0x0 0x0 0x0 0x0

From this, we can see that we need to change the first bit of the 11th byte. That is equivalent to xoring the 11th byte with 0x1.

This should do the trick:

from base64 import b64decode
from base64 import b64encode
cookie = your_cookie
dec = b64decode(cookie)
dec = dec[:10] + (dec[10] ^ 1).to_bytes(1, byteorder='big') + dec[11:]
patched_cookie = b64encode(dec)

Replace your_cookie with the cookie the website gave you. Remember that this is always different, as the IV it generates is random. You can find the cookie by opening the dev tools of any browser. In chrome it’s under the “application” tab.

This code decodes the base64 encoded cookie into it’s actual bytes, xors the first bit of the 11th byte, then puts it all back together. Take the result, and paste it into the cookie field of the website. Reload the page, and suddenly, you’re an admin!

By Hannes Hertach