How a Padding Check Becomes a Decryption Oracle

A ciphertext under CBC that decrypts to a plaintext with invalid padding is a malformed message. The receiver has to notice and reject it, and the act of rejecting is unavoidable: the padding has to be checked before the plaintext can be returned, and the check either passes or fails. What makes this dangerous is not the rejection but the assumption that an attacker cannot tell a padding failure from any other failure. In a large class of real deployments the attacker can tell, one bit at a time, and that bit is enough to decrypt the whole message without the key.

The attack needs no weakness in AES. It needs an attacker who can submit chosen ciphertexts and observe whether each was accepted, and a receiver that distinguishes padding validity from other errors — by a status code, a timing difference, a different alert, a connection teardown versus a protocol error. Both conditions are common in the history of deployed protocols.

The padding rule and the check it forces

CMS, and TLS before version 1.3, use a padding rule in which the final byte $b$ gives the number of padding bytes, which is between 1 and 16, and the last $b$ bytes are all equal to $b$. If the plaintext is already block-aligned, a full block of value $16$ is appended. Unpadding reads the last byte, checks it is in range, then checks that the preceding $b-1$ bytes match it.

The rule is self-describing, which is what makes the check meaningful: a random 16-byte block satisfies it with probability

$$\frac{1}{16}\sum_{b=1}^{16} \left(\frac{1}{256}\right)^{b-1} \approx \frac{1}{16} + \frac{1}{4096} + \dots \approx 0.0656$$

so roughly one in sixteen wrong guesses produces a block that unpads successfully. That probability is the signal-to-noise ratio of the entire attack: a valid-padding response is sixteen times more likely for a correct guess than for a wrong one, and repeating the query distinguishes them.

The arithmetic of one byte

Decryption of the last block is $P_n = D_K(C_n) \oplus C_{n-1}$. The attacker controls $C_{n-1}$ and observes whether the result passes the padding check. Write $I = D_K(C_n)$ for the intermediate value, which the attacker does not know and which is fixed as long as $C_n$ is fixed. Then $P_n = I \oplus C_{n-1}$.

Suppose the attacker wants the final byte of the plaintext, $P_n[16]$. It modifies $C_{n-1}[16]$ to a guess $g$ and submits $(C_{n-1}’, C_n)$. The resulting last byte is $I[16] \oplus g$. The block unpads successfully when that byte is $1$, because a padding length of 1 requires exactly one padding byte. So the attacker tries $g = 0, 1, \dots$ until the receiver accepts, at which point $I[16] = g \oplus 1$ and the true plaintext byte is $P_n[16] = I[16] \oplus C_{n-1}[16]$.

The false-positive rate complicates this: a guess that produces $2$ in the last byte and a matching second byte also passes. The standard remedy is to fix the last byte at the already-known value and vary the second-to-last, testing for padding length 2, which requires $I[16] \oplus g_{16} = 2$ and $I[15] \oplus g_{15} = 2$. Each subsequent byte costs at most 256 submissions and typically about 128, so recovering a 16-byte block costs on the order of $16 \times 128$ queries, and the attack can be extended to earlier blocks by using the recovered plaintext of block $n$ as the crafted $C_{n-1}$ for block $n-1$.

# Structure of the last-byte step, not a complete attack.
# c_prev, c_last are 16-byte blocks; oracle returns True iff padding is valid.
def recover_last_byte(c_prev, c_last, oracle):
    for g in range(256):
        trial = bytearray(c_prev)
        trial[15] = g                      # mask byte 16 with guess g
        if oracle(bytes(trial), c_last):
            intermediate = g ^ 0x01        # valid length-1 padding => last byte == 1
            return intermediate ^ c_prev[15]
    raise ValueError("no candidate")

Why constant-time unpadding does not help

The natural first response is to write the padding check in constant time, so that no timing difference distinguishes a valid from an invalid pad. This is necessary and insufficient, and understanding why is the crux of the topic.

A constant-time unpadding routine makes the computation uniform, but the receiver still has to do something different in the two cases: return the plaintext or discard it. If the caller learns which branch was taken — a boolean, an exception, an HTTP 500 versus an HTTP 200, a connection reset, a length field that differs — the timing work bought nothing. The oracle is the observable outcome, not the internal timing.

This is why fixes for CBC padding oracles in deployed protocols have historically been layered. TLS 1.0’s defence was to compute the MAC over the record, and to treat a padding failure and a MAC failure identically: run the MAC verification regardless, and return the same alert for both. That removes the distinguishable bit, provided every other path — decompression, length checks, the ordering of checks — is equally uniform. Implementations that checked padding first and returned early reintroduced the oracle. TLS 1.3 removed the issue by removing CBC from the cipher suites entirely.

Where the oracle hides in composition

The most instructive case is MAC-then-encrypt, the construction in which a sender computes a MAC over the plaintext, appends it, and encrypts the concatenation. The receiver decrypts, unpads, splits off the MAC, and verifies.

The receiver cannot verify the MAC before decrypting, so it must decrypt attacker-chosen ciphertext before it has any authentication. Every malformed message is therefore processed by the CBC decryption path, and the padding check happens on data the attacker supplied. The MAC is checked afterwards and always fails for the attacker’s forgeries, but it fails after the padding information has been generated. The padding oracle is fully available even though the construction has a MAC.

The reverse order, encrypt-then-MAC, computes the tag over the ciphertext and checks it before any decryption. A forged ciphertext is rejected without the block cipher ever running, so there is no padding check on attacker data. Krawczyk’s analysis of the three orderings made this the standard recommendation, and it is why the transition to AEAD modes — where the tag is computed over the ciphertext by construction — also removes the class of attack rather than patching instances of it.

There is a further reason the padding oracle resists local fixes: it is an instance of a general pattern in which a receiver’s error handling leaks information about secret intermediate state. Any check performed on decrypted-but-unauthenticated data, whose outcome reaches the attacker, is a candidate oracle. Length checks that reveal the true plaintext length after decryption, decompression of unauthenticated data, and character-set validation errors are all in the same family. The structural answer is the one taken by AEAD: nothing derived from the plaintext is revealed until the tag verifies, and the tag covers the ciphertext, so the receiver’s decision depends only on public data and the key.

What it costs to be wrong

The attack is not theoretical in the sense of requiring unusual access. It requires the ability to submit ciphertexts and observe acceptance, which any network protocol endpoint offers, and it recovers plaintext at a rate of a few hundred queries per block. A 1 KB message is 64 blocks; the recovery is a bounded, mechanical process with no search over keys.

Two design lessons follow. The first is that authenticated encryption is not an optimisation but the removal of an entire attack surface, and modes that authenticate ciphertext — GCM, CCM, and the misuse-resistant constructions covered in SIV and deterministic authenticated encryption — are preferred for exactly this reason. The second is that “encrypt then check” orderings matter as much as the primitives: a protocol that authenticates after decrypting inherits the oracle regardless of which cipher it names. The earlier article on chaining modes and IV requirements describes the error-propagation behaviour that makes a single modified ciphertext block produce a fully corrupted plaintext block plus one predictable bit — the property the attacker exploits here.

A padding check is a comparison between a decrypted block and a rule. Once an attacker can see the result of that comparison, the block is no longer secret; it is a value being searched for through a channel that answers yes or no.