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

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

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

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

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

- First I divide the ciphertext in blocks of 16 bytes:

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

Ciphertext block | Count |
---|---|

C1 | 2 |

C2 | 1 |

C3 | 3 |

... | ... |

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

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.

In a set of $n$ people, what is the probability $p(n)$ that two of them share the same birthday ? You'll find that if $n = 23$ we have $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 $E$ is the set of all possible blocks, $n$ the number of blocks then the equation is:

$p(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| = 2^{128}$ possible blocks. The equation above can be tricky to apply in the real world so we use an approximation:

$p(n) \approx 1 - e^{-\frac{n(n-1)}{2\cdot|E|}}$In our case $p(20) \approx 0$.

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

$n(p) \approx \sqrt{2 \cdot |E| \cdot ln\left(\frac{1}{1-p}\right)}$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.

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.

Check out my other articles about the Cryptopals challenges!

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