Break Me!, DownUnder CTF 2021, Writeup

For this task we have the server source code and the server address. Let’s look inside the source code

Here we see pretty classic ECB Oracle: we can send arbitrary message for server to encrypt it with AES-ECB, server will encrypt it and return the result. But before encryption server adds some secret data to our message. We can find that data repeatedly sending specifically constructed messages. The wonderful part is that we do not need to know the key. We even don’t really care about the encryption algorithm — the vulnerability lays in the ECB mode itself. You can use perfectly secure block cipher (AES is not perfectly but still computationally secure nowadays), but as long as you have the encryption scheme as above — you have a problem. Before solving the challenge, let’s first see how an attack works.

ECB Oracle Attack

Prerequisites

For the ECB Oracle attack to apply there are two properties the system must have:

1. The attacker needs to be able to send arbitrary plain texts and see the encrypted ciphertexts.
2. Before encrypting the given message, server has to add secret data to the end of the message.

So the server encryption scheme must be

Where m is message sent by an attacker. Now let’s look at the ECB encryption scheme

What we see here is that all plaintext blocks are encrypted independently from one another and for a particular plaintext the ciphertext will always be the same. Let’s assume that the secret has length of one block for simplicity (attack still applies for smaller and bigger secrets). Attacker sends the message m of one block length. Let’s also assume that the block size is 16 bytes (again, block size is not important). Therefore we have two blocks to encrypt and two blocks of ciphertext.

So we can split the received ciphertext into two parts C1 and C2. C1 is the ciphertext of completely known for us message M. And C2 is completely unknown for us secret. And there is nothing we can do to decrypt at least one byte of the C2 knowing C1 (we would have to break the underlying AES encryption).

All right, but what if we (and that might look like a silly idea, but still) reduce our message by one byte? So instead of 16 bytes, we will send server only 15. The server will append the secret, split it into blocks and encrypt.

Note the change — we now have s0 in the first block along with our known message. Can we decrypt this single byte, knowing other 15? The answer is still no (that’s sad, I know). But what we can do, is we can remember the C1 and after that send 16 bytes to server again, but this time we change the last, 16th byte. And we do that iteratively, trying all possible bytes.

Eventually we will receive C1 that equals to the one we remembered after we sent 15 bytes. That would mean that our guess ti is equal to the first byte of the secret s0. Look at that! We have decrypted first byte of the secret!

All right, what we are going to do now? How do we decrypt the rest? Well, the same way we did this one. Now as we now s0 we can replace our m14 with it and send 15 bytes to the server again.

And now again we remember C1 and try all possible bytes instead of s1.

Again, eventually we will receive C1 that is equal to remembered C1 and that’s how we know that we found s2. I suppose you got the idea now. Repeating this actions over and over again we can decrypt the whole secret.

Note that it is not a bruteforce attack. If we wanted to perform bruteforce attack, we would just try encrypting all possible values of M until we find such value that C1 == C2. This would result in 256¹⁶ tries. What we do is we decrypt one byte at a time. So we will need 256 * 16 tries, which is significantly smaller than 256¹⁶.

Solving the challenge

Now we almost have all the challenge solution covered. Although we should notice that the concatenation scheme is a bit different than the one I presented above. Instead of adding secret to the end of the message making

We have message prefixed with the flag (the secret we want to know)

And our attack doesn’t work this way. But, there is one more concatenation, namely, before encrypting, message also concatenated with the encryption key. So now we have

This doesn’t change much — we still cannot find Secret, but we can find the key, applying ECB Oracle attack. And as long as we know the key we can easily decrypt any encrypted data without applying any attacks.

The attack script looks as follows:

Here you see key = b"!_SECRETSOURCE_!" — that’s already found key, originally this field should be empty. Also, that’s not quite the algorithm I described for the attack. First, I collect 16 ciphertexts, each corresponding to the case where we know some amount of bytes. First, I get the ciphertext with 15 known bytes, next with 14, 13 and so on down to 0. After that I use this pads again, but also I concatenate the found key. So, first I take 15 known bytes (I use zero bytes here), then I add known key (which is 0 bytes at the beginning) and I iterate over the last byte until I find the exact same ciphertext as I got in the beginning for 15 bytes pad. On the second iteration I get 14 bytes pad, plus found one byte of the key and again iterate over the last 16th byte. This small change doesn’t really make the difference to the attack, that’s just the way I did it.

And after we run the script we see key bytes appear one at a time.

Unfortunately, at some point (after about 1 minute) server closes the connection. That’s not a big deal, we can set the known key to the bytes we found and run it again, the script will catch up from the point it stopped. And after a few iterations we finally get the key and immediately after that we can decrypt the flag: