Cryptopals - Detect AES in ECB mode

In the eleventh challenge of the Cryptopals crypto challenges, a file containing hex-encoded ciphertexts is given:

8a10247f90d0a05538888ad6205882196f5f6d05c21ec8[...]
bd20aad820c9e387ea57408566e5844c1e470e9d6fbbdb[...]
ed9eccbe79394ca0575a81d1fa51443aa3e83e5e3cdb7a[...]
...

One of these ciphertexts was encrypted with AES-ECB, the goal is to find which one.

AES-ECB

ECB (Electronic Codebook) is the most basic mode of AES. It can be explained in two steps:

1. Step 1: the plaintext is divided in blocks of 16 bytes

2. Step 2: each plaintext block is encrypted to produce the ciphertext blocks :

The problem with ECB mode is that two identical plaintext blocks will produce the same ciphertext blocks. The following string will have 4 plaintext blocks, two of which will be equal to "intelligence is" :

The two identical plaintext blocks $P1$ produce two identical ciphertext blocks $C1$:

AES-ECB detection

This specificity can help identify if a ciphertext was encrypted with AES-ECB.

1. First I divide the ciphertext in blocks of 16 bytes:

2. Then I count the number of times each block is repeated (with a hashmap):

If more than one block is repeated, I can consider that the oracle is using AES-ECB (and this strategy works for the challenge).

Collision probability

In the challenge the ciphertext is composed of 321 bytes, which corresponds to 20 blocks. If the ciphertext is longer shouldn't there be some natural occurence of ciphertext block repetition ? This leads to two important questions:

• What is the probability $p(n)$ that two blocks collide according to the number of blocks $n$ in the plaintext ?
• What is the number of blocks $n$ necessary to have $p(n) \ge 0.5$ ?

The questions I am aksing myself are directly related to the birthday paradox. I can use the equations solving this problem to solve mine.

If $E$ is the set of all possible blocks, $n$ the number of blocks then the equation is:

Note that a block is made up of 128 bits so there are $|E| = 2^{128}$ possible blocks. The equation above can be tricky to apply in the real world so we use an approximation:

In our case $p(20) \approx 0$.

There is also an equation to compute the number of elements required to get a certain probability:

We have $n(0.5) \approx \sqrt{2 \cdot ln(2)} \cdot 2^{64} \approx 1.39 \cdot 2^{64}$. This means that when our ciphertext is composed of approximately $2^{64}$ blocks, we have a 50% chance of having a collision.

Conclusion

To detect if AES-ECB was used, check if two blocks in the ciphertextext collide. As long as the ciphertext contains less than $2^{64}$ blocks, this should work properly.

Resources