id: 16
lang: en
date: 2012-11-24
title: ECB: you're doing it wrong
category: CTF, Security
licence0: This article is released under the *CC BY-SA* licence.
licence1: <a href="https://en.wikipedia.org/wiki/File:Tux_ecb.jpg">ECBed Tux</a> from <a href="http://www.isc.tamu.edu/~lewing/linux/">a creation</a> of Larry Ewing (lewing@isc.tamu.edu) and The Gimp.
licence2: The other images are released under the *CC BY-SA* licence.

*[AES]: Advanced encryption standard
*[ECB]: Electronic codebook
*[CTF]: Capture the flag
*[BMP]: Bitmap file format

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](/media/tux_ecb.jpg)

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](https://r.rogdham.net/15), I took
part in [PoliCTF][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:

 - 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][0_bmp]. 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.

[PoliCTF]: http://polictf.it/
[0_bmp]: /media/polictf_ecb_0.bmp


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](/media/polictf_ecb_frequencies.png)

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](/media/polictf_ecb_first_result.png)

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:

![Second result](/media/polictf_ecb_second_result.png)


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.