[RITSEC CTF 2018] [Cryptography] [Who drew on my program?] 350pts
I played this CTF with my team Imperium and managed to get the 9th place where more than 952 teams participated!
Challenge description: ‘I don’t remember what my IV was I used for encryption and then someone painted over my code :(. Hopefully somebody else wrote it down!’
In this challenge, we were given the following image:
Following the challenge’s description, our goal is to retrieve the hidden IV (Initialisation Vector).
The given python script performs an AES-CBC-128 encryption, how do we know that?
1- We can see that the key’s value is ‘9aF738g9AkI112**’, where ‘*’ means a redacted character, therefore, the key’s length is 16bytes (128bits)
2- The encrypt function creates an AES object with AES.MODE_CBC as the mode
Looking closely at the image, we can notice that the plaintext: The message is protected by AES! was encrypted by this script, and produced the following ciphertext: 9e**************************436a808e200a54806b0e94fb9633db9d67f0
Notice that the plaintext is 32chars long (32bytes), which means that the ciphertext is also 32bytes long, but why?
Let’s see how AES works in CBC mode first by viewing this nice little diagram from wikipedia:
In AES-CBC-128, the plaintext is divided into blocks where each block is 16bytes (If the plaintext’s length can’t be divided by 16, then it’s padded using a padding scheme like PKCS#7, it’s not a problem here as the plaintext’s length is 32bytes, and 32 mod 16 = 0)
Then, the first block is XORed with what we call the ‘Initialisation Vector’, the subject of this challenge, then the result is passed into the AES-128 encryption block, which produces the first block of our ciphertext.
For the second block of the plaintext, it is first XORed with the previous ciphertext block, then passed to the AES-128 encryption function resulting in the second block of our ciphertext.
What happens to the second block of the plaintext, happens to the next blocks, the first block is just a special case where there is no previous ciphertext block, so it’s XORed with the IV instead, and that’s what is the IV for!
Alright, this will be better explained with the example in the challenge:
P = ‘The message is protected by AES!’; Let’s convert it into bytes
P = ‘\x54\x68\x65\x20\x6d\x65\x73\x73\x61\x67\x65\x20\x69\x73\x20\x70\x72\x6f\x74\x65\x63\x74\x65\x64\x20\x62\x79\x20\x41\x45\x53\x21’; Now let’s divide it into blocks of 16bytes, we will obviously get 2 blocks
P0 = ‘\x54\x68\x65\x20\x6d\x65\x73\x73\x61\x67\x65\x20\x69\x73\x20\x70’
P1 = ‘\x72\x6f\x74\x65\x63\x74\x65\x64\x20\x62\x79\x20\x41\x45\x53\x21’
Let’s do the same thing to our ciphertext!
C0 = ‘\x9e**************************\x43\x6a’
C1 = ‘\x80\x8e\x20\x0a\x54\x80\x6b\x0e\x94\xfb\x96\x33\xdb\x9d\x67\xf0’
The key: K = ‘9aF738g9AkI112**’
and the IV which is unknown: IV = ‘****************’
We have the following formulas:
1- C0 = AES-128-encrypt(K, P0 XOR IV); Encryption of ‘P0 XOR IV’ under AES-128 using the key K
2 - C1 = AES-128-encrypt(K, P1 XOR C0); Encryption of ‘P1 XOR C0’ under AES-128 using the key K
Knowing that the AES algorithm is symmetric, let’s apply AES-128-decrypt to the first formula:
AES-128-decrypt(K,C0) = AES-128-decrypt(K,AES-128-encrypt(K, P0 XOR IV))
AES-128-decrypt(K,C0) = P0 XOR IV
Then using the XOR properties, we get:
IV = AES-128-decrypt(K,C0) XOR P0; So this is how we’ll be recovering IV!
Let’s do the same process to the second formula:
AES-128-decrypt(K,C1) = P1 XOR C0, and using XOR properties:
C0 = P1 XOR AES-128-decrypt(K,C1)
But we’ve got a little problem here:
We know the 1st byte, and the last 2bytes of C0 only
And the key is missing the 2 last bytes, what should we do? BRUTEFORCE!
The idea is to generate all the possibilities of the key, which aren’t too big (256² = 65536) and AES-128-decrypt C1 with that key, then XOR the result with P1, and see if the result matches what we know about C0.
Once the result matches C0, then we would have recovered not only the key, but also C0!
And now, it’s pretty straight forward, let’s go back to the 1st formula:
IV = AES-128-decrypt(K,C0) XOR P0; All what we have to do now is to decrypt the recovered C0 with the recovered key and XOR the result with P0, that is IV.
Here is the script that does the whole explained process:
After running the script, we finally capture the flag!
The flag is: RITSEC{b4dcbc#g}
I hope this writeup was informative, see you on the next one!
~ 0x000c0ded, CTF player at Imperium team
