The Vaudenay Padding Oracle Attack↑

The Vaudenay attack on block cipher encryption in CBC mode with PKCS#7 padding is a padding oracle or error oracle attack. It is a plaintext-recovery attack.

Pre-requisites for the Attack↑

A message encrypted under some key k (the target for the attack).

Access to an oracle which allows the attacker to determine whether a particular ciphertext is accepted as a valid PKCS#7 plaintext after being decrypted under k.

Note that the oracle does not give the attacker access to the plaintext result from the decryption, it just leaks information about whether the ciphertext contained a valid plaintext or not. In real-world examples, such an oracle often arises when a system will behave differently if it receives a valid message from when it receives an invalid one. For example, a protocol using CBC encryption may give an error message if it receives an invalid ciphertext, or proceed with the rest of the protocol if it receives a valid one.

How the attack works↑

This is a chosen-ciphertext attack: the attacker manipulates the ciphertext in various ways and then sends it to the oracle to see if it is accepted or not. From the pattern of accepts and rejects, he is able to deduce the value of the plaintext. For more details see Vaudenay 2003.

Work factor↑

The attack is extremely efficient. It requires O(NbW) calls to the oracle, where b is the block cipher size in words, W is the word size and N is the number of blocks in the message. For example, to decrypt an N block AES message (16 byte block size) would take 128N oracle calls on average. For very short messages, this can be improved still further (see section 3).

Mitigations↑

Use an Authenticated Encryption mode such as GCM, CCM, OCB, that prevents manipulation of ciphertexts. Note it is important to also make sure CBC is removed from the API.
If CBC must be used, alternative (non-standard) padding schemes can eliminate the oracle.
A MAC can be added to a CBC ciphertext to check it has not been tampered with. The decryption command should check the MAC on the ciphertext before attempting decryption. It is important the MAC is calculated using a separate key from the encryption operation, otherwise security of both can be lost.

Real-world instances of the attack↑

Real-world variations of this attack are widespread. These include attacks on TLS (BEAST), web frameworks, XML Encryption and PKCS#11 Cryptographic Hardware.

Notes and Variations↑

In some circumstances, the oracle can also be used to crack a plaintext that has been encrypted under a different mode (with the same key).