Padding oracle attack

The standard implementation of CBC decryption in block ciphers is to decrypt all ciphertext blocks, validate the padding, remove the PKCS7 padding, and return the message's plaintext. If the server returns an "invalid padding" error instead of a generic "decryption failed" error, the attacker can use the server as a padding oracle to decrypt (and sometimes encrypt) messages.

The mathematical formula for CBC decryption is

${\displaystyle P_{i}=D_{K}(C_{i})\oplus C_{i-1},}$

${\displaystyle C_{0}=IV.}$

As depicted above, CBC decryption XORs each plaintext block with the previous ciphertext block. As a result, a single-byte modification in block ${\displaystyle C_{1}}$ will make a corresponding change to a single byte in ${\displaystyle P_{2}}$.

Suppose the attacker has two ciphertext blocks ${\displaystyle C_{1},C_{2}}$ and they want to decrypt the second block to get plaintext ${\displaystyle P_{2}}$. The attacker changes the last byte of ${\displaystyle C_{1}}$ (creating ${\displaystyle C_{1}'}$) and sends ${\displaystyle (IV,C_{1}',C_{2})}$ to the server. The server then returns whether or not the padding of the last decrypted block (${\displaystyle P_{2}'}$) is correct (equal to 0x01). If the padding is correct, the attacker now knows that the last byte of ${\displaystyle D_{K}(C_{2})\oplus C_{1}'}$ is ${\displaystyle \mathrm {0x01} }$. Therefore, the last byte of ${\displaystyle D_{K}(C_{2})}$ equals ${\displaystyle C_{1}'\oplus \mathrm {0x01} }$. If the padding is incorrect, the attacker can change the last byte of ${\displaystyle C_{1}'}$ to the next possible value. At most, the attacker will need to make 256 attempts (one guess for every possible byte) to find the last byte of ${\displaystyle P_{2}}$. If the decrypted block contains padding information or bytes used for padding then an additional attempt will need to be made to resolve this ambiguity.[2]

After determining the last byte of ${\displaystyle P_{2}}$, the attacker can use the same technique to obtain the second-to-last byte of ${\displaystyle P_{2}}$. The attacker sets the last byte of ${\displaystyle P_{2}}$ to ${\displaystyle \mathrm {0x02} }$ by setting the last byte of ${\displaystyle C_{1}}$ to ${\displaystyle D_{K}(C_{2})\oplus \mathrm {0x02} }$. The attacker then uses the same approach described above, this time modifying the second-to-last byte until the padding is correct (0x02, 0x02).

If a block consists of 128 bits (AES, for example), which is 16 bytes, the attacker will obtain plaintext ${\displaystyle P_{2}}$ in no more than 255⋅16 = 4080 attempts. This is significantly faster than the ${\displaystyle 2^{128}}$ attempts required to bruteforce a 128-bit key.

CBC-R[3] turns a decryption oracle into an encryption oracle, and is primarily demonstrated against padding oracles.

Using padding oracle attack CBC-R can craft an initialization vector and ciphertext block for any plaintext:

• decrypt any ciphertext P_i = PODecrypt( C_i ) XOR C_i−1,
• select previous cipherblock C_x−1 freely,
• produce valid ciphertext/plaintext pair C_x-1 = P_x XOR PODecrypt( C_i ).

To generate a ciphertext that is N blocks long, attacker must perform N numbers of padding oracle attacks. These attacks are chained together so that proper plaintext is constructed in reverse order, from end of message (C_N) to beginning message (C₀, IV). In each step, padding oracle attack is used to construct the IV to the previous chosen ciphertext.

The CBC-R attack will not work against an encryption scheme that authenticates ciphertext (using a message authentication code or similar) before decrypting.