Chosen-Ciphertext Attacks Against Encryption

Imagine you discover a bug in your company's flagship software product. It decrypts ciphertexts received from the network, but a bug causes a crash if the resulting plaintext includes a null character. Luckily, you are absolutely confident that no plaintext with a null character is ever encrypted. So you might conclude that this weird bug will never be triggered, and that the software will never crash in this way.

Depending on the choice of encryption scheme, you might be totally wrong! In some schemes, including all of the ones we've seen so far, an adversary can trigger the bug. What's worse, by observing which ciphertexts trigger the crash and which don't, the adversary can completely break the encryption scheme!

9.1. Format-oracle attacks and malleability

Let's formalize the important features of the scenario described above. The victim decrypts each ciphertext it receives. To keep things concrete, let's assume the victim uses CTR mode encryption (construction 8.5.4). The adversary learns whether the resulting plaintext contains a null character. It doesn't actually matter how the adversary learns this information: It could be due to a crash (e.g., a webserver giving http response code 500), an error message, or from the expected functionality of the software. All that matters is that the adversary can learn the answer to this single yes/no question about ciphertexts that it provides.

We can formalize the situation by imagining the adversary having access to the following library:

In this section we will write bytes/characters in hex like $\byte{00}$, $\byte{c8}$, etc. The null character is $\byte{00}$.

Why is this subroutine called $\subname{nulloracle}$? In colloquial language, an oracle is a mystic who answers questions on behalf of the gods, often in an enigmatic way. You might need to do a bit of work to decipher the mysterious answers you get from an oracle. In cryptography and other areas of computer science, an oracle is an algorithm that solves a very specific kind of problem, which you might be allowed to call on inputs of your choice but not “look inside.” You might use an oracle that solves one kind of problem to help solve a different one.

Our scenario provides the adversary with an oracle that answers a very specific question: Does the decryption of this ciphertext contain any null characters? We will show the surprising fact that if you can obtain answers to these kinds of questions, then you can completely decrypt any ciphertext of your choice!

9.1.1. CTR mode is malleable

To understand the null-oracle attack, we must first understand a curious property of CTR mode. Given a ciphertext $\ctxt = \ctxt_0 \| \ctxt_1 \| \cdots \| \ctxt_\ell$, the decryption algorithm computes the first output block $\ptxt_1$ as:

How does the output of $\Dec$ change if we flip some bits in $\ctxt_1$? Flipping certain bits is the same as xor'ing $\ctxt_1$ with a certain string $\Delta$ ($\Delta$ contains $\bit1$ in each position whose bit should flip). If we replace $\ctxt_1$ with $\ctxt_1 \oplus \Delta$, then the decryption algorithm computes its first output block as:

In other words, if we flip some bits in $\ctxt_1$, then the corresponding bits will flip in $\ptxt_1$. Of course, there is nothing special about the first block in CTR mode; the same is true for all ciphertext blocks, apart from the IV:

So, even without knowing what is inside a ciphertext, we can make predictable changes to its contents. We call this kind of property malleability:

CTR mode is malleable via xor in quite an extreme way. Given an encryption $\ctxt$ of an unknown plaintext $\ptxt$, it is possible to create a new ciphertext that decrypts to $\ptxt \oplus \Delta$, for any $\Delta$ of our choice.

9.1.2. The attack

So how does CTR mode's malleability lead to an attack that lets the adversary decrypt arbitrary ciphertexts? Suppose the adversary captures a ciphertext $\ctxt$ and wants to discover the unknown value $\ptxt = \Dec(\key,\ctxt)$.

Suppose the last byte of $\ptxt$ is $b$, so we can write $\ptxt$ as $\ptxt = \ptxt' \| b$. What will happen if the adversary sends the ciphertext $\ctxt \oplus (\cdots\bit{00}\|b)$ to the null-character oracle? Applying fact 9.1.2, we can deduce that this ciphertext decrypts to:

Since the modified ciphertext decrypts to a plaintext that contains a null byte, the oracle will respond with $\mytrue$.

The adversary probably doesn't know the last plaintext byte $b$ in advance. However, it can generate and send the following 255 ciphertexts to the null-oracle:

One of these ciphertexts will cause $\subname{nulloracle}$ to return $\mytrue$, and that special ciphertext will reveal the last character of the original (secret) $\ptxt$. For example, if $\subname{nulloracle}$ responds $\mytrue$ on input $\ctxt \oplus (\cdots \bit{00} \| \byte{c8})$, then the adversary can conclude that last byte of $\ptxt$ is $\byte{c8}$.

Again, there is nothing special about the last ciphertext byte. The same approach can be used to discover any byte of the original plaintext, by xor'ing the corresponding byte of ciphertext with all 255 possible guesses.

9.2. Defining security against chosen-ciphertext attacks

Format-oracle attacks demonstrate that CPA-secure encryption doesn't always meet our expectations. We expect that the $\subname{nulloracle}$ subroutine will give the adversary the ability to learn whether the victim's plaintexts contain null characters. If the victim is careful enough to avoid null characters in its plaintexts, then we expect $\subname{nulloracle}$ to always return $\myfalse$, and to therefore be useless. But, contrary to those expectations, $\subname{nulloracle}$ gives the adversary the ability to completely decrypt ciphertexts.

Real-world systems receive ciphertexts from the network, decrypt those ciphertexts, and then do something based on the result. But the CPA attack scenario doesn't involve the decryption algorithm at all, so CPA security can't tell us what happens in real-world situations like these. When a victim decrypts ciphertexts chosen by the adversary, we describe the situation as a chosen-ciphertext attack.

First attempt at a security definition: We can follow our usual approach to formalize an attack scenario. In a chosen-ciphertext attack, a victim runs both the encryption and decryption algorithms, manages the secret key, but leaves everything else under control of the adversary. In the real-or-random paradigm, we say that an encryption scheme is secure if its ciphertexts are pseudorandom.

Following this reasoning, we would say that the scheme $\Sigma$ is secure against chosen-ciphertext attacks if the following two libraries are indistinguishable:

Unfortunately, these libraries don't lead to a useful security definition, because they can never be indistinguishable. An adversary can call $\ccaenc(\ptxt)$ to get a ciphertext $\ctxt$, then give $\ctxt$ immediately as input to $\ccadec$. In $\lib{real}$, the result will always be $\ptxt$. In $\lib{rand}$, the result is unlikely to be $\ptxt$ because $\ctxt$ is a meaningless string that is unrelated to $\ptxt$. An adversary can always successfully distinguish these two libraries with this simple strategy.

The Real Definition: To arrive at the actual definition of chosen-ciphertext security, we must make one small modification to the $\lib{rand}$ library. We usually call a ciphertext produced as output of $\ccaenc$ a challenge ciphertext. When $\ccadec$ is given such a challenge ciphertext that was the result of a previous call to $\ccaenc(\ptxt)$, rather than trying to decrypt it as usual, it should “lie” and simply give $\ptxt$ as the response. This modification is enough to thwart the simple attack described above, and it results in a security definition that can be achieved.

A Metaphor for CCA Security: It's normal to be a little confused by the CCA security definition. I like the following physical metaphor: I will place any message of your choice into a special “challenge” envelope and seal it. I will gladly open any envelope in the universe that you bring to me; however, there is no need for me to open the challenge envelope, since we both already know what's inside. Of course, the contents of other envelopes have nothing to do with the contents of challenge envelope. In fact, the contents of other envelopes won't even help you discover that I was actually lying to you! What you thought was the challenge envelope was actually a decoy piece of paper disguised to look like an envelope. My challenge “envelope” doesn't have a message inside—it doesn't even have an inside.

CTR mode encryption fails this envelope metaphor because of its malleability. Returning to the physical analogy, malleability is like having a weird machine that can clone sealed envelopes while modifying what's inside. Put a sealed envelope containing $\ptxt$ into the cloning machine (along with a string $\Delta$), and what comes out is a different sealed envelope containing $\ptxt \oplus \Delta$. Now opening these clones (revealing $\ptxt \oplus \Delta$) will help you learn what's inside the special envelope.

9.2.1. ☆ Other approaches for defining security

Definition 9.2.1 is not the most common way to define CCA security in the cryptographic literature.

• Like all security definitions in this book, definition 9.2.1 follows the real-or-random paradigm. It is possible (and more traditional) to define CCA security in the left-or-right style—the result would generalize the left-or-right definition for CPA security from definition 8.1.2.

• Any definition of CCA security must deal with the event that the adversary invokes $\ccadec$ on a challenge ciphertext. Our approach, taken in definition 9.2.1, is to “patch” $\ccadec$ in $\lib{cca-rand}$ to always give the “expected result” for these special ciphertexts. A different (and more traditional) approach is to make $\ccadec$ in both libraries simply refuse to decrypt challenge ciphertexts. The two approaches are equivalent (see exercise 9.8).

The standard, traditional way to define CCA security (which you might see in other resources) uses the left-or-right paradigm and also refuses to decrypt the challenge ciphertexts. The two libraries look like this:

9.3. Chosen-ciphertext attack strategies

The best way to get a better intuition about CCA security is to attack the encryption schemes that we've already studied.

9.3.1. A first example

Let's start with the first CPA-secure encryption scheme we saw, construction 8.3.1:

This scheme is not CCA-secure. In other words, there is an efficient attack that can distinguish the following two libraries:

Notice that the entire ciphertext $R\|S$ is used as the index in $\mathcal{D}[\cdot]$. This is an important fact about the CCA security definition.

Have you already noticed that this encryption scheme is simply CTR mode restricted to a single block? Then it's no surprise that the attack against this scheme involves CTR mode's malleability. Translating fact 9.1.2 to the terminology of this 1-block scheme, we know:

You can see malleability reflected in the schematic diagram of this scheme's decryption algorithm. Changes to the ciphertext block $S$ are propagated directly to the output plaintext $\ptxt$, because the “path” from $S$ to $\ptxt$ includes only an xor operation.

A calling program to the $\lib{cca-*}$ libraries can use this malleability to attack CCA security as follows:

When this calling program is linked to $\lib{cca-real}$, it returns $\mytrue$ with probability 1, thanks to the scheme's malleability property.

What about when it is linked to $\lib{cca-rand}$? We can understand the behavior of $\A \link \lib{cca-rand}$ through the following observations:

• $\ccaenc$ is called once, which has the effect of assigning $\mathcal{D}[ R \| S ] := \ptxt$.

• Since $\Delta \ne \bit0^\secpar$, the ciphertext $R \| (S \oplus \Delta)$ is different from $R \| S$. Therefore, the call to $\ccadec$ will find $\mathcal{D}[R \| (S \oplus \Delta)]$ undefined. It doesn't matter that both of these ciphertexts have the same $R$! $\lib{cca-rand}$ doesn't “see” the internal structure of ciphertexts; it treats them as monolithic strings. The strings $R\|S$ and $R\|(S\oplus \Delta)$ are different strings.

• The library writes $\ptxt$ to $\mathcal{D}[\cdot]$ but never reads from it. Hence, it does not use the value of $\ptxt$ at all.

• The calling program does not use the value of $\ptxt$ until its return statement.

These observations imply that the choice of $\ptxt$ is independent of everything that happens before the calling program's return statement. We can imagine an equivalent computation in which $\ptxt$ is sampled at the last possible moment, just before the return statement, and after $\ptxt'$ and $\Delta$ have been fixed. Once these values have been fixed, there is only one choice of $\ptxt$ that satisfies the condition $\ptxt' == \ptxt \oplus \Delta$ and causes the calling program to return $\mytrue$. Since $\ptxt$ is chosen uniformly, the probability that the calling program returns $\mytrue$ is only $1/2^\secpar$. (This is why it was convenient to sample $\ptxt$ uniformly in this attack, rather than let it be arbitrary.)

Since the two probabilities differ by more than a negligible amount, the attack is successful and the scheme does not have CCA security.

This attack is the simplest example of a common strategy for chosen-ciphertext attacks:

9.3.2. A second example

The previous scheme was malleable via xor, a fact that you could see reflected in the schematic diagram of its decryption algorithm. Let's try a harder challenge, with a scheme that does not have such obvious malleability.

Focusing on the decryption algorithm, changes to $R$ or to $S$ propagate through an instance of $F$ or $F^{-1}$ before affecting the output plaintext. From the adversary's perspective, $F^{\pm}$ acts like a random function; any change in an input leads to an unpredictable change in the output. Hence, unlike in the previous scheme, the adversary cannot predict how a change to the ciphertext will affect the plaintext.

To attack this new scheme, we need a new approach, which I call the Frankenstein strategy. Ciphertexts in this scheme have two halves, so what would happen if we mix and match the halves of two different ciphertexts? Surprisingly, something interesting:

We are now ready to formalize the attack. We will refer to the new “mismatched” ciphertexts $R_1 \| S_2$ and $R_2 \| S_1$ as Frankenstein ciphertexts. A chosen-ciphertext attack against the scheme is a program that successfully distinguishes the following two libraries:

The calling program is as follows:

When linked to $\lib{cca-real}$, the program outputs $\mytrue$ with probability 1 according to claim 9.3.1. When $\A$ is linked to $\lib{cca-rand}$, we must consider two cases:

• Case 1: If $R_1 = R_2$ or $S_1 = S_2$ (or both) then we in fact have:

  $\{ R_1 \| S_1, R_2 \| S_2 \} = \{ R_1 \| S_2, R_2 \| S_1 \}.$

  The Frankenstein ciphertexts are the same as the original ciphertexts (this also includes the case where all four ciphertexts are the same). In other words, the calling program calls $\ccadec$ on the original challenge ciphertexts, which will be found in $\mathcal{D}[\cdot]$. Thus, both calls to $\ccadec$ will return $\ptxt$, and the calling program returns $\mytrue$. Since $R_1, R_2, S_1, S_2$ are distributed uniformly, the probability of this case is at most $2/2^{\secpar}$.

• Case 2: $R_1 \ne R_2$ and $S_1 \ne S_2$. Then the original ciphertexts and Frankenstein ciphertexts are all distinct. So when the calling program calls $\ccadec$, the Frankenstein ciphertexts will not be found in $\mathcal{D}[\cdot]$, and the library will proceed to decrypt them as usual. The two resulting plaintexts are identical, and $\A$ returns $\mytrue$, if and only if:

  $\begin{aligned} M_1^* &= M^*_2 \\ \iff \Dec(\key, R_1 \| S_2) &= \Dec(\key, R_2 \| S_1) \\ \iff F^{-1}\bigl(\key, F(\key,R_1) \oplus S_2\bigr) &= F^{-1}\bigl(\key, F(\key,R_2) \oplus S_1\bigr) \\ \iff F(\key,R_1) \oplus S_2 &= F(\key,R_2) \oplus S_1.\end{aligned}$

  The last step follows by applying $F(\key,\cdot)$ to both sides, to cancel $F^{-1}$. The final condition happens with probability $1/2^\secpar$ because $S_1$ and $S_2$ are sampled uniformly in $\lib{cca-rand}$, and independent of $\key$.

The overall probability that the calling program outputs $\mytrue$ is at most the sum of these two cases, $3/2^\secpar$. The difference between output probabilities for $\lib{cca-real}$ and $\lib{cca-rand}$ is nonnegligible, so the scheme does not have CCA security.

9.4. Message authentication codes

Chosen-ciphertext attacks have shown us that there is risk involved when decrypting a ciphertext that has been crafted by the adversary. Imagine there was some way to “certify” that a ciphertext was not adversarially generated, but was generated by someone who knows the secret key. Such a certification would give the decryption algorithm a way to distinguish honestly generated ciphertexts from adversarially generated ones, so that it could refuse to decrypt (e.g., return an error) the adversarially generated ones.

What we are asking for is not to hide the ciphertext but to authenticate it: to ensure that it was generated by someone who knows the secret key. Later we will discuss how to apply this idea to chosen-ciphertext attacks; for now, let's develop more clarity about authenticating that some data was generated/chosen by someone who knows the secret key.

Let's begin with a simple thought experiment. I choose a string $S$ uniformly at random from $\bits^\secpar$, but keep it secret. Will you be able to guess what it is? Probably not! Even if I let you have many guesses (any polynomial in $\secpar$) you will guess correctly only with negligible probability.

Now suppose that instead of one string, I have many strings stored in a random dictionary; let's call it $\prftable[\cdot]$. Each $\prftable[X]$ is chosen uniformly and independently. You can ask me to reveal any value in the dictionary; just provide its location $X$ and I will tell you $\prftable[X]$. You can also try to guess a value, by providing $X$ and your guess $Y$ for $\prftable[X]$. Is it possible for you to correctly guess a string that I haven't yet revealed? Again, the answer is no, except with negligible probability. Since all of the strings are chosen independently, seeing other strings doesn't help you correctly guess this string.

If we now replace the random dictionary with a PRF, we will have what is called a message authentication code (MAC). For every string $X$, the PRF output $F(\key,X)$ is hard to predict by someone who doesn't know $\key$, even if they are allowed to see PRF outputs for other strings $X' \ne X$. Thus, only someone who knows $\key$ can generate a pair $(X, F(\key,X))$.

We call $F(\key,X)$ the tag (or MAC tag) of $X$; it authenticates $X$. If you see $X$ accompanied by the correct value $F(\key,X)$, you can conclude that someone who knows $\key$ has vouched for $X$. (Be careful: It doesn't mean that the person you're currently talking to knows $\key$; perhaps that person is replaying a correct pair $(X, F(\key,X))$ that they heard from someone else who knows the key.)

A tag can be verified by recomputing the “correct” tag using the secret key, and comparing it to the given tag. A forgery occurs when an adversary generates a correct tag without having seen it before. The security guarantee of a MAC is that it is hard to generate a forgery, even after seeing many examples of correct tags. We can formalize this MAC property of PRFs as follows:

These two libraries may seem strange, because this is the first time we are using libraries to define an authenticity property rather than a privacy (information-hiding) property. You can make sense of the libraries in the following way:

• In $\lib{mac-real}$, it is possible for $\macguess(X,Y)$ to output $\mytrue$ before $\macreveal(X)$ has been called.

• In $\lib{mac-ideal}$, it is not possible for $\macguess(X,Y)$ to output $\mytrue$ before $\macreveal(X)$ has been called, because $\prftable[X]$ remains undefined until $\macreveal(X)$ has been called.

• Thus, if an adversary can correctly guess a valid tag “early,” before it is revealed, then $\macreveal$ in $\lib{mac-real}$ would return $\mytrue$ but in $\lib{mac-ideal}$ it would return $\myfalse$. These different responses would allow the adversary to easily distinguish the libraries. So if the libraries are indistinguishable, then it must be hard to correctly guess a valid tag early—that is, to generate a forgery.

MACs as a separate cryptographic primitive: In this book, we define message authentication (MAC) as a convenient property of PRFs. That's because most MACs you will see in practice are simply PRFs. In other sources, you may see MACs defined as a separate cryptographic primitive.

• In this book, a MAC algorithm is always a PRF, and therefore generates pseudorandom tags. In the cryptographic literature, we generally call something a MAC when we don't care about its outputs being pseudorandom, and care only about its outputs being unforgeable. Being pseudorandom is just one natural way, but not the only way, to be unforgeable. For example, appending extra $\bit0$'s to the end of a tag does not make tags any easier to forge, but does prevent them from being pseudorandom. Traditional security definitions for MACs therefore do not require the MAC algorithm's outputs to be pseudorandom, as we do in lemma 9.4.1.

• PRFs are always deterministic. But when treating MACs as a full-fledged primitive, it may make sense to allow a MAC algorithm to be randomized.

• Every deterministic MAC algorithm has a canonical verification method: Deterministically recompute the correct tag and compare to the given tag. Only deterministic MACs are considered in this book, so MAC tags are always verified using this canonical method. In a randomized MAC, each message can have several valid tags, so we must specify a separate (noncanonical) verification algorithm to go with the MAC algorithm.

• Suppose we are using a MAC scheme in which message $\ptxt$ has several different tags that verify successfully. Then suppose an adversary queries $\macreveal$ to learn one valid tag $T$ for $\ptxt$. Is it considered a forgery if the adversary then successfully guesses a different, but valid, tag $T' \ne T$ for the same message $\ptxt$? The answer may depend on the application we have in mind for the MAC. Strong unforgeability demands that it be hard to guess new valid tags, even to messages for which the adversary has already seen a valid tag. Weak unforgeability means that it should be hard to guess valid tags of only new messages, for which the adversary has not seen any valid tag. It is not considered a forgery to guess a new tag for $\ptxt$ after seeing a valid tag for $\ptxt$. The distinction between strong and weak unforgeability is irrelevant for deterministic MAC algorithms with canonical verification.

9.5. Encrypt-then-MAC

With a MAC, we can transform any CPA-secure encryption into a CCA-secure one. The idea is to append a MAC tag of the ciphertext. The decryption algorithm should verify this tag before decrypting, and return an error if the tag is invalid. Only someone who knows the secret key can compute the correct MAC tag, and so only “legitimate” ciphertexts will be decrypted. This approach thwarts chosen-ciphertext attacks because if an adversary tries to tamper with a ciphertext in any way, they will not be able to produce the correct tag for the modified ciphertext.

Ciphertexts in the new scheme consist of two parts: a ciphertext from the underlying scheme $\Sigma$, plus a tag. It is important to use independent keys for $\Sigma$ and the MAC/PRF.

Proof idea: The two libraries, which we would like to prove are indistinguishable, both feature the $\Sigma.\Dec$ algorithm. However, we may only use the fact that $\Sigma$ is CPA-secure. The libraries that define CPA security do not mention $\Sigma.\Dec$ at all. You can think of CPA security as saying “ciphertexts are pseudorandom, if the key is used only for the encryption algorithm and nothing else.”

Thus, our main strategy in this proof is to rewrite the libraries so that $\Sigma.\Dec$ doesn't appear at all. You might be wondering how this is possible. The main insight is that the library only runs $\Sigma.\Dec$ if the MAC tag verifies successfully. If the MAC is secure, then we expect this to be possible only for ciphertexts generated by the library itself. But if the library originally generated a ciphertext, then it should already know the corresponding plaintext, and it should not need to run $\Sigma.\Dec$.

In more detail:

• Whenever the $\ccaenc$ subroutine generates a ciphertext, it can internally store the plaintext that was used. If that ciphertext is later given to $\ccadec$, the library can retrieve the plaintext from this storage, so it doesn't need to run $\Sigma.\Dec$.

• When $\ccadec$ sees a ciphertext that was not previously generated by $\ccaenc$, we do not expect the MAC tag to be valid. In other words, we expect that $\ccadec$ will return $\myerr$ before even reaching the line where it calls $\Sigma.\Dec$. In these cases, $\Sigma.\Dec$ is not needed.

So the only situation where $\ccadec$ truly needs to run $\Sigma.\Dec$ are the cases where the adversary successfully generates a MAC forgery. These cases should be negligibly likely; we express this idea formally by arguing that the library is indistinguishable from one that doesn't use $\Sigma.\Dec$ in this case (and thus, never uses $\Sigma.\Dec$ at all).