Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Understanding Padding Oracle attacks

It's been a long time I haven't written anything here... I've had to travel for work and have been doing other things and didn't find the right moment to write about anything useful. But a few days ago I decided to take a look at Padding Oracle attacks after hearing several times about them, and I thought it would be nice to share with you guys.

Padding Oracle attacks were introduced in 2002 in paper [1]. After that, several other papers have presented similar attacks based on the same concept for other padding schemes. In this post, I will restrict myself to the padding scheme presented in [1] and will add a list of references at the end for further reading.

Oracles and Padding Oracles

In cryptography, an oracle is basically a black box that responds to queries. For instance, an encryption oracle will encrypt any input you give to it under a certain key. A random oracle will always respond with uniformly random data, and this is useful to model protocols based on hash functions.

In our case, we are interested on padding oracles (PO). A PO is a sort of black box that decrypts an input message and tells you whether the padding was correct or not. For instance, think of an application that receives an input ciphertext and decrypts it using a block cipher.

Since a block cipher encrypts data in chunks of a given size, whenever the data to be encrypted does not fit exactly in a number of chunks it needs to be padded. Thus, after decryption our example application will check the padding applied and will throw an exception if the padding is incorrect. If it is correct, it will just continue with its normal processing.

As you can see, this application is an example of a padding oracle because it is telling us whether the padding is correct or not. We can check the behavior of the application and when we observe an exception we know that the padding was incorrect. When we do not, we know it was correct.

Mounting attacks based on padding oracles

So, how can we use such a PO to mount an attack on the system? The answer is it depends on the underlying cipher mode and on whether it is used properly or not, of course. Assuming the application uses a cipher in CBC mode, and it does only use encryption but no authentication, we can feed the application with specially crafted ciphertext and make assumptions about the plaintext based on the response.

Before going into the attack method, let's define the padding system we are going to look at. The PKCS#5 standard defines a padding scheme that works as follows: If the message length is a multiple of the block length, the padding scheme adds an extra block with all bytes set to the number of bytes in a block. Otherwise, the remaining bytes will be set to the number of padding bytes that need to be added to have an exact number of blocks.

If the block size is 8 bytes, then for a 7 bytes message you will add a byte set to 01; for a 6 bytes message, 2 bytes set to 02, and so on. I bet you get the idea 🙂

Now, when you decrypt in CBC mode, the process works as described earlier in this blog: first you decrypt a block, and then XOR it with the previous ciphertext block (or the IV if it is the initial block). This means that if you get a random data block, then append a target ciphertext block to it, and feed it into the random oracle, you will know whether the decryption of your ciphertext block XORed with your random data adheres to the padding scheme or not.

So, now we know that the decrypted message XORed our random data ends with either 1 byte set to 0x01, or 2 bytes set to 0x02, or 3 bytes set to 0x03, etc. In the most likely case, you'll be lucky with the first option. However, you still need to check, since it might be that by chance you got one of the other options.

How do you know then? Easy: start modifying bytes one at a time and feed them to the Oracle. To make it generic, start from the left-most byte. Modify it, and check with the oracle if the padding is incorrect. If it is incorrect, that means this byte was part of the padding, so the whole thing should be all 0x08's (assuming 8 byte blocks). If it is correct, continue with the next byte until you see that the padding turns incorrect or you reach the last byte.

This is what the original last byte decryption algorithm describes:

1. pick a few random bytes r1 , . . . , rb and take i = 0
2. pick r = r1 . . . rb-1 (rb XOR i)
3. if O(r|y) = 0 then increment i and go back to the previous step
4. replace rb by rb XOR i
5. for n = b down to 2 do
(a) take r = r1 . . . rb-n (rb-n+1 XOR 1)rb-n+2 . . . rb
(b) if O(r|y) = 0 then stop and output (rb-n+1 XOR n) . . . (rb XOR n)
6. output rb XOR 1

In the description above, b is the number of bytes in a block. In steps 1 to 3 it is discovering the last byte as I explained above. It creates b random bytes, and modifies only the last one until it gets a message with the right padding. Then it replaces this last byte with the correct value.

Now, using this value for r it has a good padding, so it starts modifying the bytes from the top and checking if this changes the results. If the result is not affected in any of the cases, then the last byte was set to 0x01 after decryption, and this means the last byte of the decrypted plaintext is our random byte rb XORed with 0x01. The same holds for the other cases, only that you need to XOR the random bytes with the appropriate value.

So the above algorithm works for the last byte, and if you are lucky for some other bytes as well. How do we turn it into a block decryption oracle?

Quite simple: assuming you know the final X bytes, generate a random block that after XORing with those known bytes sets the result to X+1. Now, the final block ends with an unknown byte followed by X bytes set to X+1... so now you start trying values to XOR with that unknown byte until you get a good padding response. At that point, you know that this unknown byte XORed the random data you supplied must give X+1 as a result to form a good padding (remember, good padding = Y last bytes set to a value Y).

So now you know one more byte, and you only need to iterate all the way till the end of the block to finish the decryption. The following algorithm was provided in the original paper:

1. take rk = ak XOR (b - j + 2) for k = j, . . . , b
2. pick r1 , . . . , rj-1 at random and take i = 0
3. take r = r1 . . . rj-2 (rj-1 XOR i) rj . . . rb
4. if O(r|y) = 0 then increment i and go back to the previous step
5. output rj-1 XOR i XOR (b - j + 2)

In this case, ak with k=j,...,b are the bytes you know. In step 1 you generate the random bytes that would set the final bytes to the appropriate value. Then you add some random numbers to them, and loop through the possible values for the unknown byte until you find the one that creates a proper padding (step 4). From this one, you construct the value for the unknown byte and return it in step 5.

Implementing the attack in Python

To make sure I understood what I explained above in the right way, I created a small python class able to decrypt any input block given a padding oracle. The class constructor takes an input block size together with a padding oracle in the form of a function returning a boolean value.

This means you can construct your own padding oracle function in python, which will simply return True or False depending on whether the padding was correct or not. This function can be a simple POC to test the concept or can be a function using a padding oracle present on a web site or whatever you can think of. See the presentation by Juliano Rizzo and Thai Duong ([3]) linked at the end for ideas ;).

By the way, the code quality might not be very good and some things might be done easier in Python than I've done them. I'm pretty new to Python so if you see anything you think should be changed let me know ;-). As for the code, you can do whatever you like with it.

As an example, I've used the following code to test the class:

'''
Created on Jul 4, 2010
 
@author: Eloi Sanfelix < eloi AT limited-entropy.com >
'''
 
from PaddingOracle.DecryptionOracle import DecryptionOracle
from Crypto.Cipher import DES
import random
import struct
 
def hex_string(data):
    x = struct.unpack("B"*len(data),data)
    return "".join([ hex(i)+" " for i in x])
 
#Random key globally initialized 
key = "".join([struct.pack("B",random.getrandbits(8)) for i in range(8) ])
 
def oracle(ctext):
    oracleCipher = DES.new(key,DES.MODE_CBC,"\x00"*8)
    ptext = oracleCipher.decrypt(ctext)
 
    paddingLen = struct.unpack("B",ptext[-1])[0]
    goodPadding = (ptext[-paddingLen:] == struct.pack("B",paddingLen)*paddingLen)
 
    return goodPadding
 
if __name__ == '__main__':
 
    #Random 2 block plaintext
    bytes = ""
    data = "".join([struct.pack("B",random.getrandbits(8)) for i in range(16) ])
    print "Plaintext: "+hex_string(data)
 
    cipher = DES.new(key,DES.MODE_CBC,"\x00"*8)
    ctext = cipher.encrypt(data)
 
    print "Ciphertext: "+hex_string(ctext)
 
    decryptOracle = DecryptionOracle(oracle,8)
 
    #Recover first block
    result = decryptOracle.decrypt_message(ctext)
 
    if(data == result ):
        print "CORRECT ptext recovered: "+hex_string(result)
    else:
        print "INCORRECT ptext recovered: "+hex_string(result)

Which provided the following output:

eloi:~/dev/PaddingOracle/src$ python PaddingOracleTest/DesPaddingOracle.py 
Plaintext: 0xd4 0xe2 0x4b 0xdf 0xed 0xad 0x75 0x58 0xfa 0x0 0xa5 0x45 0x17 0xc7 0x9b 0x5f 
Ciphertext: 0x98 0x8 0xd8 0xaf 0x69 0xab 0x34 0xe1 0x4a 0x61 0xa7 0x34 0xb2 0xc8 0xf 0x2b 
CORRECT ptext recovered: 0xd4 0xe2 0x4b 0xdf 0xed 0xad 0x75 0x58 0xfa 0x0 0xa5 0x45 0x17 0xc7 0x9b 0x5f 
eloi:~/dev/PaddingOracle/src$

You can see it works for my test case. I also tested it using AES encryption insted of DES and it works fine there too, which gives me confidence enough that the concepts above are correctly explained and the tool works appropriately 🙂

You can download the whole package with my DecryptionOracle class and the test cases here.

Hope you enjoyed it and I'm looking forward to see your feedback in the comments!

References

There is more to padding oracle attacks than exposed here. If you want to know more, you can check the following resources. I might be implementing other attacks as well in the future, but the fastest way to know more will be to read these papers:

[1] Security Flaws Induced by CBC Padding. Applications to SSL, IPSEC, WTLS... - S. Vaudenay - Download here
[2] Padding Oracle Attacks on the ISO CBC Mode Encryption Standard - K.G Patterson and A. Yau . Download here
[3] Practical Padding Oracle Attacks . Juliano Rizzo and Thai Duong . Download here