Cryptopals challenge 8: Detect ECB mode encryption

This is my write up of the eighth Cryptopals challenge, using Python3 as my language of choice. The challenge:

Detect AES in ECB mode

In this file are a bunch of hex-encoded ciphertexts.

One of them has been encrypted with ECB.

Detect it.

Remember that the problem with ECB is that it is stateless and deterministic; the same 16 byte plaintext block will always produce the same 16 byte ciphertext.

Wikipedia provides the bulk of the background knowledge we need to understand how to solve this challenge:

The simplest of the encryption modes is the Electronic Codebook (ECB) mode (named after conventional physical codebooks). The message is divided into blocks, and each block is encrypted separately…

…The disadvantage of this method is a lack of diffusion. Because ECB encrypts identical plaintext blocks into identical ciphertext blocks, it does not hide data patterns well. In some senses, it doesn’t provide serious message confidentiality, and it is not recommended for use in cryptographic protocols at all.”

It then goes on to show this image, which is the standard image that is shown to demonstrate that ECB can reveal patterns:

With this knowledge, a solution can be found by: 1) reading/decoding the data from the file; 2) Group the data into 16 byte chunks and count any repeating chunks; 3) Select the ciphertext with the most repetitions.

Read/decode data from the file

>>> ciphertext = [bytes.fromhex(line.strip()) for line in open('8.txt')]

Group the data and count repeating chunks


>>> block_size = 16
>>> chunks = [ciphertext[i:i+block_size] for i in range(0, len(ciphertext), block_size)]

I’ve used code like this in previous challenges, but let me demonstrate it in an easier example, using a cipher that is easier on the eyes than the actual encrypted data, and using a block size of two. The idea is to traverse the entire string and break the string up into block size-sized chunks:


>>> example_cipher = '0123456789'
>>> size = 2
>>> for i in range(0, len(example_cipher), size):
...     example_cipher[i:i+size]
...
'01'
'23'
'45'
'67'
'89'

Hopefully that is easier to see. Now to count the patterns in the ciphertext.

>>> number_of_repetitions = len(chunks) - len(set(chunks))

The set() function will take my list of chunks and remove duplicate values, so I will take the length of that set() object and subtract it from the total number of chunks to determine the number of repeating chunks. Once again, here is a contrived example that may be easier to visualize:


>>> l = [1,1,1,1,2,2,3,4,5,6]
>>> len(l)
10
>>> set(l)
{1, 2, 3, 4, 5, 6}
>>> len(set(l))
6
>>> len(l) - len(set(l))
4

So in this example, I have four repetitions.

Putting it all together and selecting the ciphertext with the most repetitions

When I read the file I store the ciphertexts in a list. When I count the repetitions, I go through that list, cipher by cipher, sending the cipher to the function that identifies repeating blocks. That function returns the cipher and number of repetitions in a dictionary, which I then put into a list. Once all ciphers have been sent through the function, I sort the list by the dictionary key ‘repetitions’ that has largest number value:

most_repetitions = sorted(repetitions, key=lambda x: x['repetitions'], reverse=True)[0]

Here is what my solution looks like:

I also created a tool that uses this code, but also adds in options to specify data from a file and apply your choice of decoding to the encrypted data. The tool, detect_ecb_mode.py, is located on my GitHub.

Example usage to examine an encrypted file (8.txt), line by line, that has been hex encoded:


C:\crypto_tools>python3 detect_ecb_mode.py -f 8.txt -x -l
Ciphertext: b'\xd8\x80a\x97@\xa8\xa1\x9bx@'...
Repeating Blocks: 3
Line number: 133

Leave a Reply

Your email address will not be published. Required fields are marked *