9.2: What Went Wrong?

Last updated
Save as PDF

Page ID: 7356

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

CBC encryption provides CPA security, so why didn’t it save us from padding oracle attacks? How was an attacker able to completely obliterate the privacy of encryption?

First, CBC encryption (in fact, every encryption scheme we’ve seen so far) has a property called malleability. Given an encryption \(c\) of an unknown plaintext \(m\), it is possible to generate another ciphertext \(c^{\prime}\) whose contents are related to \(m\) in a predictable way. In the case of CBC encryption, if ciphertext \(c_{0}\|\cdots\| c_{\ell}\) encrypts a plaintext \(m_{1}\|\cdots\| m_{\ell}\), then ciphertext \(\left(c_{i-1} \oplus x, c_{i}\right)\) encrypts the related plaintext \(m_{i} \oplus x\)
In short, if an encryption scheme is malleable, then it allows information contained in one ciphertext to be "transferred" to another ciphertext.

Second, you may have noticed that the CPA security definition makes no mention of the Dec algorithm. The Dec algorithm shows up in our definition for correctness, but it is nowhere to be found in the \(\mathcal{L}_{\text {cpa- } \star}\) libraries. Decryption has no impact on CPA security!
But the padding oracle setting involved the Dec algorithm - in particular, the adversary was allowed to see some information about the result of Dec applied to adversarially-chosen ciphertexts. Because of that, the CPA security definition does not capture the padding oracle attack scenario.

The bottom line is: give an attacker a malleable encryption scheme and access to any partial information related to decryption, and he/she can get information to leak out in surprising ways. As the padding-oracle attack demonstrates, even if only a single bit of information (i.e., the answer to a yes/no question about a plaintext) is leaked about the result of decryption, this is frequently enough to extract the entire plaintext.

If we want security even under the padding-oracle scenario, we need a better security definition and encryption schemes that achieve it. That’s what the rest of this chapter is about.

Discussion

Is this a realistic concern? You may wonder whether this whole situation is somewhat contrived just to give cryptographers harder problems to solve. That was probably a common attitude towards the security definitions introduced in this chapter. However, in 1998, Daniel Bleichenbacher demonstrated a devastating attack against early versions of the SSL protocol. By presenting millions of carefully crafted ciphertexts to a webserver, an attacker could eventually recover arbitrary SSL session keys.
In practice, it is hard to make the external behavior of a server not depend on the result of decryption. This makes CPA security rather fragile in the real world. In the case of padding oracle attacks, mistakes in implementation can lead to different error messages for invalid padding. In other cases, even an otherwise careful implementation can provide a padding oracle through a timing side-channel (if the server’s response time is different for valid/invalid padded plaintexts).

As we will see, it is in fact possible to provide security in these kinds of settings, and with low additional overhead. These days there is rarely a good excuse for using encryption which is only CPA-secure.
Padding is in the name of the attack. But padding is not the culprit. The culprit is using a (merely) CPA-secure encryption scheme while allowing some information to leak about the result of decryption. The exercises expand on this idea further.
If padding is added to only the last block of the plaintext, how can this attack recover the entire plaintext? This common confusion is another reason to not place so much blame on the padding scheme. A padding oracle has the following behavior: "give me an encryption of \(m_{1}\|\cdots\| m_{\ell}\) and I’ll tell you some information about \(m_{\ell}\) (whether it ends with a certain suffix)." Indeed, the padding oracle checks only the last block. However, CBC mode has the property that if you have an encryption of \(m_{1}\|\cdots\| m_{\ell}\), then you can easily construct a different ciphertext that encrypts \(m_{1}\|\cdots\| m_{\ell-1}\). If you send this ciphertext to the padding oracle, you will get information about \(m_{\ell-1}\). By modifying the ciphertext (via the malleability of CBC), you give different plaintext blocks the chance to be the "last block" that the padding oracle looks at.
The attack seems superficially like brute force, but it is not: The attack makes 256 queries per byte of plaintext, so it costs about \(256 \ell\) queries for a plaintext of \(\ell\) bytes. Brute-forcing the entire plaintext would cost \(256^{\ell}\) since that’s how many \(\ell\)-byte plaintexts there are. So the attack is exponentially better than brute force. The lesson is: brute-forcing small pieces at a time is much better then brute-forcing the entire thing.