2
$\begingroup$

I've been working on the Cryptopals Cryptography challenge problems, and I recently solved one where you recover a plaintext given a encryption oracle. The oracle produces a ciphertext in ECB mode AES.

You are given a base64 encoded piece of plaintext (encoded so that it isn't immediately human readable). The only thing you have control of is the plaintext you enter into the oracle. The key for AES is randomly generated each time, and you're not supposed to see it either.

More information on the problem here: Set 2, Challenge 12

What confuses me is that at the end of the problem a little box says

This is the first challenge we've given you whose solution will break real crypto. Lots of people know that when you encrypt something in ECB mode, you can see penguins through it. Not so many of them can decrypt the contents of those ciphertexts, and now you can. If our experience is any guideline, this attack will get you code execution in security tests about once a year.

How can this vulnerability be used in real life? To crack the plaintext, you need access to it, as well as an encryption oracle (which contains the key). Is it ever possible to have this much control over a system? And if you did, why couldn't you just directly print out the plaintext or key?

$\endgroup$
2
$\begingroup$

The vulnerability happens when:

  1. You send an INPUT to the server.
  2. The server appends secret to INPUT -> INPUT||secret
  3. The server encrypts it with a secret key -> encrypt(INPUT||secret, key)
  4. The server returns, or you get access in some way to the resulting cipher.

Let's assume the block size is 8. Steps;

  1. All you have to do to decrypt the first byte of "secret" is to send a block of 7 bytes (block size -1). Let's assume we send: AAAAAAA. We get a cipher back, this cipher is our "target".

  2. Next we try AAAAAAA with every other possible bytes: AAAAAAAA, AAAAAAAB, AAAAAAAC, ... Let's assume the cipher returned at STEP1 is the same as when we send AAAAAAAw. That means we know for sure the first byte of the secret is w. We discovered the first byte, yay!

  3. Send 6 bytes (block-size - 1 - known bytes) + w (the byte we discovered previously). Get cipher.

  4. Brute force the last byte until you know the second bytes... Repeat all steps until you discovered secret.

See? We never actually needed to know the key and yet we discovered secret.

A concrete scenario where this could happens:

Website creates a secret key for each user for the duration of their session, but wants to remain stateless so it saves the secret key in their cookie, encrypted. Except that the cookie also contains the username (which the user can control/modify). Now the encrypted cipher is username||secret_key, which is easily decryptable.

$\endgroup$
  • $\begingroup$ This explains the attack, but not how the vulnerability could be used in real life. What concrete scenario could be attacked this way? $\endgroup$ – Conrado Jan 10 at 17:58
  • 1
    $\begingroup$ I focused more on the part where OP thought we needed the secret key to do the attack, which we do not. The first part of the answer also list the requirements for the attack to be possible. As for a concrete scenario, I edited my post with an example. $\endgroup$ – MyUsername112358 Jan 10 at 18:21
  • $\begingroup$ @Conrado the codebook is so small, you dont even need to recover the key, after 255 attempts you know every plaintext/ciphertext pair, as long as you have an encryption oracle to use $\endgroup$ – Richie Frame Jan 11 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.