Cryptopals - Detect AES in ECB mode

14 August 2020

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.

This article is high level, to find the code take a look at my repository

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
P=[P1,P2,...,PN]P = [P1, P2, ..., PN]
  1. Step 2: each plaintext block is encrypted to produce the ciphertext blocks :
C1=Ek(P1),C2=Ek(P2),...C1 = E_k(P1), \quad C2 = E_k(P2), ...

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" :

intelligence is good reasoning, intelligence is shaped gradually\text{intelligence is good reasoning, intelligence is shaped gradually}

The two identical plaintext blocks P1P1 produce two identical ciphertext blocks C1C1:

Padding

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:
C=[C1,C2,C3,...,CN]C = [C1, C2, C3, ..., CN]
  1. Then I count the number of times each block is repeated (with a hashmap):
Ciphertext blockCount
C12
C21
C33
......

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)p(n) that two blocks collide according to the number of blocks nn in the plaintext ?
  • What is the number of blocks nn necessary to have p(n)0.5p(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.

🥳 Birthday paradox

In a set of nn people, what is the probability p(n)p(n) that two of them share the same birthday ? You'll find that if n=23n = 23 we have p(n)=50.7%p(n) = 50.7\%.


This means that with only 23 random people and 365 birthdays, there is more than 50% chance that at least two of them share the same birthday! This counter-intuitive result gave the problem its designation of "paradox".

If EE is the set of all possible blocks, nn the number of blocks then the equation is:

p(n)=1E!(En)!1Enp(n) = 1 - \frac{|E|!}{(|E| - n)!}\cdot\frac{1}{|E|^n}

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

p(n)1en(n1)2Ep(n) \approx 1 - e^{-\frac{n(n-1)}{2\cdot|E|}}

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

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

n(p)2Eln(11p)n(p) \approx \sqrt{2 \cdot |E| \cdot ln\left(\frac{1}{1-p}\right)}

We have n(0.5)2ln(2)2641.39264n(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 2642^{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 2642^{64} blocks, this should work properly.

Check out my other articles about the Cryptopals challenges!

Resources

I used and studied the following resources while writing this post: