Multi-block Vaudenay attack · 3 cipher blocks · 48 bytes
Padding oracles are the most well-known of a class of vulnerabilities called format oracles. A format oracle exploits a crypto system through a side channel: a victim accepts untrusted ciphertext, attempts to decrypt it, and then — depending on the result — does one thing or another in a way that is visible to the adversary.
That observable difference can arise from an implementation bug, or from the intended functionality of the system. Either way, it leaks information about the plaintext, one query at a time.
To understand how this works, we first need to understand how CBC mode chains blocks together, why block ciphers need padding, and how that padding is formatted.
Each ciphertext block passes through AES block decrypt to produce an intermediate value, which is XOR'd with the previous ciphertext block (or IV) to yield plaintext.
A block cipher like AES operates on fixed-size blocks — always exactly 16 bytes in, 16 bytes out. It's a permutation on 2¹²⁸ elements. If your plaintext is 13 bytes, AES has no idea what to do with it. You need to fill the remaining 3 bytes with something before encryption.
A stream cipher (or a block cipher in CTR/GCM mode acting as one) is different. It generates a keystream byte-by-byte and XORs it with plaintext of any length — no block boundary, no padding needed. The ciphertext is the same length as the plaintext.
PKCS#7 is simple: append N bytes, each with the value N. The receiver reads the last byte, checks the preceding N−1 bytes match, and strips them. If they don't match — padding error.
Note: even if the plaintext is already a multiple of 16, a full block of 0x10 (16 bytes of value 16) is appended. There is always padding — the receiver always validates it — and the oracle always exists.
A padding oracle attack exploits a server that leaks whether CBC-mode ciphertext has valid PKCS#7 padding after decryption. With only this 1-bit oracle, an attacker recovers the entire plaintext without the key.
For each ciphertext block Ci, the attacker manipulates the previous ciphertext block Ci−1 (or the IV for the first block). By sending modified (C'i−1, Ci) pairs and observing the oracle, each byte of the intermediate state Ii = AES⁻¹(K, Ci) is recovered right-to-left. Then Pi = Ii ⊕ Ci−1.
CBC forces the receiver to parse and validate a post-decryption format. That validation is the oracle. Stream-cipher modes avoid the problem entirely by not having padding in the first place.
Worst case: 256 × 16 × 3 = 12288 oracle queries for 3 blocks.