Rogdham

ECB: you're doing it wrong

Electronic codebook

Block ciphers (e.g. AES) are good ways to encrypt a block (e.g. 16 bytes) of data using a cipher that has been proved to been (somehow) secure.

The problem is that the messages we want to send encrypted are usually loger than 16 bytes. Hence, we want to turn a block cipher into a stream cipher.

To do that, different modes of operation exists. Among them, ECB is the easiest one: we see the message as consecutive blocks, and we just apply the block cipher to each block separately. However, this mode of operation is known not to be secure, since it is prone to frequency analysis.

Tux encrypted in ECB mode: we can still see that it is the Linux mascot

The image above was encrypted using the ECB mode. We have lost the details (including the colours used), but it is pretty clear that the original image was the Tux, the Linux mascot.

Well, that example was made up for the sake of argument, right? How would an attacker actually exploit a secure block cipher used in ECB mode?

Context

As you may know from my previous article, I took part in PoliCTF, which was a security CTF competition. The B1n 500 challenges consisted in getting the file from a binary program.

The part of the program we will be interesting in for the rest of the article works as follows:

  1. asks the user for a key
  2. decrypts some data with AES in ECB mode using that key
  3. stores the data in a file called 0.bmp

We don't know anything about the key to enter, but we will assume the following:

How would you get the token? If you want to give it a try, here is the BMP file you obtain when you give an empty key to the binary. Of course, this file is not a valid BMP image.

I did get the token during the CTF, but that token was only the first (out of 3) step of the B1n 500 challenge. Unfortunately we have not been able to go any further in due time, so you will not find a full write up here.

Exploit

The exploit starts with frequency analysis.

Since we know that AES is used, we can assume that the block size is 16 bytes. Hence, we split the file into blocks, and count the repartition of the different blocks.

Frequency analysis

As show in the graph above, one block uses 90% of the file space, the second most frequent 6.8%, and the others are below 1%.

The next idea is simple: turning the most frequent block into white pixels, the second most frequent block into black pixels, and we don't care about the colour of the remaining ones.

But now we have a problem: what is the size of the image? The trial and error method seems appropriate in that case. Try different width values, and get a usable image back!

First result

This is far from being perfect, for two reasons:

Since I was doing a CTF, I was in a hurry, so I just opened my favorite image editor, did a mirror transformation and read the token: Tro11d. Job done.

However, to to better, we could consider doing the following:

Which gives the following result:

Second result

Conclusion

ECB mode is not safe. We knew that, but it was pretty easy to actually see what the image looked like without having any clue about the key.

Of course, this worked well because BMP files are not compressed whatsoever. Compression is a way to increase the entropy of the data. But if the attacker has enough data, frequency analysis will still work. That being said, if you manage to increase the entropy in such a way that your data looks like random, you will be safe. Guess what? This is exactly what encryption is doing.

And there is no point in using a bad encryption scheme on top of a good one. Just use a better mode of operation.

This article is released under the CC BY-SA licence.

ECBed Tux from a creation of Larry Ewing (lewing@isc.tamu.edu) and The Gimp.

The other images are released under the CC BY-SA licence.

Short URL: http://r.rogdham.net/16.