Help me understand this ECB attack

[king_mob]

It's pretty old i guess now (2012) but i'd still like to able to understand the adaptive chosen plaintext attack on AES-ECB. Specifically, how it's explained in this video from Thomas Ptacek's talk on crypto: https://vimeo.com/41116595

I can understand how we identify where our block boundaries are, but repeatedly injecting known plaintext (32 or 64 A's for example) and then appending another known string, but this time with a different value (another letter in the alphabet). From this, build up a dictionary of ciphertext that we know the plaintext for.

My problem is i cant understand how the attack gets implemented practically, for example in the video it's suggested to include a pipe character | (thats @ 45 minutes in or so) but i cant see how this would lead to a decryption?

[todd8]

In ECB mode, a block cipher (like AES) is used to encipher/decipher each block (of say 128 bits) with the cipher key independently of all other blocks. This means that two equal ciphertext blocks, say block 23 and block 61, have equal corresponding plaintext blocks so we can surmise that plaintext blocks 23 and 61 are identical. This weakness precludes using simple ECB mode in most cryptographic situations. It is too easy to exploit this property of ECB mode with replay or reordering attacks because the encrypted blocks can be rearranged and still remain valid.

The talk that you reference implys that is it possible to progressively decrypt ECB encoded data by progressively decrypting one byte at a time. I don't see how this makes any sense in the way suggested in that video, and I am guessing that this is why you are wondering how this type of attack would be applied in practice. First note that changing even one bit of the plaintext block will on average change half of the bits in the resulting ciphertext when using a strong block cipher like AES. Mr. Ptacek suggests using a chosen plaintext attack to build up a dictionary of ciphertext to plaintext such as

   Plaintext           Ciphertext (in hexidecimal)
   ----------------    --------------------------------
   AAAAAAAAAAAAAAAA    219d992d9f5ae84d29ffd4dfbeaf1f7f
   AAAAAAAAAAAAAAAB    a20400dbb98b6da0ac0178d71204460d
   AAAAAAAAAAAAAAAC    cd20f8731ccf8e6643b287aadaf84f26
   ...                 ...

Now, whenever we see a block containing cd20f8731ccf8e6643b287aadaf84f26 we know that it's plaintext translation is AAAAAAAAAAAAAAAC. But this doesn't help us. Changing only the last character or even bit of the plaintext is no different than changing the first of 12th bit, the result is a new completely cryptographically random result in the ciphertext. We can't progressivly attack the plaintext one character at a time as suggested by the video.

We can continue to fill in the dictionary by just submitting chosen plaintext to the system and recording the results. The problem with this approach is that to be useful this dictionary will contain many many entries and will change completely for each different key. For arbitrary plaintext, the dictionary will contain 2^64 entries or worse 2^128 or 2^256 entries depending on the block size of the underlying cipher.

All of this doesn't mean that ECB mode is safe against attacks, just that the attack as described by the video using pipe characters, etc. doesn't make sense. However, there are times where we can brute force ECB mode with a chosen plaintext attack. For example, if we already know that a block of important plaintext starts with the eleven characters "Password = " this leaves only 5 bytes in the block to be guessed. Now we can run through all 5 character values and use this. It may only reveal the first five characters of a password in this case, but that is an important vulnerability.

I believe that the section of this video to which you refer is confusing because Mr. Ptacek is attempting to present a simple introduction to an important cryptographic attack against another mode of using block ciphers. This attack is known as the padding oracle attack. The CBC mode (cipher block chaining) eliminates the weaknesses I've described above for ECB mode, but it has an important vulnerability of its own which makes use of a padding error oracle. I won't attempt to describe it here, it requires quite a bit of explanation, but by using this attack, a system that returns detectable errors when there is a block padding error, can be attacked and almost an entire message can be decrypted one byte at a time as Mr. Ptacek suggests. It's just all more complex and applies only to the CBC mode not the ECB mode.

Unfortunately, on the web, there is a lot of hard to understand information on such cryptographic attacks. I find many blog posts are by those describing systems that they don't fully understand and papers written by researchers that do understand the attack but make heavy use of mathematical notation and describe the attacks in their full generality. There are few resources with easy to understand diagrams and clear descriptions. For this particular padding attack on ECB mode I suggest: http://robertheaton.com/2013/07/29/padding-oracle-attack/

[king_mob → todd8]

Thanks a lot for the response, you've given me a lot to go and research.