niteCTF 2021, Flip Me Over Writeup

We have the server source code and its network address. As usual, let’s examine the code:

So the server allows us to perform two operations: generate token and verify token. We can generate token only once per connection but we can verify it as many times as we want (we need to verify token just once anyway).

For token generation we send server arbitrary hex string and it performs the following actions:

1. Get 16 random bytes of IV.
2. Decode hex to bytes and check that it doesn’t contain gimmeflag.
3. Initialize AES-CBC with generated IV and KEY and encrypt received bytes.
4. XOR tag with ciphertext (as tag is initially contains only zeroes, after XOR operation it will be equal to ciphertext)
5. XOR tag with iv
6. XOR tag with entropy, where entropy is some random byte string.
7. Return tag + ciphertext

For verification we must send to server two hex strings: token and tag. And verification is the following:

1. Decode token and tag from hex to bytes.
2. XOR tag with token
3. XOR tag with entropy
4. Set iv to tag.
5. Initialize AES-CBC with iv and KEY, decrypt token and return result.

If verification process returns any string that contains gimmeflag server will print flag.

Let’s summarize:

1. We can generate token from arbitrary hex string
2. We can verify arbitrary token with arbitrary tag
3. Once verification process returns byte string that contains gimmeflag we get the flag
4. We cannot generate token from gimmeflag.

Solution

So we need to somehow forge token. There is no chance to determine the key (or maybe there is, but why bother?), so don’t even think about it. All we can do is somehow manipulate generated token or tag and that’s what we will do. Let’s remember CBC encryption mode scheme

Consider the decryption scheme. Note that in this challenge we know both plaintext (not just know, but can choose it) and ciphertext (also can choose it). So we know that, for example, first block of ciphertext XORed with whatever comes out of block cipher decryption for second block gives us second block of plaintext. Let’s write it down in math:

where D is block cipher decryption function (AES in our case). I assume that other notations are clear. Now observe that manipulating first ciphertext block we can get second plaintext block to be anything we want:

So, if we want second block to decrypt into some P2' we do:

Now the attack draws itself:

1. Generate token with arbitrary bytes
2. Change first block of token so that second plaintext block decrypts into gimmeflag.
3. Send edited token to server
4. Voila

This is a well known bit flipping attack against CBC. Exploit code is below. I use xor function from my own package ptCrypt. You can find analogue in popular libraries, such as PyCrypto (or implement it yourself).

Script run result: