Padding Oracle Attack: Decrypting CBC Ciphertext Byte-by-Byte

What It Is and the Problem It Exposes

CBC mode encrypts each plaintext block by XORing it with the previous ciphertext block before applying the block cipher. Because block ciphers only handle fixed-size blocks (16 bytes for AES), the final block is topped up with PKCS#7 padding: if k bytes are missing, each padding byte holds the value k. So a message needing 3 pad bytes ends in 03 03 03; a full extra block of padding is 16 16 ... 16 (0x10 sixteen times).

On decryption, the receiver strips and validates this padding. A naive implementation returns a different, observable response when padding is malformed (an exception, a 500 error, a slower code path) versus when it is well-formed but the inner message is garbage. That distinguishable response is the oracle. Vaudenay's 2002 insight was that this single bit — "padding OK?" — is a decryption oracle in disguise. The attacker never breaks AES; they weaponize the receiver's own decryption routine as a machine that leaks plaintext, exploiting the gap between confidentiality and integrity.

How It Works, Step by Step

CBC decryption computes P_i = D_K(C_i) XOR C_{i-1}. Call the cipher's raw output the intermediate state I_i = D_K(C_i). The attacker's goal is to recover I_i, because once known, P_i = I_i XOR C_{i-1} falls out for free with the real previous block.

To attack a target block C_i, the attacker prepends a fully controlled block C' and submits C' || C_i. The decrypted last byte is I_i[15] XOR C'[15]. The attacker tries all 256 values of C'[15] until the oracle says "valid padding" — which almost always means the last byte decrypted to 0x01:

find last byte:
  for g in 0..255:
    C'[15] = g
    if oracle(C' || C_i) == VALID:
      I_i[15] = g XOR 0x01   # decrypted byte was 0x01

find byte j (moving left), targeting pad value p = 16 - j:
  fix all known bytes so they decrypt to p:
    C'[k] = I_i[k] XOR p   for k > j
  for g in 0..255:
    C'[j] = g
    if oracle(C' || C_i) == VALID:
      I_i[j] = g XOR p

Each solved byte lets you force the tail to any padding value, so you march right-to-left across all 16 bytes. One edge case: for the last byte, a "valid" hit could be a coincidental 0x02 0x02; disambiguate by tweaking C'[14] and re-checking.

Complexity and a Worked Byte Trace

Per byte, the attacker tries values 0..255, so at most 256 oracle queries, 128 on average. A block of b bytes costs O(256 · b) queries; an n-block message costs O(256 · b · n) — linear in message length, independent of key size. For a 16-byte AES block that is ≈4,096 queries worst case (~2,048 average). Space is O(1): you store only the running intermediate state.

Worked trace on the final byte of a block, assuming the true intermediate byte is I[15] = 0x3C:

C'[15]=0x00 -> decrypts to 0x3C  -> INVALID
C'[15]=0x01 -> 0x3D             -> INVALID
...
C'[15]=0x3D -> 0x3C XOR 0x3D = 0x01 -> VALID  ✓
=> I[15] = 0x3D XOR 0x01 = 0x3C
=> P[15] = I[15] XOR realC_{i-1}[15]

To attack byte 14 next, set C'[15] = I[15] XOR 0x02 = 0x3E (forcing the last byte to 0x02), then sweep C'[14] until the oracle accepts 0x02 0x02. The attack is embarrassingly parallel across blocks, so recovering an n-block ciphertext parallelizes to the per-block latency.

Where It Bites in Real Systems

Padding oracles are not academic — they have broken production systems at scale:

• ASP.NET (2010, MS10-070): the framework returned distinguishable errors for bad padding vs. bad MAC on encrypted ViewState and WebResource.axd, letting attackers decrypt and forge; it enabled reading web.config and full site compromise.
• Ruby on Rails, JavaServer Faces, and Steam's early login shipped exploitable CBC encryption of session/state tokens.
• OpenSSL, GnuTLS, and NSS all had CBC ciphersuite issues; Lucky Thirteen (2013) turned the MAC-verification timing difference in TLS's MAC-then-Encrypt construction into an oracle even after error messages were unified.
• POODLE (2014) exploited SSL 3.0's underspecified CBC padding, combined with a protocol downgrade, to steal HTTPS cookies at 256 requests per byte.

The common thread: whenever ciphertext integrity is checked after — or leaks through — the padding/decryption step, the oracle reappears, whether as an error code, a timing gap, or a length side channel.

Comparison to the Alternatives and the Real Fix

The padding oracle attack is a specific case of a broader lesson: unauthenticated encryption is not secure against active attackers. Its cousins illuminate the tradeoffs:

• vs. Bleichenbacher (1998): same idea on RSA PKCS#1 v1.5 — a conformance oracle — but far costlier (~10^6 queries) because RSA's structure leaks less per query than CBC's clean XOR relationship.
• vs. Lucky Thirteen: same padding-oracle root cause, but the signal is a sub-microsecond timing difference, requiring statistical averaging over ~2^23 queries per byte instead of a clean error bit.
• vs. BEAST: also CBC, but exploits predictable IVs / chosen-plaintext rather than padding validity.

The correct defense is authenticated encryption (AEAD): AES-GCM or ChaCha20-Poly1305, or, for CBC specifically, Encrypt-then-MAC — verify the MAC over the ciphertext before touching decryption or padding, and reject on MAC failure with a constant-time, indistinguishable response. TLS 1.3 removed CBC ciphersuites entirely.

Pitfalls, Failure Modes, and Why It Still Matters

The attack's power comes from three requirements, and mitigations target each:

• Distinguishability: if "bad padding" and "bad MAC" produce byte-identical, constant-time responses, the oracle collapses. Naive fixes fail because timing and error length are also oracles — Lucky Thirteen defeated systems that had merely unified their error messages.
• Malleability: CBC lets an attacker flip specific plaintext bits by editing the prior ciphertext block. A MAC over the ciphertext removes malleability entirely.
• Decrypt-before-authenticate: MAC-then-Encrypt and Encrypt-and-MAC both decrypt first, exposing the padding step. Only Encrypt-then-MAC / AEAD authenticate first.

Common implementation traps: writing your own "constant-time" MAC check that branches on length; using CBC with a random IV but still returning verbose parser errors; and rolling custom cookie/token encryption with CBC. The lasting significance is architectural — padding oracles are the canonical proof that confidentiality without integrity is broken, and they drove the entire industry toward AEAD as the default primitive.

Padding oracle attack vs. related chosen-ciphertext and side-channel attacks on CBC/RSA

Attack	Target	Oracle signal	Cost to decrypt	Year / Author
Vaudenay padding oracle	CBC + PKCS#7	Padding valid/invalid (error)	~128 queries/byte	2002 / Vaudenay
Lucky Thirteen	MEE-TLS-CBC (MAC-then-Encrypt)	MAC-check timing difference	~2^23 queries/byte (statistical)	2013 / AlFardan-Paterson
POODLE	SSL 3.0 CBC	MAC valid after downgrade	256 requests/byte	2014 / Möller-Duong-Kotowicz
Bleichenbacher	RSA PKCS#1 v1.5	PKCS#1 conformance	~10^6 queries/message	1998 / Bleichenbacher