A Bit of Background
I recently encountered a fun little padding oracle attack as part of a CTF and found surprisingly few articles online outlining the attack. Of the articles I did find, most either discussed specific instances of the attack (POODLE) or described a lengthy sequence of mathematical operations which were difficult to follow. In this post I want to present a different, more visual description of the attack in the hope that some may find it useful and easier to understand.
Before talking about padding oracles, we need to talk about cipher modes and block ciphers. The cipher we will be using in our examples is the Rijndael block cipher which forms part of the Advanced Encryption Standard (AES). A block cipher is an algorithm which operates on fixed-length groups of bits (blocks). Contrast this with a stream cipher where each bit is encrypted one at a time. As a block cipher is only suitable for a single fixed-length message, additional steps are required to encrypt or decrypt messages longer (or shorter) than one block. A cipher mode algorithm describes how to apply the single-block operation repeatedly to securely encrypt or decrypt a message larger than a single block.
Padding oracles are commonly associated with block ciphers operating in Cipher Block Chaining (CBC) mode. In CBC mode each block of plaintext is mixed with the previous block before encryption. This prevents information leakage associated with the simpler Electronic Codebook (ECB) mode. In ECB mode each block is encrypted with the same key and so the same plaintext is always encrypted to the same ciphertext. This means patterns present in the plaintext will likely still be present in the ciphertext. We can see this in the images below comparing ECB and CBC modes.
Now that we understand the different encryption modes we can begin exploring how a message is encrypted and then onto the decryption stage where our padding oracle will enable us to decrypt the message without knowing the key.
Onto the padding oracle. An oracle is simply a mechanism to determine whether a test has passed or failed. So in our case a padding oracle is a weakness which enables us (the attacker) to determine if a message is successfully padded. The particular padding oracle we will be looking at occurs during decryption. The decryption process for CBC mode ciphers is to decrypt all blocks, validate and remove the padding then return the plaintext. How the server responds based on invalid padding will determine whether or not we can perform the attack.
A padding oracle attack exploits the padding validation step of decryption in order to decrypt the message without knowing the key. The attack relies on having a padding oracle which reveals whether or not a message is correctly padded. Typically this will be the decryption server responding with a verbose error message indicating the padding is invalid. However, other channels are also possible. For example a server may take longer to reply if a message is incorrectly padded, as long as it can be inferred whether or not a message is correctly padded the attack can be performed.
Now that we know what we’re looking for in a padding oracle we can walk through the decryption of our message and perform a padding oracle attack.
So what can we do to prevent this attack? The obvious fix is to not reveal whether or not a message is correctly padded. However, this is easier said than done. Providing a generic error if a message fails to decrypt will eliminate any obvious padding oracles. But timing-based padding oracles are much harder to detect and prevent. In a timing-based padding oracle, rather than an error message indicating invalid padding a server may take a noticibly different amount of time to process a correctly padded message from an incorrectly padded message. How long it takes the server to respond can then be used to determine if a message is correctly padded or not.
A much better approach is to encrypt the message and then append a Message Authentication Code (MAC) to verify the integrity of the ciphertext. The MAC is then validated by the server before any decryption occurs. If the validation fails, it indicates the message has been tampered with. The server can then refuse to continue decrypting the message. This ensures that there is no padding oracle, regardless of implementation details such as timings and error messages.
Hopefully this has helped explain padding oracles a little better, as well as illustrate how important it is to understand how to correctly implement cryptographic code as one small mistake can very quickly bring it tumbling down. An interesting takeaway is that this technique is not just limited to decryption. Padding oracles can also be exploited to forge valid ciphertext without knowing the key, but I'll leave that as an exercise for the reader. If you ever see a system which assumes that an encrypted value cannot be tampered with (session tokens are good ones), don't forget to check for padding oracles.
If you're interested in learning more please check out the links below. They really helped me while I was writing this article.