Padding Oracle Attack
Firstly, this vulnerability is not related to the Oracle database or the Oracle Company in any way. In cryptography, an ‘oracle’ is a system that performs cryptographic actions by taking in certain input. Hence a ‘padding oracle’ is a type of system that takes in encrypted data from the user, decrypts it and verifies whether the padding is correct or not. Before getting into the attack details, the below sections throws light on some of the basic concepts that the user needs to be familiar with in order to understand the exploitation.
In my previous article, I described the types of encryption schemes available. Here is a quick summary of them.
There are two types of encryption schemes:
Symmetric key encryption: Encryption and decryption keys are the same.
Asymmetric key encryption: Encryption and decryption keys are not the same.
Symmetric key encryption can use either stream ciphers or block ciphers. A stream cipher encrypts one bit at a time, while a block cipher encrypts plaintext in chunks. Once again, even in this article we need to learn more about block ciphers. So here are the two notable points about block ciphers.
They operate on fixed size data (eg. 64-bit for DES, 128-bit for AES, etc.)
They operate in modes. There are different modes of operation, such as CBC, ECB, etc.
In CBC mode, to make each message unique, an initialization vector (IV) is used in the first block. An IV is a random string that is XORed with the plaintext message prior to encryption. Each block of plaintext is XORed with the previous cipher text block before being encrypted. In other words, each cipher text block depends on all plaintext blocks processed up to that point, as shown in the figure below. It’s important to note that here IV is not a secret; it only adds randomness to the output. IV is sent along with the message in clear text format.
What is padding?
Although a block cipher operates on fixed size data, it is understandable that the incoming messages or the data is not fixed in length. For example, take a look at the two messages below and say you would want the block size to be 8. For Message 1, you can easily divide it into 3 parts with block size as 8 (8 A’s+8 B’s+8 C’s). But for Message 2, you would be short by 4 letters if you want to apply the block size as 8. Hence padding was introduced to overcome this limitation.
Message 1: AAAAAAAABBBBBBBBCCCCCCCC
Message 2: AAAAAAAABBBBBBBBCCCC
In simple terms, padding adds those extra few bits which are necessary before encryption to make a meaningful block. There are different padding schemes. However, for this article we are only interested in the PKCS #5 standard. It is relatively easy to understand compared to others.
In PKCS#5, the final block of plaintext is padded with N bytes of value N. For instance, consider the below screenshot. The block sizes of all the examples mentioned below is 8 bytes. In Ex1, there are 5 bytes missing. Hence all those 5 places are going to be filled with 0x05. Similarly, take Ex3 where 1 byte is missing. Hence that place is going to be filled with 0x01.
The attack scenario
Finally, with all this information, let us now focus on how the attack is accomplished. First, let us consider the below URL.
Let us assume that some information is sent in this UID parameter (say username) in encrypted form using the CBC mode and PKCS #5 standard. So the application decrypts this value and returns the results based on that value. In other words, there are 3 possible scenarios that can occur when the application is passed with different values in the UID parameter.
Case 1: Valid cipher text – Valid and normal page
- Case 2: Invalid cipher text [with improper padding] – Invalid page [such as 404]
- Case 3: Valid cipher text but invalid padding [error]
To clarify, below are corresponding examples for each of these 3 cases listed above.
Example Case 1: Say you sent the value UID=8A219A434525535FF324D4G56FC95348 and it decrypts to a valid user ‘tom’. Then the application would send a normal response. (This is the URL that ‘tom’ would have grabbed after logging in).
Example Case 2: Say you sent the value UID=998877PA434525535FF324D4G56FC95348 and it decrypts to ‘xxx’ (invalid user). The application might respond back with a 404 message saying no such page exists.
Example Case 3: Say you sent the value UID=66IXS7IA434525535FF324D4G56FC95348 and it decrypts to ‘sam’ (valid user) but with invalid padding. The application would return some exception.
Thus, if you can send different cipher texts and find out if they decrypt to different values with valid padding or not,
then you can decrypt any given cipher text. So it all boils down to finding an application which returns a 200 OK message for a valid cipher text and an exception (usually 500 error) for a tampered cipher text.
Take a look at the CBC mode of decryption in the below figure.
Simple and main point: In CBC decryption, each cipher text is passed through the cipher, then XORed with the previous cipher text block to give the plaintext.
So if you take our above example, the cipher blocks would be first created as shown below.
Cipher blocks: 8A219A43| 4525535F| F324D4G5| 6FC95348
Hence the first cipher block is going to be used during the plaintext calculation of second cipher block. Follow the below steps to understand the attack in a phased manner.
If the below request with initial block of all zeros is sent, it would most probably result in 500, since it might not decrypt to any valid value.
But now, send the same request by incrementing the value of this initial block by 1.
Notice that although the request returns an error, the last value of the decrypted cipher text has changed since you sent 0x01 in the request.
Thus, if we increment just the last byte in the IV each time (up to FF) we will inevitably hit a value that produces a valid padding sequence. Only one value (out of the possible 256 different bytes) will produce the correct padding byte of 0x01. When you hit this value, you should end up with a different response than the other 255 requests.
From this, we can now deduce the ‘intermediary value’ at this position, since we know that when XORed with 0x3C, it produces 0x01.
If [Intermediary Byte] ^ 0x3C == 0x01,
then [Intermediary Byte] == 0x3C ^ 0x01,
so [Intermediary Byte] == 0x3D
Once you know the intermediary byte value, we can deduce what the actual decrypted value is. Just XOR it with the previous cipher text. Look at the CBC mode decryption figure.
Using this technique, we can work our way backwards through the entire block until every byte of the intermediary value is cracked, thus getting the decrypted value one at a time. Whatever process has been described above is automated with tools such as Padbuster, etc. which are handy if you want to show a PoC to the application owner.