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.
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:
I explain the idea behind each step in the rest of this article.
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:
AAis padded to
AAAis padded to
AAAAis padded to
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.
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.
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'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 . If I chose the string made up of three bytes , the padded text will be . This also means that the first block will be : I just managed to isolate one byte of the unknown string.
Thanks to this trick, I know the ciphertext produced by the first block , which is in my example. This knowledge will allow me to perform a brute force attack later on.
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 and get the encryption of the block as a result, which is in the example below:
I can iterate over all possibilities for the last byte to create a dictionnary (also called codebook):
Once I have the codebook I just have to look for the input that produces the ciphertext I acquired when I isolated the first byte of the unknown string:
In this example, my codebook tells me that the ciphertext comes from the plaintext , which means that .
I apply the same principle to decrypt each byte of the unknown string, one at a time. Once I know , I use the input so that the first plaintext block is . I have now isolated and I can create a codebook for this specific case. The code to decrypt one byte can be found here.
You liked this article ? Check out the other posts about the Cryptopals challenges!