Cryptopals - Byte-a-time ECB decryption (Simple)

The challenge 12 of the Cryptopals crypto challenges is the first one having you breaking real crypto. Some of the ideas behind this challenge are not that obvious so I thought it would make a good subject for a write-up.

Premises

The goal of the challenge is to decrypt a ciphertext encrypted with ECB. Obviously, I do not know the plaintext, but I am given an oracle to help me decrpyt the ciphertext. I call the plaintext unknown-string. Thanks to the oracle I can prepend a chosen string to the unknown string before performing the encryption:

Oracle(chosen-string) = AES-128-ECB(chosen-string || unknown-string)

To perform the attack, I am given some instructions:

1. First I need to determine the block size of the cipher. The indications disclose that it's 128, but I'm doing this challenge to learn, so I pretend I don't know the block size.
2. Secondly I need to detect that the oracles is using ECB. Again, I role play this part.
3. Finally I need to brute force each byte of the unknown string one by one.

I explain the idea behind each step in the rest of this article.

Determining the block size

I know that I am attacking a block cipher, which means that the plaintext chosen-string || unknown-string will be padded (I assume PKCS7 in the examples). And the length of the padded plaintext will be equal to the length of the ciphertext. So by studying the length of the ciphertext I can determine the length of the padded text.

To determine the block size I grow the size of chosen-string until the length of the padded text suddenly changes: this indicates that I reached the end of a block and started a new one. For instance, if one block is 4 bytes long:

• the input AA is padded to AA22
• the input AAA is padded to AAA1
• the input AAAA is padded to AAAA4444

In this example, I gradually increased the length of the input to monitor the length of the padded text. When I reached an input of size 4, the length of the padded text suddenly changed and increased by 4: this means that the block size is 4.

Of course, the challenge is slightly different since I work with unknown-string as well. Still, I can apply the same process.

I increase the size of the chosen string by one byte every iteration. Once the ciphertext length suddenly increases, I compute the number of bytes added: this is the block size.

Detecting ECB usage

The challenge 8 is dedicated to detecting ECB usage. You can find my article about this challenge here. In the rest of the article I consider I have a function DetectECB at my disposal.

Byte-at-a-time decryption

To keep the diagrams and the explanation simple I assume the cipher is using 4-byte blocks, when in reality it is using 16-byte blocks.

To be able to decrypt one byte of the unknown string, I have two abilities at my disposal:

• I can craft special blocks containing only one byte of the unknown string
• I can create a dictionnary to perform a brute force attack

Byte isolation

I'll start with the first step: crafting special blocks. I know that the blocks are 4 bytes long, which means that an input of 7 bytes will produce a padded plaintext of 8 bytes.

To keep the example simple, I'll assume that the unknown string is made up of four bytes $[s_1, s_2, s_3, s_4]$. If I chose the string made up of three bytes $[A, A, A]$, the padded text will be $[A, A, A, s_1, s_2, s_3, s_4, 1]$. This also means that the first block will be $[A, A, A, s_1]$: I just managed to isolate one byte of the unknown string.

Thanks to this trick, I know the ciphertext produced by the first block $[A, A, A, s_1]$, which is $[x_1, x_2, x_3, x_4]$ in my example. This knowledge will allow me to perform a brute force attack later on.

Dictionnary creation

Thanks to the oracle function I can perform a chosen plaintext attack. Since I know the length of one block, I can prepend the unknown string by one block composed of $[A,A,A,A]$ and get the encryption of the block $[A,A,A,A]$ as a result, which is $[u_1,u_2,u_3,u_4]$ in the example below:

I can iterate over all possibilities for the last byte to create a dictionnary (also called codebook):

Brute force

Once I have the codebook I just have to look for the input that produces the ciphertext $[x_1, x_2, x_3, x_4]$ I acquired when I isolated the first byte $s_1$ of the unknown string:

In this example, my codebook tells me that the ciphertext $[x_1, x_2, x_3, x_4]$ comes from the plaintext $[A, A, A, 8]$, which means that $s_1 = 8$.

Decrypting the entire string

I apply the same principle to decrypt each byte of the unknown string, one at a time. Once I know $s_1$, I use the input $[A, A]$ so that the first plaintext block is $[A, A, s_1, s_2]$. I have now isolated $s_2$ and I can create a codebook for this specific case. The code to decrypt one byte can be found here.