Thumbnail: ctflearn

CTFlearn 289 - We want Nudes instead of Nukes

by on under writeups
7 minute read

Write-up on CTFlearn’s challenge 289 - We want Nudes instead of Nukes. Donald has got completely crazy… Challenge author: macmueller.


Challenge

Cryptography, 90 points

Donald has gone completely crazy. To prevent world chaos, you kidnapped him. Right before the kidnapping he tried to send one encrypted message to his wife Melania. Luckily you intercepted the message. Donald admits that he used AES-CBC encryption - a block cipher operating with a block length of 16 bytes. (here represented by 32 characters)The message was: {391e95a15847cfd95ecee8f7fe7efd66,8473dcb86bc12c6b6087619c00b6657e} The format contains first the Initialization vector(IV) and then the cipher text(c) separated by a colon all wrapped in curly braces. {IV,c} After torturing him by stealing his hairpiece, he tells you the plain text of the message is: FIRE_NUKES_MELA! As a passionate hacker you of course try to take advantage of this message. To get the flag alter the message that Melania will read: SEND_NUDES_MELA! Submit the flag in the format: flag{IV,c} The characters are hexlified, and one byte is represented by two characters; e.g. the string “84” represents the character “F” of the message and so on.

Solution

The main idea behind the solution is to alter the IV before the decryption happens, so it gives a different, altered result of our choice. (in this case: SEND_NUDES_MELA! instead of FIRE_NUKES_MELA!) Let’s dive further in and learn a bit more about AES.

AES-CBC

AES is an abbreviation for Advanced Encryption Standard. As the name suggests, it is a huge standard in encryption. It is even used by the USA’s federal government. I won’t go in many details about how it works, all we need to know to solve this challenge is a big overall view of this algorithm. We will be looking at decryption only because we can’t change the original ciphertext but we can change the result of the decryption by changing the Initial Vector (IV). Below is a schema I’ve found on Wikipedia representing AES-CBC decryption.

AES-CBC Decryption

As you can see, the ciphertext is getting decrypted progressively from multiple rounds of the AES algorithm and if the key passed was right, it will be returned as the original plaintext. But notice the role of the IV at the decryption: it performs an XOR operation on the last output of the algorithm, right before getting returned. This is the exact place where we can perform the attack.

The Attack

We both know the IV and the original plaintext, so if we reverse the XOR operation, we can find the state of the ciphertext right before it being finally decrypted with the IV. Why is that worth knowing? Let’s take a look at this operation’s properties.

The XOR Operation

XOR, short for the name exclusive or, is a binary bitwise operation that returns 1 only if the 2 inputs are different, as you can see in the truth table below.

XOR truth table

XOR is used by a lot of encryption techniques and even has a cipher who bears his name.

It has a lot of property we can use at our advantage. Let’s take look at how to create a forged IV that will result in the plaintext we want and use some of these properties along the way.

The operation we want to reverse is the very last XOR of the AES algorithm. This operation looks a bit like that:

Output ^ Initial Vector = Plaintext (Where Output is AES’ output right before the XOR)

The property to use there in order to reverse this operation is that XOR is self-inverse. Briefly, it means that anything XOred with itself yields 0.

A ^ A = 0

Accordingly, we can perform algebra by XORing both sides by the Initial Vector, giving the following result: Output = Plaintext ^ Initial Vector. Note that the order of the terms XORed doesn’t matter, because XOR is commutative.

We now have Output. The only thing left to do is to generate an IV that suits our needs (in that case, getting the plaintext “SEND_NUDES_MELA!” after the decryption).

Using the same algebra, we can get the equation to calculate an IV: Plaintext ^ Output = Initial Vector.

If Output is equal to Plaintext ^ Initial Vector and the Altered Initial Vector is equal to Altered Plaintext ^ Output, then the formula for a forged IV is: Altered Initial Vector = Altered Plaintext ^ (Plaintext ^ Initial Vector). Using XOR property to be self-inverse and associative (order of the operations between XOR doesn’t matter), this can be reduced to Altered Initial Vector = Altered Plaintext ^ Plaintext ^ Initial Vector.

Therefore, using the original plaintext, the plaintext desired and the Output variable found before, we can get a new IV that is going to decrypt precisely to the plaintext we want.

Exploit Script

Let’s write a short Python script that does exactly what I just explained. I like to use bytearrays to perform byte-wise operations on hexadecimal strings. First, let’s add our ciphertext and our initial vector to the program.

IV = bytearray.fromhex("391e95a15847cfd95ecee8f7fe7efd66")
CT = bytearray.fromhex("8473dcb86bc12c6b6087619c00b6657e")

Then, we need to add the hexadecimal version of both the plaintext and the altered one. This can be done pretty easily online. Add them to the program.

ORIGINAL_MESSAGE = bytearray.fromhex(
    "464952455f4e554b45535f4d454c4121")  # FIRE_NUKES_MELA!

ALTERED_MESSAGE = bytearray.fromhex(
    "53454e445f4e554445535f4d454c4121")  # SEND_NUDES_MELA!

To finish the variable declarations, we are going to create a variable that is going to hold the altered IV as following.

ALTERED_IV = bytearray()

As you can see, all of our hexadecimal components (both plaintexts, IV and ciphertext) are 32 characters long; hence they are hexadecimal strings of 16 bytes because 2 hexadecimal character represents 1 byte. Let’s loop over every byte using a simple loop that counts from 0 to 15.

for i in range(16):
    # CODE GOES HERE

Now, we need to perform the formula found before. This is how to implement it in code:

for i in range(16):
    ALTERED_IV.append(ALTERED_MESSAGE[i] ^ ORIGINAL_MESSAGE[i] ^ IV[i])

Finally, we need to spit out a flag in format {IV,Ciphertext}. We can do that easily using Python’s improved string formatting (more about it here).

print(f'THE FLAG IS: flag{{{ALTERED_IV.hex()},{CT.hex()}}}')

This is the final script:

IV = bytearray.fromhex("391e95a15847cfd95ecee8f7fe7efd66")
CT = bytearray.fromhex("8473dcb86bc12c6b6087619c00b6657e")

ORIGINAL_MESSAGE = bytearray.fromhex(
    "464952455f4e554b45535f4d454c4121")  # FIRE_NUKES_MELA!

ALTERED_MESSAGE = bytearray.fromhex(
    "53454e445f4e554445535f4d454c4121")  # SEND_NUDES_MELA!
    
ALTERED_IV = bytearray()

for i in range(16):
    ALTERED_IV.append(ALTERED_MESSAGE[i] ^ ORIGINAL_MESSAGE[i] ^ IV[i])

print(f'THE FLAG IS: flag{{{ALTERED_IV.hex()},{CT.hex()}}}')
comments powered by Disqus