DSP Explorables

Padding oracles

CBC mode with AES keeps a message’s contents hidden: nobody without the key can read it. But a server that receives CBC messages has to decrypt them, and decide what to do when one doesn’t make sense. If it tells the sender why it didn’t, by a different error message, or even a different response time, it can give away the whole message, one byte at a time, without the key and without AES being broken at all.

This is a chosen-ciphertext attack, the strongest kind of attacker on What we want from cryptography: Mallory sends the server ciphertexts of their own making, and watches what it says.

1 · A server that says too much

CBC encrypts whole 16-byte blocks, so a message is first filled out with padding (the modes page has the details). The usual rule, PKCS#7, adds n bytes, each of value n: one byte of 01, two of 02 02, three of 03 03 03, and so on, up to a whole block of 16 bytes of 10 (hex for 16). After decrypting, the receiver reads the last byte, checks that that many bytes all hold that value, and strips them.

A message cut into blocks and padded (padding shaded). Below it, the receiver’s check on its own: type the last few bytes of a decrypted message, in hex, and see whether they’re good padding. 01 on its end is always good; 02 01 is good too (one byte of padding, 01); 03 02 isn’t; 00 never is.

Imagine a web server that keeps a user’s session in a cookie encrypted with CBC: the browser sends it back with every request, and the server decrypts it to see who’s asking. Sent a cookie that’s been tampered with, the server can fail in two different ways:

the padding is wrong: it replies bad padding;
the padding is fine, but what’s left doesn’t make sense: it replies bad request (and if it does make sense, OK).

That difference is one bit of information about the decrypted message: was its padding good? A machine that answers such a question is called an oracle, and this one is a padding oracle.

The server, with a real encrypted cookie (an IV and three blocks, as Mallory sees them). Change a byte, as Mallory can, and see the server’s reply. The server always decrypts; it only differs in what it says. Changing block 2’s last byte usually breaks the padding (which lives in block 3, the block after it). Changing the IV’s first byte gives “bad request”: the cookie no longer starts as the server expects, but the padding is fine. Tick the box to see what the server decrypted (Mallory can’t).

2 · One byte

Recall how CBC decrypts. AES decrypts a ciphertext block to a value, call it D, and then D is XORed with the previous ciphertext block to give the plaintext:

P_2 = D_2 \oplus C_1

Mallory can’t change D (that would need the key), but can change C₁ freely, and the server will XOR whatever C₁ it’s sent into the result. So Mallory sends a doctored block, C₁′, in front of the real C₂, and the server works out

P_2' = D_2 \oplus C_1'

and checks its padding. Mallory has no idea what P₂′ is, except at one moment: when the server says the padding is good, P₂′ almost certainly ends in a single 01. Mallory tries every value of C₁′‘s last byte, 00, 01, 02 … until that happens. Then, for that last byte:

D_2[16] \oplus C_1'[16] = 01 \quad\Rightarrow\quad D_2[16] = C_1'[16] \oplus 01

Mallory now knows a byte of D₂, which the key was supposed to protect. And the real message’s byte is that XORed with the real C₁’s last byte, which Mallory has: $P_2[16] = D_2[16] \oplus C_1[16]$ .

Finding the last byte of block 2 of the cookie. Mallory changes only the last byte of block 1 and sends it with the real block 2. Each square is one possible value of that byte, 00 to FF (grey: tried, bad padding; orange: good). When the server says good, the working below gives the byte. At most 256 questions; on average about 128.

“Almost certainly 01” has one exception. If the real plaintext happens to have 02 just before the last byte, then a last byte of 02 also gives good padding (02 02). To tell the two apart, Mallory changes the second-to-last byte of C₁′ as well and asks again: a lone 01 doesn’t care what comes before it; 02 02 is broken by the change. (Pale yellow squares in the grid are guesses that were fooled this way; they’re rare in the middle of a message, but always happen on a block that really ends in 02 02.)

3 · Every byte, every block

With the last byte known, Mallory moves on to the one before. Now the target is padding of two bytes, 02 02: Mallory sets C₁′‘s last byte so that the server’s result ends in 02 (it’s D₂[16] ⊕ 02, now that D₂[16] is known), and tries every value of the second-to-last byte until the padding is good again. Then 03 03 03 for the third, and so on, back to the first byte of the block, 16 bytes of 10.

Each block is attacked with the block before it as the one to doctor. For the first block, that’s the IV, which is sent with the message. So every block falls, the padding at the end included.

The whole attack on the cookie, against the server in the page, which holds the key. Watch it find each block’s bytes from the end, the orange byte being the current guess. It needs only the server’s two kinds of reply. At most 256 questions a byte, plus a check at each block’s last byte; about 128 on average. Then tick the server checks a MAC first and attack again (section 5).

The tests run the attack on 40 random messages of two blocks and count: the average is between 120 and 137 questions a byte (in theory 128.5, since the right value is equally likely to be any of the 256, and Mallory tries them in order). For the cookie’s 48 bytes, that’s around 6,000 questions: nothing, for a computer sending requests to a server.

Nothing here is a weakness of AES. The server does all the decrypting; Mallory only reads the server’s answers. Any block cipher in CBC mode, behind a server that answers like this, gives the same result.

4 · It happened, more than once

2002: Serge Vaudenay published the attack, against CBC padding in protocols including SSL and IPsec.
2010: Juliano Rizzo and Thai Duong showed it working against real web frameworks. In ASP.NET, Microsoft’s web framework, it decrypted and forged the encrypted data that websites trusted, and Microsoft issued an emergency fix.
2013: Lucky Thirteen. TLS, the protocol behind secure websites, had already learned to send the same error for bad padding as for a bad message. Nadhem AlFardan and Kenneth Paterson showed that the server still took a little longer in one case than the other: timing became the oracle.
2014: POODLE. Bodo Möller, Thai Duong and Krzysztof Kotowicz showed that SSL 3.0, the older protocol browsers could still be pushed into using, checked even less of its padding, making the attack easy. SSL 3.0 was switched off almost everywhere soon after.

Each time, the fix was to make the server’s behaviour the same for every kind of failure, and each time it turned out that a little difference had been left. Hiding a leak is hard; the real fix removes it.

5 · The fix: don’t decrypt what you haven’t checked

The attack works because the server decrypts messages it has no reason to trust. If it first checks a MAC, a check value that only someone with the key can make (see MACs and authenticated encryption), computed over the IV and the ciphertext, then any change Mallory makes is caught before decryption starts. Every doctored message gets the same answer, at the same speed, and the padding is never looked at.

That’s encrypt-then-MAC: encrypt, then compute the MAC over the ciphertext; on receipt, check the MAC first. The order matters. TLS used to MAC the plaintext and then encrypt (MAC-then-encrypt), which forces the receiver to decrypt, and look at the padding, before it can check anything: the root of Lucky Thirteen and POODLE. Modern protocols use authenticated encryption, which does both jobs in one, so a forged message is rejected before any of it is used. The last figure’s checkbox shows the difference: with the MAC checked first, 256 guesses at the first byte all get the same reply, and the attack stops there.

Summary