9

Reading up on attacks against AES i have seen countless examples of why ECB is bad, and the logic behind it i can understand, but i can't get my head around how these attacks actually work in the real world.

So the big example that i see getting used a lot is a session token that is encrypted with AES-ECB, and as its a session token (cookie for example) we can repeatedly inject chosen plaintext and monitor the changes in ciphertext, assuming the session token is always encrypted under the same key. But how from that do we infer the correct plaintext?

For example, say i inject 64 A's as my username, and in the hex dump of the cookie that gets returned i can see the tell-tale repeating 16 byte blocks that indicate pretty conclusively the encryption is AES-ECB. I can change the last 16 A's to instead be 15 A's a B, so i know now not only what the ciphertext for 16 A's looks like, but also what the ciphertext for all A's and a B looks like.

But after that i get stuck and i can't see how this attack expands out to become practical. So far all i can see is we know what the last byte looks like, and a bunch of A's.

Good explanations i've seen so far have been: https://vimeo.com/41116595 although he loses me around the 42 minute mark, and http://www.slideshare.net/ceng/cryptography-for-penetration-testers-pdf-version-presentation

EDIT: After thinking about the problem, i think a better way of phrasing this question would be - assuming the block we control is an arbitrary length into the ciphertext, and the total ciphertext is an arbitary length, how do you calculate the length of the prefix (the number of A's) to inject so you can decipher each successive byte?

EDIT: The above edit which forms an addition to the question, "how do we calculate the length of the prefix" is actually inaccurate. I've found its trivial to calculate the prefix length of the ciphertext that we do not control, and the ECB attack as i have seen it explained is designed to decipher text the comes explicitly after the ciphertext of the the chosen plaintext.

AlexH
  • 371
  • 3
  • 9
  • Does this help? http://crypto.stackexchange.com/questions/12510/ecb-weakness-and-its-exploitation – paj28 Jun 29 '14 at 17:51
  • Thank you, although i had read that Q recently before posting and in fact it was one of the reasons i decided to ask a similar question here. Thank you for the comment though as it as helped me spot how i can improve my question. – AlexH Jun 29 '14 at 18:00

1 Answers1

12

Sounds like you're well on your way to figuring this out. I've never exploited ECB chosen plaintext, but I recently did a padding oracle exploit, so I've got some idea how you would do this.

The basic idea is to brute force one byte at a time.

Just suppose we have a simple example where there is no other data inserted so it's just "[username][secret]". First, set your username to 16 A's. Then you change the last character to a B. In fact, go through all the 256 possible values for the final byte, and keep a record of the cipher texts.

Now set your username to 15 A's. The plaintext block will consist of your 15 A's, and one byte from the secret. The ciphertext will match one of the ciphertexts you previously generated, and from that you can deduce one byte of the secret.

Now set your username to a 16-character value: 14 A's, the one byte of plaintext you know, and cycle through the 256 possible values for the final byte. Record all the ciphertexts. Next step is to set your username to a 14 A's, and nothing else. From the generated ciphertext you can deduce the second byte of the secret.

Carry on and pretty soon you have the full secret!

In a practical scenario there are likely to be other things that make exploitation harder, but this is the basic idea.

paj28
  • 32,736
  • 8
  • 92
  • 130
  • Thanks a lot, that answer was a big light bulb moment for me, I think i'm starting to get it. One last question though, when you say to include the one byte you know, do you mean the plaintext byte? As i would of though that as the whole block is XOR'd, plaintext A under the key wont always result in the same ciphertext output? I.e plaintext A will be 0x3f in one block, but could be 0xd9 in the next. I mean, otherwise frequency analysis could defeat the encryption given the same key. – AlexH Jun 29 '14 at 19:31
  • @AlexH - glad I could help. Yes, I do mean the plaintext byte. With ECB the same plaintext block and key does result in the same ciphertext block. That is the main weakness of ECB, and that is why more complex schemes like CBC exist. A change to an individual byte does change the whole ciphertext block, but in this attack attack works around that problem. – paj28 Jun 29 '14 at 22:07
  • paj28, thanks again, i keep re-reading your answer and it makes more and more sense each time. – AlexH Jun 30 '14 at 10:01