There are hundreds of web sites that describe the Padding Oracle attack, but many people find the concept confusing. I am going to try to explain everything you need to know. I am not going to write a bunch of equations to explain it. I’m not going to throw a big complicated diagram in front of you. You don’t have to understand encryption. I’ll just teach it to you one step at a time. It won’t make your head hurt. I promise.
This will help you write your own tool, or use an existing tool, and I’ll make it as simple as possible, while pointing out all of the tricky bits…
If you remember that A-B == C and you can add B to both side of the equation to get A== B+C, and if you understand HEX values and the Exclusive Or (XOR) function, you have all of the deep knowledge needed to understand the attack.
Why are Padding Oracle Attacks important?
This type of attack is well known, and a lot of sites are vulnerable to this attack. It’s a common error. And it’s devastating because it works so fast. To understand the attack, you have to understand a a few simple things about cryptography.
What is Cryptographic Padding?
There are two types of encryption – stream based and block based. A stream based encryption system can be used to encrypt any number of bytes. A block-based encryption algorithm encrypts text in blocks. AES-128 uses 16-byte (i.e. 16*8 or 128-bit) blocks. If you want to encrypt a single character with AES, you get 16 characters out. 17 Characters takes 2 blocks, or 32 characters total.
What happens if your cleartext is shorter than a block? It’s padded with extra characters to fill up the block before it’s encrypted because you have to encrypt a block. These could be null characters, or random characters, but how do you tell the difference between important characters and extra characters?
There are several ways to do this. PKCS#7 is a typical example. If you have 15 bytes and need to add one more byte to fill up the block, you append hex (01). If you need to add 2 bytes, you append hex(02 02). 3 Bytes requires you add the 3-byte pad of hex(03 03 03). Note that this allows a form of error checking, because there is some redundancy when more that a single byte is added. If the last byte has the hex value of 04, then the previous 3 bytes have the same value. If not, then that is a padding error.
If the text fills up the 16-byte-block exactly, you add another block that contains 16 bytes hex(10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10). Each of these values have the binary value of 16.
The important point is that you always have padding, from 1 to 16 characters., to the last block.
Here is a table that shows how cleartext (in blue) is padded (in black) before the block of 16 bytes is encrypted, just in case this isn’t clear.
Table 1 – PKCS#7 padding on a 16-byte block
What is an Padding Oracle?
An Oracle is a system that reveals information. Normally, a system that uses encryption either works or doesn’t. However, if the system reveals extra information – like if padding was valid, then this is called a Padding Oracle.
Hey Oracle! Does this block have proper padding? Tell me!
While the technical term is Padding Oracle, think of it as a blabbermouth.
What is Cipher Block Chaining (CBC)?
Classic block encryption, such as AES, has a problem. AES can be used several ways, but the simplest is called ECB or Electronic Codebook Mode. In this mode, a block of data is transformed. There is no information used from a previous block of data that affects the transformation. When you encrypt the same data, the output or ciphertext is identical. If I encrypt 16 “A” characters, the output will be the same.
Or to put it another way, every time I encrypt my “Beans and Franks” recipe, the result is identical. If I send it to Alice, and I send to Bob, someone can see that I sent the same recipe to both people. It’s a cookbook. The recipes don’t change as long as we keep the same book.
One way to fix this problem is to combine or “chain” the results of the previous encryption block with the next block, so if the input is repeated, the results is different. One of these methods is called Cipher Block Chaining or CBC.
How does Cipher Block Chaining (CBC) work?
A better explanation of CBC is found on Wikipedia, but the most important point to understand is that when decoding block N, Block N is first decrypted, then XOR’ed with the previous block N-1.
The cleartext of Block N-1 does not matter when decoding Block N.
This detail is critical. Let me elaborate with an example. When CBC-mode is used, you need an Initialization Vector (IV) before you decrypt the encrypted block. In simple terms, this is a block of data that is usually sent as the first block of the data.
- Block 1 is used as the IV for Block 2.
- Block 2 is used as the IV for Block 3, etc.
Let’s say a system transmits the encrypted block LCB0byB0aGUgcG9p with the IV of all zeros. The IV should be random, but for the sake of this explanation, let’s assume it’s all zeros. So the decryption system is sent the following 32 hex bytes (2 blocks)
0000000000000000 LCB0byB0aGUgcG9p
Now let’s suppose the cleartext decodes the second 16-byte block to “AAAAAAA Pay $100″ or hex(41 41 41 41 41 41 41 20 50 61 79 20 24 31 30 30)
The ASCII character for “1” is hex(31), shown in bold above. Suppose I want to change the $100 to $500. The ASCII value for “5” is just one bit different, or hex(35) instead of hex(31). In other words, suppose I wanted to modify the encrypted message and change 100 to 500, i.e.:
“AAAAAAA Pay $500″ is hex(41 41 41 41 41 41 41 20 50 61 79 20 24 35 30 30)
All I have to do to change the cleartext from $100 to $500 is to flip the matching bit in the Initialization Vector and send:
0000000000040000 LCB0byB0aGUgcG9p
In other words:
When I invert a single bit in the previous block, the matching bit in the decrypted cleartext will be inverted.
It may seem unbelievable, but that’s all it takes. I don’t have to know the secret key used to encrypt the message to modify it. All I have to do is change the previous block, and this changes the decrypted value of the message. CBC-mode does nothing to check the integrity of the message. It’s vulnerable to this sort of attack. Scary, huh? If I know the cleartext of one block, I can modify it to be anything I want by manipulating the previous block, without knowing anything about the encryption.
What’s required to perform a Padding Oracle Attack
There are two things you need to attack a Padding Oracle:
- You need a Padding Oracle.
- You need a way to capture and replay an encrypted message to that oracle. In other words, you need to be able to send and modify the message to the Oracle.
Once you have that, you can decode the decrypted message.
What is a Padding Oracle Attack?
In the previous attack, I just modified a single bit. But I could modify any bit I want to, trying any of the 256 different values.
Normally modifying the message does not provide a way to guess the contents, because it’s encrypted and I don’t know what the decrypted message is. However, if we can sent the message to the Padding Oracle, and it returns “Good Padding” or “Bad Padding” – then we can defeat the system.
The value hex(01) is valid padding when we have to add a single byte pad, so if we try all 256 combinations of the last byte, and one of these returns “Valid Padding”, then we know now what the cleartext of that byte is, thanks to the blabbermouth oracle.
How do you crack the byte once you found it has valid padding?
Let’s assume the byte we are modifying has the value Q (for Question Mark). And we are trying all 256 values of R (for Random) , so that the result is Valid Padding, i.e.
Q XOR R == hex(01)
and if you want the mathematical form, that would be
Q ⊕ R == hex(01)
Now’s it’s time for a little bit of Math. Not too much, though. We can XOR the same value to both sides of the equation and the equation will still be true. If we XOR the same number to itself, it becomes all zeros, and Q ⊕ hex(00) == Q. Therefore we now know the following:
Q == R ⊕ hex(01)
Or in other words, when we XOR the expected padding to the random guess, we get the cleartext value of the corresponding byte.
Okay – we are done with the math. You can relax now. The rest is easy.
Once you crack the last byte, how do you crack the previous byte?
Once we know the value for the last byte (Byte 16) of the block N, we XOR the desired padding for a 2-byte pad into block N-1. The 2-byte padding is hex(02 02). In reality, we need to XOR three values together:
- The original 16-byte block that precedes the block we are attacking
- The padding (the number of bytes depends on which pad we are using)
- The guessed cleartext (initially all nulls)
If, for example, we learn that byte 16 is ‘A’ hex(41), then to guess byte 15, we modify the previous block by XORing the bytes
OriginalBlock XOR hex(02 02) XOR hex (00 41)
But I should make it clear that we are working with 16-byte blocks
- OriginalBlock
- hex(00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 02)
- hex (00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 41)
and we XOR all possible 256 values into the byte we are randomly guessing, which is byte 15 in this case:
- hex (00 00 00 00 00 00 00 00 00 00 00 00 00 00 XX 00 )
When one of the values returns valid padding, we know that the cleartext for the 15th byte is R ⊕ hex(02)
And for Byte 14, we XOR the newly learned value for byte 15 into the guessed cleartext, use hex(03 03 03) as the padding we XOR, and then we try all values for byte 14. That is, we shift one byte to the left, and change the padding string to be the proper length and replicated value, shown in Table 1 above.
If we continue this, we can guess all 16 bytes of the last block.
Padding Oracle Attacks do not use encryption
Note that I just use the XOR function. It doesn’t matter what the encryption is. We never need to perform any encryption functions to do the attack. This attack does not require a powerful CPU or crypto accelerator. We just toggle bits, one byte at a time.
Padding Oracle Attacks decodes the cleartext without knowing the key
Also – this attack does not use or reveal the encryption key. I can’t determine the key, and can’t use it to decode other messages. I can only attack a message I have captured and can replay.
Padding Oracle Attacks only decode the last block sent
Since we are trying to fake the padding, this only works on the last block of the chain. If more blocks are sent, the oracle only checks the last block for proper padding.
You don’t have to send every block to the Oracle.
The attack works on the last block I sent the oracle, but I don’t have to send all of the blocks. If I have captured 10 blocks, I can break the 10th block. But after I learn what the cleartext of block 10 is, I could just send 9 blocks. Or 8. Or 7. In other words, once I have cracked the last block, I can simply truncate that block from my test, making the previous block (e.g. 9) be the the new last block.
Because of the way CBC-mode works, all I need to do is send 2 blocks. If I wanted to attack block 7, there is only one requirement – it’s the last block I send. I can send blocks 1 through 7. Or I can just send blocks 6 and 7.
I only need to send 2 blocks; any 2 consecutive blocks.
In other words, I can crack the blocks in any order I want to. I can just send the IV and the first block and decode block 1. Then I can send blocks 1 and 2 to crack 2.
Padding Oracle Attacks can be completed in less than 256 * Number of Encrypted Bytes attempts
This is one of the reasons the attack is so dangerous. If each test takes a 1ms, then to crack 16000 characters takes 256*1600*1 milliseconds, which is 4096 seconds., or a little more than an hour.
Instead of trying all 256 values, we can stop once we find a valid pad. Therefore the average number of guesses would be 128, so a more realistic estimate would be the above number divided by 2, which is 30 minutes.
There is a special case when guessing the last padded block
If you implement your own version of this attack, you may want to check to see how many times you get a valid pad for each byte. You should get exactly one correct answer. If you get zero, or more than 1, you have a bug.
There is a special case you should be aware of.
Let’s say the block you are guessing is the last block, that is, the block with proper padding. Let’s assume the block has, for example, 7 bytes of padding, ending in
hex(07 07 07 07 07 07 07)
If we try every combination, one of the combinations will modify the last 7 bytes to be
hex(07 07 07 07 07 07 01)
In other words, there are two “values” for byte 16 where you have valid padding. One way to check for this is to see if the block has valid padding before you start. You can also check if the padding is hex(01) and the guess is hex(01) is the same, and if you get a valid padding when these are the same. If so, then ignore it.
Congratulations – you are now an expert in Padding Oracle Attacks
