Padding oracle attack

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In cryptography, a padding oracle attack is an attack which is performed on the padding of a cryptographic message. The plain text message often has to be padded (expanded) to be compatible with the underlying cryptographic primitive. Leakage of information about the padding may occur mainly during decryption of the ciphertext. Padding oracle attacks are mostly associated with ECB or CBC mode decryption used within block ciphers. Padding modes for asymmetric algorithms such as OAEP may also be vulnerable to padding oracle attacks.[1]

Symmetric cryptography[edit]

In symmetric cryptography, the padding oracle attack can be applied to the CBC mode of operation, where the "oracle" (usually a server) leaks data about whether the padding of an encrypted message is correct or not. Such data can allow attackers to decrypt (and sometimes encrypt) messages through the oracle using the oracle's key, without knowing the encryption key.

Example of the attack on CBC encryption[edit]

Suppose the attacker has three ciphertext blocks C_1, C_2, C_3 and he wants to decrypt the second block (get plaintext P_2). He only knows that the very last block C_3 is padded correctly and the padding method is PKCS7, which means that the last block is padded with n bytes each equals to n (for example: six bytes, each byte = 0x06).

CBC decryption works as follows: P_i = D_K(C_i) \oplus C_{i-1}, C_0 = IV. If the attacker changes the last byte of C_1 and sends (IV,C_1,C_2) to the server, it will affects the whole block P_1 (because of decryption avalanche effect) and the last byte of P_2 (because of XORing operation). Then the server checks the padding of the last decrypted block (which is P_2), and return the result: if the padding correct or not (this check is performed before the actual processing of the plaintext message).

Let b_{-1} be the last byte of C_1. The attacker changes it as follows: b_{-1} = b_{-1} \oplus z_{-1} \oplus \text{0x01}, where z_{-1} is the guessed value of the last byte of P_2. If z_{-1} were a shrewd guess (the exact value of P_2's last byte) the server will not raise the padding error (because the last byte of P_2 becomes equal 0x01, which is correct padding). In other case the sever will return the padding error code and the attacker will try the next value of z_{-1}. In the worst case he needs to make 255 attempts to find the right value of z_{-1}.

After he knows the last byte of P_2, he continues to obtain the last but one byte of P_2. He changes the last two bytes of C_1: b_{-1} = b_{-1} \oplus z_{-1} \oplus \text{0x02} and b_{-2} = b_{-2} \oplus z_{-2} \oplus \text{0x02}. Now he tries to find the value z_{-2}, which results in correct padding (0x02,0x02). After no more than 255 guesses he will get it and proceed to z_{-3} and so on.

If any block consists of 128 bits (AES, for example), which is 16 bytes, the attacker will obtain plaintext P_2 in no more than 255⋅16 = 4080 attempts. This attack costs literally nothing and can be performed in a few seconds (depends on the server's speed).

Attacks using padding oracles[edit]

The original attack was published in 2002 by Serge Vaudenay.[2] In 2010 the attack was applied to several web application frameworks, including JavaServer Faces, Ruby on Rails[3] and ASP.NET.[4][5][6] In 2012 it was shown to be effective against some hardened security devices.[7]

While these earlier attacks were fixed by most TLS implementors following its public announcement, a new variant, the Lucky Thirteen attack, published in 2013, used a timing side-channel to re-open the vulnerability even in implementations that had previously been fixed. As of February 2013, TLS implementors are still working on developing fixes for their TLS code.

POODLE is the recent (as of 2014) padding oracle attack on SSL 3.0 and TLS.

Solution[edit]

To prevent this attack, one could append an HMAC (Hash-based message authentication code) to the ciphertext. Without the key used to generate the HMAC, an attacker won't be able to produce valid ciphertexts. Since the HMAC is checked before the decryption stage, the attacker cannot do the required bit-fiddling and hence cannot discover the plaintext.

References[edit]

  1. ^ Manger, James. "A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0". Telstra Research Laboratories. 
  2. ^ Serge Vaudenay (2002). Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS... EUROCRYPT 2002. 
  3. ^ Juliano Rizzo, Thai Duong (2010-05-25). Practical Padding Oracle Attacks. USENIX WOOT 2010. 
  4. ^ Thai Duong, Juliano Rizzo (2011). Cryptography in the Web: The Case of Cryptographic Design Flaws in ASP.NET. IEEE Symposium on Security and Privacy 2011. 
  5. ^ Dennis Fisher (2010-09-13). "'Padding Oracle' Crypto Attack Affects Millions of ASP.NET Apps". Threat Post. 
  6. ^ Vlad Azarkhin (2010-09-19). "“Padding Oracle” ASP.NET Vulnerability Explanation". 
  7. ^ Romain Bardou, Riccardo Focardi, Yusuke Kawamoto, Lorenzo Simionato, Graham Steel, Joe-Kai Tsay (2012), "Efficient Padding Oracle Attacks on Cryptographic Hardware"