Wtf is a padding oracle attack (POA) and how does it work?
We will answer this question based on a (hopefully) simple example. But first, we need to clarify some basics.
How do block ciphers work?
Block ciphers do not en- and decrypt messages bit by bit. Instead messages (m) are split into blocks of a certain size (n).
How does RFC 2040 padding work?
As block ciphers always need blocks of a certain size (n), messages with a size which is not a multiple of n, have to be padded. The padding described in RFC 2040 has the following form:
- If there is one byte of padding, the padding byte has the value 01
- If there are two bytes of padding, the two bytes have the value 02
- If there are three bytes of padding, the three bytes have the value 03
…and so on and so forth.
Please note that at the end of a message, we do ALWAYS need a padding, so we are able to recognize the end of a message. If the message size is a multiple of the block size n, a full block of padding has to be added at the end of the message.
By the way, what is an oracle?
An oracle is a counterpart which retrieves some information and provides a certain answer based on the given information. In our case, it is a server that retrieves some cipher text. If the cipher text doesn’t have a valid RFC 2040 padding, the server returns an error message.
How does CBC mode work?
The last thing to remember is the Cipher Block Chaining mode. Mapping a certain input to the same corresponding output leads to weakness against statistical attacks. To make things less predictable CBC takes the cipher text from a previous encrypted block and XORs it to the new input like shown below. For the very first block – when there is no previous cipher text – an initialization vector (IV) is XORed to the input.
So what’s wrong with CBC mode?
CBC is malleable! We will stick to the following image to explain the problems. It shows an example of decrypting a cipher text (c) using a secret key (k) to retrieve the plain text (m).
The first problem to mention is that the XOR operation of CBC is done after the decryption operation (and before the encryption operation). This enables an attacker to flip a specified plain text bit by flipping corresponding cipher text bit without knowing any part of the secret key. From the example: if an attacker flips the last bit of the known IV (green), it will be XORed after decryption operation (yellow), hence it will flip the last bit of the plain text.
The second problem is that during decryption the cipher text blocks are only depending on their predecessors. For our example this means that we are able to only have a look at the decryption of the first block (red dottet area). We are able to completely skip the rest of the message and concentrate only on the first block, and still we have a valid decryption operation here.
Now we have everything together to start a POA.
Step by step guide to padding oracle attack
For the step by step guide we will stick to the example of the previous image (red dotted area). Requirements for the attack are following:
- we need to know the original IV and cipher text block c1, which can usually be collected by eavesdropping on the network
- we need the possibility to send messages to the oracle and retrieve its answers somehow
We will now try to learn the last byte of the first message block m1.
Step 1: Collecting data
We eavesdrop on the network and collect IV, c1, c2 and c3.
Step 2: Choose random IV‘ with to generate incorrect padding
With help of the oracle, we can start decrypting c1 like this: Instead of the original IV we choose a random IV‘ and prepend it to the cipher text block c1. This message is then sent to the oracle.
As c1 is now the last message, the oracle has to assume that it has a padding. Remember, a message has to end with a padding. The padding has to follow a specific format (01 if the last byte is padded, 02 if the last two bytes are padded, …). There is a high chance, that the padding format of m1′ is incorrect and the server returns an error message. If the server does not return an error message, we choose a new random IV‘ and run Step 2 again.
Step 3: Modify IV‘ until padding is valid
Now that we retrieved an error message from the oracle, we start modifying the last byte of IV‘ until the oracle does no longer send an error message. As we are modifying just one byte, we only have to do this 255 times maximum.
If the oracle does not return an error message, the padding of m1′ is correct. Most likely, m1′ ends with 01 now. There is also the possibility that it ends with 0202, 030303, …, but the chance is a lot lower. We elimitate this posibility by modifying the second last byte of IV‘ and send the message to the oracle again. If the message m1′ is still valid, its last byte has to be 01 by 100%.
So… now we have a somehow random IV‘ and our somehow random plain text m1′, what can we learn from that?
Step 4: Learn the original plain text
It might not be obvious yet, but getting the original plain text is very simple now. Let’s add an intermediate step between the decryption and the XOR operation.
The last byte (xi) of the decryption output (x) can easily be calculated by XORing the last byte of our IV‘ and 01. Remember, we are sure that the last byte of m1′ is 01 because of Step 3.
xi = IV’i XOR 01
Can you already predict the happy ending? Have a closer look at the intermediate result x. It does NOT depend on the IV‘ at all. So all our changes we did to it, are completely irrelevant! xi is in fact the original intermediate result of the dec(c1, k)!
With this knowledge about xi see what happens if we use the original IV again:
Using the original IV instead of our manipulated IV‘, we are now able to reconstruct the last byte of the original plain text m1 by XORing the last byte of IV and the byte of x. We just got the original plain text without having any idea of the secret key. There’s only “public” information needed.
We have our first plain text byte now and as you might assume, the steps above can be implemented and performed in software very quickly. But how can we proceed and get to know the other bytes, and also the other blocks?
Proceeding to the next byte
Having just the last byte of the first block of a message does not seem to be a big deal, but getting the next one is quite simple. We can use the specification of the RFC 2040 padding again. First, we increment the last byte our message m1′ from 01 to 02. This can by achieved by flipping the last two bits of our IV‘. Remember: Our IV‘ XORed with some other value caused our plain text m1′ to end with the byte 01 (see Step 3). If we now flip the last two bits of IV‘, the last two bits of m1′ will also be flipped during the XOR operation. In binary terms, this means that there was a 00000001 before, and after flipping the last two bits, there will be a 00000010, so we performed a simple incrementation here.
After that, we can just go back and repeat Step 3 and modify the second last byte of our IV‘ until the oracle stops sending error messages. We are able to learn the intermediate result xi-1 like we did in Step 4. And then we are able to get the next original plain text byte by XORing xi-1 and the original IV.
This method can be repeated until we learned the whole message block m1.
Proceeding to the next block
Decrypting m2 is staightforward. The following message blocks can be decrypted using the steps from above with one small adjustment. Instead of choosing a random IV‘ to start with, we just choose a random m1′.
Interesting fact: secrets do not matter
As we found out in the step by step guide, a padding oracle attack can be performed without any knowledge about the secret key. Furhtermore the secret key and the encryption/decryption operation is not involved in any of the mathematical/logical operations during the attack. This means, it is completely irrelevant which block cipher (DES, 3DES, AES, …) is being used. It is also irrelevant if the key length is 128 bit, 512 bit or 4096 bit. If CBC and RFC 2040 padding is in place, the example attack works for all of them.
I hope this post can save someones tortured soul and bring some light into the darkness of padding oracle attacks.