ECB: you're doing it wrong
- Traduction en français : ECB : La mauvaise façon de faire
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.
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:
- asks the user for a key
- decrypts some data with AES in ECB mode using that key
- 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:
- if we have entered the real key,
0.bmp
would be a valid BMP file - that valid image would be depicted the token we are looking for
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.
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!
This is far from being perfect, for two reasons:
- we forgot that the BMP format is listing the pixels from bottom to top and left to right, so the image has to be flipped over
- there is some shifting involved since we don't know the length of the header of the file (also, I removed a lot of blank pixels before and after this image)
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:
- assuming that the header is 54 bytes long, which would have removed the shifting problem
- using more than the first top two frequencies
Which gives the following 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.