Breaking ECB by prepending your own message.
This is a small write up on how the AES ECB mode can be broken without much computing power if you have the ability to prepend your own message to the plaintext. I strongly recommend checking out Cryptohack.org if you want to try it out for yourself. See the ECB Oracle Challenge.
The ECB Mode
ECB is the easiest Block Cipher Mode there is. The plaintext is divided into n block sized chunks and each chunk is encrypted separately. If the plaintext is not divisible by the block size, bytes will be appended in order to fit into the block size. The biggest flaw here is that blocks are completely independent. This might be good for parallelization but leaves us with the ability to easily crack the plaintext if we have the means to prepend our own text to said plaintext.
Step 1: Get the Block Size
The first step is to get to know our target block size. Since we assume we have the ability to prepend bytes to the unknown plaintext we start by prepending single bytes to the plaintext message and watch how the output length changes.
Let’s start by checking the length of the encrypted output. For this example we imagine the initial length of the encrypted output to be 8 bytes. We now start by prepending a single byte to our unknown plaintext. After the first added byte our encrypted output length did not change at all. It seems the plaintext itself is smaller than 8 bytes and in order to encrypt it with ECB, filler bytes have been added. So we need to continue adding bytes until we observe a change in the length of the encrypted output. In our case we see a change from 8 bytes to 16 bytes after the third byte added. The difference in length has to be our block size! Not only that but we also know how long the initial plaintext is. If the block size is 8 and we needed to append 3 bytes in order to overflow the first block we know the initial plaintext has to be 6 bytes!
?????? + FF -> ??????FF
?????? + F + B -> ??????FB
?????? + BB -> ??????BB
?????? + BBB -> ??????BB BFFFFFFF? being the unknown plaintext, F a filler byte appended by AES in order to be divisible by the block size and B being our own byte we append. I appended bytes instead of prepending them here for easier visualization.
That’s all we need for our attack!
Step 2: Brute-forcing our way to success
In order to crack the code we need to prepend a known pattern to the unknown plaintext until only one byte of the plaintext is part of our blocks. Since blocks are completely independent in ECB Mode we only need to brute-force a single byte, or 2⁸ combinations, in each step. We repeat this step until we cracked all 6 bytes of the plaintext. Let me visualize this for better understanding.
First select your known sequence. It doesn’t matter what sequence you choose but for this demonstration I chose the ASCII character X repeated n times. How long do we need to make our sequence? Well since our goal is to replace our know sequence byte by byte with bytes from the plaintext we need at least S bytes:
P being the length of our plaintext (6 bytes) and B the block size (8 bytes). In our example S would be 8 bytes.
Let’s decrypt the plaintext:
Step Block 1 Block 2
0 XXXXXXXX ??????FF1 XXXXXXX? ?????FFF
2 XXXXXXP? ????FFFF
3 XXXXXPP? ???FFFFF
4 XXXXPPP? ??FFFFFF
5 XXXPPPP? ?FFFFFFF
6 XXPPPPPP
X is our know byte sequence. This can represent the actual ASCII representation of X or any other byte you like. ? is the encrypted plaintext. P is the decrypted plaintext and F is a filler byte just like before.
In each step we remove one of our sequence byte X and send it to our target for encryption. We already know that the first block of this encrypted message contains 7 times the character X and only one unknown byte.
To crack the single byte just replace ? with all 2⁸ combinations of a single byte and encrypt it with AES until the first encrypted block of our output is equal to the first encrypted block of the encrypted message we got from our target.
After this we successfully cracked the first byte of the unknown plaintext. In the next step we remove yet another one of our sequence bytes and send it for encryption. This time 2 bytes of the plaintext will be part of our block, but we know already what the first byte is! So it’s the same procedure as with the first byte just that our known sequence changed from XXXXXX to XXXXXXP with P being our known plaintext byte. We still know 7 out of 8 bytes!
At a maximum we would only need 6 * 2⁸ AES calls to break this message. Compared to (2⁸)⁶ calls if you just brute-force the block without any hints.
