When error messages decrypt your ciphertext

A padding oracle is any system that, when fed a ciphertext, reveals whether the decrypted plaintext has valid padding — via an error message, a timing difference, or a behavioral quirk. Astonishingly, this single yes/no bit of leakage is enough to decrypt the entire ciphertext without the key. Vaudenay (2002) showed this for CBC mode; it has broken countless real systems (the original SSL/TLS, ASP.NET, and more).

Recap: CBC and PKCS#7 padding

CBC decryption of block C_i is P_i = D_k(C_i) ⊕ C_i-1. Plaintext is padded to a block multiple with PKCS#7: if N bytes are needed, append N copies of the byte value N. So valid endings are 01, or 02 02, or 03 03 03, etc. The decryptor strips padding and complains if it is malformed — that complaint is the oracle.

Key relation.

Let I_i = D_k(C_i) be the intermediate (post-block-cipher, pre-XOR) value. Then P_i = I_i ⊕ C_i-1. The attacker controls C_i-1 entirely, so by changing it she changes P_i while I_i stays fixed.

The byte-by-byte attack

To decrypt target block C_i, the attacker submits a crafted (C', C_i) two-block ciphertext where C' is a chosen IV/preceding block she manipulates. She forges padding to learn I_i one byte at a time, from the last byte inward.

recovering the last byte of a block

Goal: find I[15], the last byte of I_i = D_k(C_i). Know: decrypted last byte = I[15] XOR C'[15]. We want decrypted last byte = 0x01 (valid 1-byte padding). for guess g = 0 .. 255: set C'[15] = g, random elsewhere submit (C', C_i) to oracle if oracle says PADDING VALID: // decrypted last byte is 0x01 I[15] = g XOR 0x01 break now I[15] is known; true plaintext P[15] = I[15] XOR Creal[15] (guard against the rare 0x02 0x02 false hit by varying C'[14])

Having I[15], move to byte 14. Now force the last byte to decrypt to 02 by setting C'[15] = I[15] ⊕ 0x02, then brute-force C'[14] until the oracle accepts — valid padding now means the last two plaintext bytes are 02 02, revealing I[14] = C'[14] ⊕ 0x02. Continue inward.

generalizing to byte position j (target pad value P = 16-j)

// already know I[j+1..15] P = 16 - j // desired padding byte value for t = j+1 .. 15: C'[t] = I[t] XOR P // fix known bytes to read as P for guess g = 0 .. 255: C'[j] = g if oracle(C', C_i) == VALID: I[j] = g XOR P break cost: at most 256 queries per byte, 16 bytes -> ~4096 queries/block

Insight.

The whole 128-bit block falls in at most 16×256 = 4096 oracle queries, regardless of key strength. The attack is linear in block size — the cipher’s mathematical security is irrelevant once the padding bit leaks.

Bleichenbacher’s attack: a padding oracle for RSA

Bleichenbacher (1998) found the analogous oracle for RSA PKCS#1 v1.5 encryption. A PKCS#1 v1.5 block is 00 02 [≥8 random nonzero bytes] 00 [message]. A server that decrypts c and reveals whether the result starts with 00 02 (“PKCS conforming”) is an oracle. RSA’s multiplicative homomorphism makes it exploitable: if c = m^e mod n, then (c · s^e) mod n decrypts to (m · s) mod n for any chosen s.

Bleichenbacher interval narrowing

conforming means 2B ≤ m < 3B, where B = 2^{8(blocklen-2)} repeat: search for multiplier s such that (c · s^e) mod n is PKCS-conforming (oracle says yes) each yes gives: 2B ≤ (m·s mod n) < 3B i.e. 2B + r·n ≤ m·s < 3B + r·n for some integer r => m lies in [ (2B + r·n)/s , (3B + r·n)/s ) intersect this with the current set of candidate intervals intervals shrink each round; converge to a single m ~10^5 to 10^6 oracle queries for 1024-bit RSA (the “Million Message Attack”)

Each conforming s confines m·s mod n to [2B, 3B), which (lifting modular wraps) pins m into a union of narrowing real intervals. Iterating drives the intervals to a single integer — the plaintext (often a TLS pre-master secret). Variants (DROWN, ROBOT) revived this against modern TLS stacks decades later.

Defenses.

Encrypt-then-MAC and AEAD: verify a MAC over the ciphertext before any decryption/padding check, so malformed ciphertexts are rejected without revealing padding. Always prefer authenticated encryption (AES-GCM, ChaCha20-Poly1305).
Uniform errors and constant time: never distinguish “bad padding” from “bad MAC”; make the rejection path identical in message and timing.
For RSA: abandon PKCS#1 v1.5 encryption for OAEP, which is provably IND-CCA2; and on detecting non-conforming RSA, proceed with a random secret rather than aborting visibly (the TLS countermeasure).

▸Exercise

Decrypt a CBC block via the oracle, then explain Bleichenbacher.

Given I_i = D_k(C_i) is fixed and P_i = I_i ⊕ C_i-1, derive the formula for the last byte and show how forcing valid 01 padding yields I[15].
Show how to set C'[15] to read as 02 and brute-force C'[14] to obtain I[14]; generalize to byte j.
Count total oracle queries to recover one 16-byte block.
Explain why (c·s^e) mod n decrypts to (m·s) mod n, and how a “00 02” oracle narrows the interval containing m.