9.1: Padding Oracle A acks
- Page ID
- 7355
Imagine a webserver that receives CBC-encrypted ciphertexts for processing. When receiving a ciphertext, the webserver decrypts it under the appropriate key and then checks whether the plaintext has valid X.923 padding (Section \(8.4\)).
Importantly, suppose that the observable behavior of the webserver changes depending on whether the padding is valid. You can imagine that the webserver gives a special error message in the case of invalid padding. Or, even more cleverly (but still realistic), the difference in response time when processing a ciphertext with invalid padding is enough to allow the attack to work. \({ }^{1}\) The mechanism for learning padding validity is not important what is important is simply the fact that an attacker has some way to determine whether a ciphertext encodes a plaintext with valid padding. No matter how the attacker comes by this information, we say that the attacker has access to a padding oracle, which gives the same information as the following subroutine:
We call this a padding oracle because it answers only one specific kind of question about the input. In this case, the answer that it gives is always a single boolean value.
It does not seem like a padding oracle is leaking useful information, and that there is no cause for concern. Surprisingly, we can show that an attacker who doesn’t know the encryption key \(k\) can use a padding oracle alone to decrypt any ciphertext of its choice! This is true no matter what else the webserver does. As long as it leaks this one bit of information on ciphertexts that the attacker can choose, it might as well be leaking everything.
Malleability of CBC Encryption
Recall the definition of \(\mathrm{CBC}\) decryption. If the ciphertext is \(c=c_{0} \cdots c_{\ell}\) then the ith plaintext block is computed as: \[m_{i}:=F^{-1}\left(k, c_{i}\right) \oplus c_{i-1}\] From this we can deduce two important facts:
- Two consecutive blocks \(\left(c_{i-1}, c_{i}\right)\) taken in isolation are a valid encryption of \(m_{i}\). Looking ahead, this fact allows the attacker to focus on decrypting a single block at a time.
- xoring a ciphertext block with a known value (say, \(x\) ) has the effect of xoring the corresponding plaintext block by the same value. In other words, for all \(x\), the ciphertext \(\left(c_{i-1} \oplus x, c_{i}\right)\) decrypts to \(m_{i} \oplus x\) :\[\operatorname{Dec}\left(k,\left(c_{i-1} \oplus x, c_{i}\right)\right)=F^{-1}\left(k, c_{i}\right) \oplus\left(c_{i-1} \oplus x\right)=\left(F^{-1}\left(k, c_{i}\right) \oplus c_{i-1}\right) \oplus x=m_{i} \oplus x\]
If we send such a ciphertext \(\left(c_{i-1} \oplus x, c_{i}\right)\) to the padding oracle, we would therefore learn whether \(m_{i} \oplus x\) is a (single block) with valid padding. Instead of thinking in terms of padding, it might be best to think of the oracle as telling you whether \(m_{i} \oplus x\) ends in one of the suffixes \(01,0002,000003\), etc.
By carefully choosing different values \(x\) and asking questions of this form to the padding oracle, we will show how it is possible to learn all of \(m_{i}\). We summarize the capability so far with the following subroutine:
Given a ciphertext \(c\) that encrypts an unknown message \(m\), we can see that an adversary can generate another ciphertext whose contents are related to \(m\) in a predictable way. This property of an encryption scheme is called malleability.
Learning the Last Byte of a Block
We now show how to use the cHEcKXOR subroutine to determine the last byte of a plaintext block \(m\). There are two cases to consider, depending on the contents of \(m\). The attacker does not initially know which case holds:
For the first (and easier) of the two cases, suppose the second-to-last byte of \(m\) is nonzero. We will try every possible byte \(b\) and ask whether \(m \oplus b\) has valid padding. Since \(m\) is a block and \(b\) is a single byte, when we write \(m \oplus b\) we mean that \(b\) is extended on the left with zeroes. Since the second-to-last byte of \(m\) (and hence \(m \oplus b\) ) is nonzero, only one of these possibilities will have valid padding - the one in which \(m \oplus b\) ends in byte 01 . Therefore, if \(b\) is the candidate byte that succeeds (i.e., \(m \oplus b\) has valid padding) then the last byte of \(m\) must be \(b \oplus 01\).
Using LEARNLASTBYTE to learn the last byte of a plaintext block:
For the other case, suppose the second-to-last byte of \(m\) is zero. Then \(m \oplus b\) will have valid padding for several candidate values of \(b\):
Using LEARNLASTBYTE to learn the last byte of a plaintext block:
Whenever more than one candidate \(b\) value yields valid padding, we know that the second-to-last byte of \(m\) is zero (in fact, by counting the number of successful candidates, we can know exactly how many zeroes precede the last byte of \(m\) ).
If the second-to-last byte of \(m\) is zero, then the second-to-last byte of \(m \oplus 01 \quad b\) is nonzero. The only way for both strings \(m \oplus 01 \quad b\) and \(m \oplus b\) to have valid padding is when \(m \oplus b\) ends in byte 01 . We can re-try all of the successful candidate \(b\) values again, this time with an extra nonzero byte in front. There will be a unique candidate \(b\) that is successful in both rounds, and this will tell us that the last byte of \(m\) is \(b \oplus 01\).
The overall approach for learning the last byte of a plaintext block is summarized in the LEARNLASTBYTE subroutine in Figure 9.1. The set \(B\) contains the successful candidate bytes from the first round. There are at most 16 elements in \(B\) after the first round, since there are only 16 valid possibilities for the last byte of a properly padded block. In the worst case, LEARNLASTBYTE makes \(256+16=272\) calls to the padding oracle (via CHECKXOR).
Learning Other Bytes of a Block
Once we have learned one of the trailing bytes of a plaintext block, it is slightly easier to learn additional ones. Suppose we know the last 3 bytes of a plaintext block, as in the example below. We would like to use the padding oracle to discover the 4 th-to-last byte.
Using LEARNPREVBYTE to learn the 4th-to-last byte when the last 3 bytes of the block are already known.
Since we know the last 3 bytes of \(m\), we can calculate a string \(x\) such that \(m \oplus x\) ends in 000004 . Now we can try Xor’ing the 4 th-to-last byte of \(m \oplus x\) with different candidate bytes \(b\), and asking the padding oracle whether the result has valid padding. Valid padding only occurs when the result has 00 in its 4 th-to-last byte, and this happens exactly when the 4 th-to-last byte of \(m\) exactly matches our candidate byte \(b\).
The process is summarized in the LEARNPREVBYTE subroutine in Figure 9.1. In the worst case, this subroutine makes 256 queries to the padding oracle.
Putting it all together. We now have all the tools required to decrypt any ciphertext using only the padding oracle. The process is summarized below in the LEARNALL subroutine.
In the worst case, 256 queries to the padding oracle are required to learn each byte of the plaintext. \({ }^{2}\) However, in practice the number can be much lower. The example in this section was inspired by a real-life padding oracle attack \({ }^{3}\) which includes optimizations that allow an attacker to recover each plaintext byte with only 14 oracle queries on average.
\({ }^{1}\) For this reason, it is necessary to write the unpadding algorithm so that every execution path through the subroutine takes the same number of CPU cycles.
\({ }^{2}\) It might take more than 256 queries to learn the last byte. But whenever LEARNLASTBYTE uses more than 256 queries, the side effect is that you’ve also learned that some other bytes of the block are zero. This saves you from querying the padding oracle altogether to learn those bytes.
\({ }^{3}\) How to Break XML Encryption, Tibor Jager and Juraj Somorovsky. ACM CCS \(2011.\)