Background information

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. https://www.example.com/home.asp?UID=8A219A434525535FF324D4G56FC95348 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.

Exploitation

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. https://www.example.com/home.asp?UID=8A219A43|4525535F|F324D4G5|6FC95348 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.

https://www.example.com/home.asp?UID=00000000|4525535F|F324D4G5|6FC95348

But now, send the same request by incrementing the value of this initial block by 1.

https://www.example.com/home.asp?UID=00000001|4525535F|F324D4G5|6FC95348

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 ciphertext. Look at the CBC mode decryption figure.

Using this technique, we can work our way backward 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.