Padding oracle

The padding oracle is one of the most elegant yet most practical crypto attacks: it lets you decrypt (and often encrypt) data protected with CBC without knowing the key, by abusing the fact that the system reveals whether the padding is valid. It shows up in cookies, tokens, encrypted parameters, and APIs.

The context: CBC and PKCS#7

CBC decrypts: P_i = D(C_i) XOR C_{i-1}      (C_0 = IV)
PKCS#7 padding: pads the last block with N bytes of value N (e.g. 04 04 04 04)
On decryption the padding is validated -> if wrong, PADDING ERROR

The flaw: if the server responds differently to “invalid padding” vs “valid padding but bad data” (different HTTP error, message, or even timing), you have an oracle.

How the attack decrypts (concept)

Goal: recover P2 = D(C2) XOR C1, without the key.
You manipulate C1 byte by byte (C1') and observe the oracle over [C1' | C2]:
  - adjusting the last byte of C1' until the padding is VALID (0x01),
    you deduce D(C2)[last] = C1'[last] XOR 0x01
  - knowing D(C2)[last], force padding 0x02 0x02 and repeat for the second-to-last byte
  - ... until all 16 bytes of D(C2) are recovered -> then P2 = D(C2) XOR C1 (the real C1)
Result: decrypt the WHOLE message block by block. Max 256 tries per byte.

To encrypt arbitrary text (forge a valid ciphertext) you use the same property in reverse, choosing the C_{i-1} blocks that yield the desired plaintext.

Practical exploitation

# padbuster: automates the attack against a web endpoint
padbuster http://host/x?data=<C> <C_in_base64> 16 -encoding 0 -cookies 'sess=...'
# python-paddingoracle to build it custom when the oracle is non-standard
# key: define the oracle(ciphertext)->bool (padding ok?) function correctly

Signs of an oracle: a parameter/cookie that is clearly a ciphertext (multiple of 16 bytes in base64/hex) and distinguishable responses when you corrupt it.

Variant: Padding Oracle in RSA (Bleichenbacher / ROBOT)

The same principle applies to RSA with PKCS#1 v1.5 padding: a “valid padding” oracle lets you decrypt or sign. Revived as ROBOT (2017) at major sites (see PKI & certificates/TLS).

Tools

padbuster, python-paddingoracle, custom scripts in PyCryptodome.
Burp (to automate requests and distinguish responses), CyberChef (to verify blocks).

Defense

Authenticated encryption (AEAD): AES-GCM / ChaCha20-Poly1305 — there’s no padding to validate.
If using CBC, encrypt-then-MAC and verify the MAC before attempting to decrypt/validate padding.
Don’t distinguish errors: same response and timing for invalid padding and invalid data.
Don’t expose manipulable ciphertext to the client without integrity.

CVEs and real-world cases

Vaudenay (2002): original formulation of the CBC padding oracle.
Lucky Thirteen (2013): timing padding oracle in TLS CBC.
ROBOT (2017): Bleichenbacher (RSA padding oracle) at Facebook, PayPal, Cisco, F5, etc.
POODLE (2014): padding oracle over SSLv3 CBC.

Testing checklist

Locate parameters/cookies that are CBC ciphertext (multiple of 16)
Does the system distinguish “invalid padding” from “invalid data”? (error/timing)
Run padbuster / a script to decrypt block by block
Try ciphertext forgery (controlled encryption)
RSA PKCS#1v1.5: look for a Bleichenbacher/ROBOT-type oracle
Verify the defense: AEAD or encrypt-then-MAC + uniform responses