On a recent pentest, I encountered an authentication system that used a block cipher in CBC mode, which I was able to break using a Padding Oracle. The vulnerability required access to valid ciphertext, which limited the scope of the attack, but it was possible to decrypt a full authentication token in about an hour even though the token was encrypted with AES-256.
Cryptography is difficult to implement securely due to the fact that it is complicated and requires many moving parts, and if any of these components are not handled properly, the entire system can be compromised.
The problem with CBC mode is that it is malleable. Recently, researchers broke PDF encryption using CBC Gadgets to inject content into an encrypted document (https://pdf-insecurity.org/encryption/cbc-malleability.html). The notion that simply because something is encrypted it can be trusted is false. Here are some reasons why.
Bit Flipping Attacks
In CBC mode, each block of plaintext is XOR’d against the previous block of ciphertext BEFORE encryption (the first block of plaintext is XOR’d against a block known as the Initialization Vector). This makes the value that is encrypted completely dependent on the prior ciphertext block.
During decryption the process is in reverse. A block is decrypted to an intermediate value, and then this intermediate value is XOR’d against the previous ciphertext block to return to the original plaintext.
XOR, or Exclusive OR, is a commutative operation, much like addition. For example,
a = b ⊕ c b = a ⊕ c c = b ⊕ a
Also, anything XOR’d against itself will become 0
0 = a ⊕ a
A ciphertext is by design a public thing. The plaintext and the key are the secrets. So in a crypto system, an attacker can see a ciphertext.
The problem with CBC mode is that the decryption of blocks is dependant on the previous ciphertext block. This means attackers can manipulate the decryption of a block by tampering with the previous block using the commutative property of XOR.
Say an authorization token contains the value and it is encrypted using AES-256 in CBC mode
loggedin=0
Assume an attacker also knows the structure of this token; i.e. they know that the value of 0 is in the 10th position of the block. If the token decrypts to
loggedin=1
then the application will assume the request is authenticated. This is very easy to forge in CBC mode by manipulating the previous block.
Walking through this step by step
The loggedin=0 block is decrypted to the intermediate value, but it is not yet the plaintext loggedin=0
The intermediate value is XOR’d against the previous block
The 0 in the 10th byte of the resulting plaintext is the result of the XOR between the 10th byte of the previous block and the 10th byte of the intermediate value, ie
0 = previous_block[10] ⊕ intermediate_value[10]
In order to authenticate, an attacker needs to make the following construction true
1 = previous_block[10] ⊕ intermediate_value[10]
This example is simple, because anything XOR’d by itself is 0, so when the plaintext decrypts to 0 here, we know that
previous_block[10] == intermediate_value[10]
To get an output of 1, we simply need to chain an additional XOR. The value is easy to calculate and must be placed in the 10th byte of the attacker’s previous block.
1 = previous_block[10] ⊕ intermediate_value[10] ⊕ 1
Under such an attack, the attacker’s previous block will decrypt to garbage, so for this to work, that garbage needs to be discarded by the application (think of tokens that are split on &, for example). If an attacker can safely get the application to ignore the garbage, then the target block would decrypt to a forged authenticated token.
Note, CTR mode is also vulnerable to an attack like this, but in an even more direct fashion, as previous blocks don’t need to be tampered with.
Padding Oracles
While Padding Oracles do not recover the encryption key, a ciphertext encrypted with that key can be decrypted with 256 guesses per byte. The reason the vulnerability exists is because block ciphers must have valid padding, and encryption algorithms will handle the padding for developers during encryption. Consequently, during development and testing, valid ciphertexts are used and developers may never even be aware padding exists. This is dangerous because not handling padding errors safely can compromise the system.
So what is padding and why is it necessary?
A block cipher deals with fixed sizes of data, or blocks. In AES, the block size is 16 bytes, or 128 bits. A ciphertext block will always be 16 bytes, and so plaintext must also always be in blocks of 16 bytes. Real world scenarios don’t conform to such requirements, however. If the plaintext is 20 bytes in length, the first 16 bytes will form a block, and the remaining 4 bytes will be 12 bytes short of the 16 byte block size. Those remaining 12 bytes will get filled with padding.
The PKCS#7 standard defines how this padding is constructed, and it is quite simple. The number of padding bytes will be filled with the value of how much padding is necessary. To demonstrate, here we have 13 bytes of plaintext, and 3 bytes of padding. So we pad the 13 bytes with 3 bytes of \x03.
s o m e p l a i n t e x t \x03 \x03 \x03 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Padding can be anywhere from 1 to 16 bytes. The reason 16 bytes of padding would exist is if the plaintext evenly falls into 16 byte blocks. An additional block of only padding would then be required so that the algorithm knows the padding is valid.
During decryption, a ciphertext is first decrypted and then the padding is discarded. If the ciphertext was not tampered with, then the padding will be valid. But if the padding can’t be found and the application errors, then an attacker can leverage this error as an oracle.
Using techniques similar to those in the bit flipping attack, an attacker can force decryption of a block to one that has valid padding if the application provides information when the padding is invalid. This is because for each byte in the target block, there will be an 8bit value in the previous block that XORs the intermediate value into valid padding. For instance, for the last byte of the block, we are looking for a padding of \x01. So a valid equation would look like this:
attackers_previous_block[15] ⊕ intermediate_value[15] = \x01
Using XORs commutative property, and the original previous block, we can then decrypt the last byte of the target block
intermediate_value[15] = attackers_previous_block[15] ⊕ \x01 plaintext[15] = original_previous_block[15] ⊕ intermediate_value[15]
Knowing the last byte of plaintext, the attacker would then need to find a block that decrypts to intermediate values that end in \x02\x02, \x03\x03\x03, \x04\x04\x04\x04, etc. This allows for an efficient decryption of a ciphertext without ever knowing the key, simply because the application didn’t handle an error.
Recommendations
Just because something is encrypted, doesn’t make it trustworthy. To ensure the integrity of ciphertexts, sign them with a Message Authentication Code (MAC), or consider using a block cipher mode that provides authentication, such as GCM. For authentication tokens, using an HMAC with SHA-256 is advisable.