Cryptography - Byte by Byte ECB Decryption

In this post we’ll cover how to attack an oracle function that encrypts user supplied data concatenated with an unknown string under ECB mode while using a constant but unknown key.

This post will assume you know what PKCS#7 padding is. If you’re unsure what this is, you can read my short post about it here.

This post is also a solution to challenge 12 on the cryptopals website. This site is a great resource for hands on learning about cryptography. The technique used to complete this challenge is outlined on that page. This post will explain the same technique with a bit more detail and visual examples.

1. What are we Breaking
2. Attack Summary
   • Step 1 - Determining the Block Size
   • Step 2 - Unknown String Size
   • Step 3 - Determining the Unknown String
   • Step 4 - Determining the Unknown String Continued

What are we Breaking

For a more concrete example of what we are breaking, imagine the oracle function is a web server API such as:

• POST /encrypt This API would take a single parameter which is the message we want to encrypt, and would return the cipher-text. Because the key used by the server remains constant, sending the same message results in the same response.

Example Request

This is my message I want encrypted

Example Response (HEX)

3b600a3994308f1d53879432125635deb10485748eefc86905180ff82f9a73c235b09a4c89e30328094effe8d2282edb9e2d3ccf364ba758e1395f1fcebbedc1

Behind the scenes the server is doing the following:

1. Concatenating the user supplied string with an unknown constant string (like a salt), and encrypting it with a unknown constant key.
   • AES-ECB(user-string || unknown-constant-string, unknown-constant-key)
2. The resulting encrypted data is sent back to the user.

My claim is that we can determine exactly what unknown-constant-string is by repeated calls to this oracle function without ever knowing the encryption key!

Attack Summary

Step 1 - Determining the Block Size

The first piece of information we require is the block size, since encryption modes like ECB and CBC encrypt blocks of a fixed length. The cryptopals challenge uses AES, so we already know the block size is 16 bytes, but we’ll assume we don’t know that. The below visual examples will use a block size of 8 bytes, since it fits on the screen better. The technique is exactly the same for all block sizes.

Working out the block size is very simple, we just need to do the following:

1. Create a message 1 byte in length.
2. Send the message to the oracle function, and store the cipher-text length.
3. Increase the message size by 1 byte, and send the message to the oracle function.
4. Repeat the previous step until the length of the cipher-text changes.
5. The block size will be the final size minus the original size.

Example Setup:

• The server is using a unknown string that is 13 bytes long (marked as XX since we don’t know what it is).
• We’ll use the byte 0x41 as our message, which is actually the letter A. This is arbitrary, and you can use any byte you like.
• After the user string is concatenated with the unknown string, the message is padded using PKCS#7 to make sure the length is a multiple of block size.

Message 1 (1 Byte Message)

41	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	XX	02	02

After being encrypted and returned, the length would be 16 bytes, which we store as the starting size. We add another message byte and repeat.

Message 2 (2 Byte Message)

41	41	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	XX	XX	01

The response is still 16 bytes long, so we add another message byte and repeat.

Message 3 (3 Byte Message)

41	41	41	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	XX	XX	XX
08	08	08	08	08	08	08	08

The response size has increased to 24 bytes. We now stop, and subtract the current size from the starting size to find the block size.

Block Size = 24 - 16

Block Size = 8 bytes

Step 2 - Unknown String Size

This part is trivial now that we have determined the block size in the last step. We don’t even have to send any more messages to work this out.

The first message we sent was 1 byte long, and the response was 16 bytes long. This means the unknown string is guaranteed to be less than 16 bytes long.

We kept adding bytes to our message until the next block is added. Recall that in PKCS#7 padding, an entire block of padding is added when the plain-text length is a multiple of the block size.

• Look at Message 3 above, the plain-text (user-string || unknown-string) exactly filled 2 blocks

Because of this, we now know:

• length(user-string) + length(unknown-string) = 16 bytes
• length(unknown-string) = 16 bytes - length(user-string)
• length(unknown-string) = 16 bytes - 3 bytes
• length(unknown-string) = 13 bytes

The 16 bytes comes from the response length in Message 1. The 3 bytes comes from the length of our message when the response size increased.

Perfect, with just a little Math we know the length of the unknown string is 13 bytes!

Now let’s get to decrypting what unknown string is.

Step 3 - Determining the Unknown String

Our first step to finding the unknown string is to create a piece of plain-text that is bigger than the unknown string.

Since the unknown string is 13 bytes long, we’ll add enough extra bytes until it’s a multiple of the block size. Our plain-text will be 16 bytes long, since 16 is a multiple of 8 (block size), and is bigger than 13 (unknown string size).

The message we’ll send is 16 repeated bytes (we’ll use 0x41 again). If we send said message to the server, we know that it would look like this after the unknown string and padding is added:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	41	41
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	03	03	03

The only block of plain-text and cipher-text we’ll really be looking at is what block number the final block of plain-text is. Since we sent 2 blocks of plain-text, we’ll only be interested in the 2nd block of cipher-text. If we had sent 30 blocks of plain-text, we’d only focus on the 30th block of cipher-text.

Okay, now the fun stuff. Observe what we happen if we were to remove a single byte of our message. The first byte of the unknown string is now the last byte in block 2 (the highlighted row):

41	41	41	41	41	41	41	41
41	41	41	41	41	41	41	XX
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	04	04	04	04

How do we determine what that unknown byte is? By brute force!

A byte can only be 256 possible values. So we’ll send 256 messages, each with a different value in the final position of block 2.

Message 1 would look like this:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	41	00
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	03	03	03

Message 2 would look like this:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	41	01
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	03	03	03

…

Message 256 would look like this:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	41	FF
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	03	03	03

For each of the 256 messages, we store the cipher-text value of block 2 (the highlighted row) along with the byte that was added in a lookup table.

Now let’s send the earlier message with 1 byte less than a full block:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	41	XX
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	04	04	04	04

We can now get the cipher-text value of block 2, perform a lookup in our table, and see what byte is required to produce said cipher-text. It turns out it was 0x53.

We’ve just discovered the first byte of the unknown string, let’s find more!

Step 4 - Determining the Unknown String Continued

We’ve found the first byte, 1 down, 12 to go. We just need to rinse and repeat.

For the second byte, we first remove another byte of our message so that the first two bytes of the unknown string are in block 2:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	53	XX
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	05	05	05	05	05

Since we know the first byte of the unknown string, there are again only 256 possible values for the final byte. So let’s brute force again and create another lookup table. From now on we’ll be appending the recovered unknown string bytes to the end of our plain-text when doing the brute forcing.

41	41	41	41	41	41	41	41
41	41	41	41	41	41	53	00
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	03	03	03

41	41	41	41	41	41	41	41
41	41	41	41	41	41	53	01
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	XX	XX	03	03	03

With the new lookup table built, we can send our plain-text message (with no unknown string bytes added), extract block 2 of the cipher-text, and perform a lookup to see what byte produced that cipher-text:

41	41	41	41	41	41	41	41
41	41	41	41	41	41	53	XX
XX	XX	XX	XX	XX	XX	XX	XX
XX	XX	XX	05	05	05	05	05

It turns out the second byte was 0x65.

Awesome, 2 bytes down 11 to go. This step is just rinse and repeat until all the unknown string bytes are found.

Finishing Up

After repeating Step 4 eleven more times, we’ve found our unknown string for our example. It turns out it was SecretStuff@1.

Using this exact technique on the challenge cipher-text yielded the following unknown string.

Rollin' in my 5.0
With my rag-top down so my hair can blow
The girlies on standby waving just to say hi
Did you stop? No, I just drove by

Some final notes:

• We recovered this string without knowledge of the encryption key.
• This attack was not on the underlying cipher, it was against the cipher mode. AES is just as vulnerable to this attack as DES.
• This attack scales linearly O(N) and takes (256 * N) oracle function calls to complete, where N is the length of the unknown string. This could be lowered if you assumed/guessed the unknown string is only printable ASCII chars.
• Checkout the cryptopals website if you want to solve more problems like this and learn more about cryptography.