CBC Padding Oracle Attack: Byte-by-Byte Plaintext Recovery via PKCS#7 Error Responses

Why This Matters

The CBC padding oracle attack was first published by Serge Vaudenay in 2002 and subsequently operationalised against real TLS implementations in the POODLE (2014), BEAST (2011), and Lucky Thirteen (2013) attacks, which collectively affected every major HTTPS implementation in production. In web application contexts, the attack was demonstrated against ASP.NET ViewState encryption (MS10-070, 2010), JavaServer Faces, and numerous session token implementations, allowing unauthenticated attackers to decrypt arbitrary ciphertext values. The padding oracle is frequently described as the canonical example of why encryption without authentication — "encrypt-then-MAC" vs. "MAC-then-encrypt" — is dangerous, and it remains a live attack vector in any system that returns distinguishable error responses for invalid padding versus invalid content.

Core Concept

CBC (Cipher Block Chaining) mode decrypts each block as: Pᵢ = Dₖ(Cᵢ) XOR Cᵢ₋₁, where Dₖ is the AES block decrypt operation, Cᵢ is the current ciphertext block, and Cᵢ₋₁ is the preceding ciphertext block (or the IV for i=1). The intermediate value Dₖ(Cᵢ) — sometimes called I-block — is independent of the previous ciphertext block.

PKCS#7 padding specifies that if the plaintext is not a multiple of the block size, it is padded with n bytes each of value n. A block padded with 4 bytes looks like: ... || 0x04 0x04 0x04 0x04. Valid padding values are 0x01 through 0x10 (for 16-byte blocks). The decryption routine checks this padding and returns a padding error if the last bytes do not form a valid PKCS#7 sequence.

A padding oracle is any mechanism that reveals whether the decrypted padding is valid. This can be an explicit error message ("Padding Invalid"), an HTTP 500 vs. 200 response code difference, a timing difference in response latency, or any other side channel. The oracle provides a single bit of information per query: valid or invalid.

The attack exploits the XOR relationship in CBC decryption. To recover the last byte of block Pᵢ, the attacker modifies the last byte of Cᵢ₋₁ to a value C'ᵢ₋₁[-1] and queries the oracle. When the oracle returns "valid padding", the decryption of the modified block produces a last byte of 0x01 (1-byte valid PKCS#7 padding). This means: Dₖ(Cᵢ)[-1] XOR C'ᵢ₋₁[-1] = 0x01, so Dₖ(Cᵢ)[-1] = 0x01 XOR C'ᵢ₋₁[-1]. The original plaintext last byte is then: Pᵢ[-1] = Dₖ(Cᵢ)[-1] XOR Cᵢ₋₁[-1].

The attack then proceeds to the second-to-last byte by fixing the last byte of the modified block to produce 0x02 in decryption and repeating the scan. For a 16-byte block, 16 iterations recover all 16 bytes, each requiring at most 256 oracle queries. The total query count for a k-block ciphertext is at most 256 × 16 × k.

The cryptanalytic precondition is ciphertext-only plus a padding oracle: the attacker need not know the key, only the ability to submit modified ciphertexts and observe the valid/invalid padding response.

Technical Deep-Dive

def padding_oracle_attack(ciphertext: bytes, oracle, block_size: int = 16) -> bytes:
    """
    Recover plaintext from CBC ciphertext using a padding oracle.
    oracle(ct: bytes) -> bool: returns True if padding is valid.
    Ciphertext must include IV as first block_size bytes.
    """
    blocks = [ciphertext[i:i+block_size]
              for i in range(0, len(ciphertext), block_size)]
    # blocks[0] = IV, blocks[1..] = ciphertext blocks
    plaintext = b""

    for block_idx in range(1, len(blocks)):
        ct_block = blocks[block_idx]
        prev_block = bytearray(blocks[block_idx - 1])
        recovered_iblock = bytearray(block_size)  # Dk(Ci)

        for byte_pos in range(block_size - 1, -1, -1):
            pad_val = block_size - byte_pos  # target padding byte value
            # Set already-recovered bytes to produce target padding
            modified_prev = bytearray(prev_block)
            for k in range(byte_pos + 1, block_size):
                modified_prev[k] = recovered_iblock[k] ^ pad_val

            found = False
            for guess in range(256):
                modified_prev[byte_pos] = guess
                test_ct = bytes(modified_prev) + ct_block
                if oracle(test_ct):
                    # Confirm it's not a false positive from multi-byte padding
                    if byte_pos == block_size - 1:
                        # Verify by flipping byte_pos-1 if it exists
                        if byte_pos > 0:
                            alt = bytearray(modified_prev)
                            alt[byte_pos - 1] ^= 0x01
                            if not oracle(bytes(alt) + ct_block):
                                continue  # was 0x02 0x02 false positive
                    # I-block byte = guess XOR pad_val
                    recovered_iblock[byte_pos] = guess ^ pad_val
                    found = True
                    break
            if not found:
                raise ValueError(f"No valid padding found at block {block_idx}, byte {byte_pos}")

        # Recover plaintext: Pi = Dk(Ci) XOR C(i-1)
        pt_block = bytes(recovered_iblock[j] ^ prev_block[j] for j in range(block_size))
        plaintext += pt_block

    # Strip PKCS#7 padding from last block
    pad_byte = plaintext[-1]
    if 1 <= pad_byte <= block_size:
        plaintext = plaintext[:-pad_byte]
    return plaintext

Cryptanalysis Methodology

1. Identify the oracle signal — Probe the target by submitting ciphertexts with the last byte of the second-to-last block flipped to each of 256 values. Observe the response for each: HTTP status code, response body content, or response time. One value (the original) will produce no padding error; others will produce errors unless the modified byte happens to also produce valid padding.
2. Confirm the oracle is reliable — Submit the original unmodified ciphertext: it must return "valid". Submit a ciphertext with the last byte zeroed: it should return "invalid" in most cases. If the oracle is ambiguous (e.g., only timing), calibrate the timing threshold using baseline measurements.
3. Run padbuster or pwntools PaddingOracle — Use padbuster (command-line tool) for web-based oracles: padbuster <URL> <base64_ciphertext> 16 -encoding 0. For CTF challenges with a Python server, use the padding_oracle_attack() function above.
4. Recover block by block — For each ciphertext block (working from last to first), apply the byte-at-a-time recovery. Concatenate the decrypted blocks. The last block will contain PKCS#7 padding — strip it.
5. Handle IV-in-cookie scenarios — Some implementations transmit the IV alongside the ciphertext (commonly concatenated as IV || CT). The attacker controls the IV and can use the attack to modify plaintext values in the first decrypted block directly by XORing the desired change into the IV.
6. Adapt for timing oracles — If the response time is the signal (Lucky Thirteen style), measure a large sample of timings for each guess value and use the slowest response as the "valid padding" indicator, since PKCS#7 validation of a longer valid padding sequence requires more comparison operations.

Secure Implementation Note — Always use authenticated encryption: AES-GCM or ChaCha20-Poly1305. Verify the MAC before decrypting (encrypt-then-MAC or AEAD). A MAC verification failure must return a generic error with no information about whether the failure was due to padding versus content invalidity. Using AES-CBC with HMAC-SHA-256 in an encrypt-then-MAC construction eliminates the padding oracle by aborting before decryption when the MAC is invalid.

Common Cryptanalysis Errors

• Triggering false positives at the last byte of a block — When scanning byte_pos = 15 (the last byte), a guess that produces 0x02 will be valid if the second-to-last byte also happens to produce 0x02 after modification. Always confirm by flipping an adjacent byte and verifying the oracle now rejects it.
• Forgetting that the IV is block 0 — For the first ciphertext block, the "previous block" is the IV. If the IV is not transmitted with the ciphertext, recovering the first plaintext block's exact value is impossible, but blocks 2 onward are still fully recoverable.
• Using a too-short request rate — Web-based padding oracles may rate-limit or block IPs after many rapid requests. Add a small delay between oracle queries and rotate session identifiers if rate-limiting is detected.
• Stopping after recovering one block — The attack works independently on each block. It is common in CTF challenges for the flag to span multiple blocks. Always recover all blocks.
• Misidentifying the oracle signal — An application that returns 200 for both valid and invalid padding but with different response bodies can still be a valid oracle; check for any distinguishable difference in the response, not just the HTTP status code.
• Not handling variable-length padding in the last block — The last plaintext block may have 1 to 16 bytes of PKCS#7 padding. After recovery, read the last byte value and strip that many bytes; do not assume a fixed padding length.

NICE Framework Alignment

Further Reading

• Security Flaws Induced by CBC Padding — Serge Vaudenay, EUROCRYPT 2002, Springer LNCS 2332
• Lucky Thirteen: Breaking the TLS and DTLS Record Protocols — N.J. Al Fardan and K.G. Paterson, IEEE S&P 2013
• Practical Padding Oracle Attacks — Rizzo and Duong, USENIX WOOT 2010