Chosen-Plaintext Attacks Against Encryption

The encryption schemes we have seen so far have been severely limited. Specifically, they are secure only when each key is used to encrypt a single plaintext. In this chapter, finally, we study real encryption, in which one short key can safely encrypt any number of plaintexts.

8.1. Definitions and leaking the plaintext length

One-time secrecy for encryption (definition 2.5.3) considers an attack scenario in which a new/fresh key is chosen for each ciphertext. With a simple modification, we can write a library that describes an attack scenario where the same key is used for all encryptions:

Then, we can demand that the adversary sees only random junk in this attack scenario. In other words, the following two libraries must be indistinguishable:

This is indeed a reasonable security definition for multi-use encryption, but it does contain a subtle problem. To understand why, suppose we have an encryption scheme that supports plaintext of any length, where plaintexts of length $\ell$ are encrypted into ciphertexts of length $\ell+\secpar$. Several examples of such schemes are described later in this chapter. Then just by looking at the length of a ciphertext, an adversary can learn something about the plaintext! For example, an adversary can easily tell whether you have encrypted a small 1 KB plaintext or a huge 1 GB plaintext; such an attack would be incompatible with the security definition given above (see exercise 8.1).

The problem with this security definition also surfaces in the following way: Suppose an encryption scheme supports an infinite set of possible plaintexts—say, it supports plaintexts of arbitrary length. Then the set of possible ciphertexts $\C$ must also be infinite. The library above includes a statement “$\ctxt \gets \C$”, but what can this mean if $\C$ is infinite? There is no well-defined uniform distribution over an infinite set!

The issue does not arise for encryption schemes that support only a fixed plaintext length, including all of the schemes we have seen so far. In those cases, $\C$ was finite, and there is no problem with the security definition above. But in the more general case:

Ciphertexts must leak (something about) the plaintext's length, so the best we can hope for is that ciphertexts leak nothing more than the plaintext length. We can modify the security definition to reflect this idea as follows. The security definition above says, essentially, “encryptions of $\ptxt$ are indistinguishable from a uniformly sampled ciphertext (from the space of all possible ciphertexts).” We can instead demand that “encryptions of $\ptxt$ are indistinguishable from a uniform sample from the set of all encryptions of plaintexts with the same length as $\ptxt$.”

A good way to understand this new definition is to study the $\lib{cpa-rand}$ library. The only information it uses about $\ptxt$ is its length, and it ignores everything else about $\ptxt$. So outputs from $\lib{cpa-rand}$ simply cannot leak more than the length of $\ptxt$. And if the two libraries are indistinguishable, we can conclude that true ciphertexts generated by $\lib{cpa-real}$ also do not leak more than the length of the plaintext.

8.1.1. The plaintext length side-channel

Encryption cannot completely hide the length of plaintext data. We must accept this fact, even if its consequences are unpleasant. Plaintext length can convey a surprising amount of information and have huge impacts to real-world security! An adversary who observes only the length and timing of your encrypted network traffic can figure out:

• which pages you visited on Wikipedia, or any website with relatively static content of different sizes;

• which movie you are streaming, because video formats use variable bit-rate (VBR) encodings, so that “busier” segments of the video require more data per second;

• or even what you are saying in an encrypted audio call!

See the chapter notes for references about these attacks. Personally speaking, these are the kinds of attacks that give me the most existential dread about cryptography. However, encryption is about more than just hiding the content of communication, as we will see later in section 9.6.

8.1.2. ☆ CPA security in the left-or-right paradigm

Recall the discussion in section 2.7. Our default way to define security of encryption is the real-or-random paradigm, but it is also possible to use the left-or-right paradigm. A security definition in the left-or-right style says, essentially, if an adversary provides two plaintexts $\ptxt_L, \ptxt_R$, then they cannot tell which of those two plaintexts is actually encrypted.

However, if $\ptxt_L$ and $\ptxt_R$ have very different lengths, then we do expect it to be possible to distinguish their encryptions. Only when the plaintexts have the same length can we reasonably expect their ciphertexts to be indistinguishable. Thus, when defining security in the left-or-right paradigm, we limit the adversary to plaintext pairs $(\ptxt_L, \ptxt_R)$ of equal length. This is achieved by making the library give an error if the adversary provides $\ptxt_L$ and $\ptxt_R$ of different lengths.

This left-or-right flavor of CPA security is commonly called IND-CPA, which stands for “ciphertext indistinguishability, under chosen-plaintext attacks.” The real-or-random flavor (definition 8.1.1) is often called IND$-CPA, which stands for “indistinguishability from random/uniform, under chosen-plaintext attacks.”

8.2. Deterministic encryption

A deterministic encryption scheme cannot have CPA security.

One-time pad is an example of a deterministic encryption scheme. The scheme from construction 2.6.1 was not deterministic.

If an encryption scheme is deterministic and an adversary sees the same ciphertext twice, then he/she can deduce that the same plaintext was sent twice. In other words, the adversary learns something about the plaintexts! We can formulate this attack as a calling program that distinguishes the $\lib{cpa-*}$ libraries:

When this calling program is linked to $\lib{cpa-real}$ and the encryption scheme is deterministic, it outputs $\mytrue$ with probability 1. When linked to $\lib{cpa-rand}$, $\ctxt_1$ and $\ctxt_2$ are distributed uniformly over $\C(\ell)$, where $\ell = |\ptxt|$. So $\ctxt_1 = \ctxt_2$ only with probability $1/\bigl|\C(\ell)\bigr|$. The difference between these probabilities is nonnegligible, and so the scheme is not CPA-secure.

You may be thinking, “Of course the same plaintext will result in the same ciphertext! How can this really be a problem?” Be careful that your mental model of encryption has not been “overfitted” to deterministic schemes like OTP and simple toy substitution ciphers (newspaper cryptograms). The problem with deterministic encryption is a direct consequence of definition 8.1.1. The definition has no special exceptions for repeated plaintexts! If you accept definition 8.1.1, then you must accept that encryption cannot be deterministic. Besides, we can achieve this definition of CPA security; encryption can hide whether plaintexts repeat! Since we can hide this information, we should.

8.3. A randomized encryption scheme based on PRFs

Since deterministic encryption cannot be CPA-secure, we will consider schemes whose $\Enc$ algorithm is randomized. (This is not the only way to avoid the limitations of deterministic encryption; see section 8.7.)

In this section we describe an encryption scheme based on a PRF. Each time Alice wants to send a message to Bob, she uniformly samples a value $R$. She uses $F(\key,R)$ as a OTP key to encrypt her plaintext, and she also includes $R$ as part of the ciphertext. Given $R$, Bob can compute the same OTP key $F(\key,R)$ and use it to decrypt the plaintext. But an eavesdropper who sees $R$ will not be able to guess $F(\key,R)$ when $F$ is a secure PRF.

This encryption scheme supports plaintexts of a single, fixed length. Thus, there are no complications when it comes to leaking the plaintext length—their length is already a public parameter of the scheme.

Proof idea: The goal is to show that ciphertexts in this scheme are pseudorandom. What can we say about how these ciphertexts are generated?

Ciphertexts consist of two parts, $R$ and $S$. $R$ is clearly sampled uniformly, so there is not much to say about it. But $S$ is computed as $S = F(\key,R) \oplus \ptxt$. We can interpret this as a kind of OTP ciphertext, with $F(\key,R)$ acting as the OTP key. But OTP produces uniform ciphertexts only when the key is uniform and used only once. Is that the case with $F(\key,R)$ here?

Since $F$ is a secure PRF, its outputs are indeed pseudorandom, but only when the PRF's inputs are distinct. Can we argue that these inputs don't repeat?

The inputs in question are the $R$-values, which are uniformly sampled $\secpar$-bit strings. Thus, the probability of a repeat is the standard birthday probability, which is negligible. The formal proof is the result of assembling all of these observations, to finally conclude that ciphertexts of the form $R\|S$ are pseudorandom.

8.4. An example chosen-plaintext attack

As usual, security is a knife's edge, requiring everything to be in a delicate balance. Make one seemingly minor change to a secure scheme, and all security may be lost. Such is indeed the case with the scheme from the previous section. In that scheme, the second part of the ciphertext is computed as $F(\key,R)\oplus\ptxt$. Suppose we swap the role of $\ptxt$ and $R$ and compute the second part of the ciphertext as $F(\key,\ptxt) \oplus R$. The result, as we show below, is totally insecure:

This example illustrates an important distinction between the values $R$ and $\ptxt$ in construction 8.3.1. Its security rests on the fact that $\ptxt$ is under the complete control of the adversary, while $R$ is under the complete control of the victim.

8.5. Block cipher modes

Construction 8.3.1 supports plaintexts of a single, fixed length. In this section we discuss how to efficiently encrypt long plaintexts, of variable length, using a single key. These methods are called block cipher modes (sometimes called modes of operation): recipes for using a block cipher (PRP) to process data that is longer than a single block.

In this section we will focus on plaintexts whose length is a multiple of the PRP's blocklength. In other words, we assume that each plaintext can be divided exactly into blocks that are suitable as inputs to the PRP. We call such plaintexts block-aligned and write each $\ptxt$ as $\ptxt_1 \| \ptxt_2 \| \cdots$, where each $\ptxt_i$ is a single block. Later in section 8.6 we discuss how to properly handle non-block-aligned plaintexts.

We will write $(\bits^\secpar)^*$ to denote the set of all block-aligned strings with blocklength $\secpar$: strings consisting of any number of complete blocks. In this section we will also measure the length of plaintexts in units of blocks. For example, security proofs refer to $\Sigma.\C(\ell)$, which in our case will mean the set of ciphertexts obtained by encrypting plaintexts of $\ell$ blocks, not bits.

8.5.1. ECB mode

We start by discussing what not to do: ECB mode is the “obvious” way to apply a block cipher to a long plaintext. It's a horrible idea. The only reason to mention it is to teach you its name so you can recognize it, avoid it, and publicly shame anyone who uses it.

ECB is deterministic, so of course it is insecure! Please don't use ECB mode.

8.5.2. CBC and CTR modes

Quickly moving past ECB mode, let's now see two good block cipher modes.

Both CBC and CTR modes are randomized; they each start by uniformly sampling the initialization vector. In both modes the ciphertext is one block longer than the plaintext.

Comparison: CBC and CTR modes are essentially the only two modes that are ever used in practice for CPA security. Both provide the same qualitative security guarantee, and so any comparison between the two must be based on things outside of the CPA security definition. Here are a few properties that are often considered when choosing between these modes:

• CTR mode does not use the block cipher's inverse $F^{-1}$, even for decryption. Thus, CTR requires only a PRF rather than a PRP. However it is rare to encounter an efficient PRF in practice that is not also a PRP.

• Both CBC and CTR modes have a parallelizable decryption algorithm, meaning that you can directly decrypt any plaintext block without first decrypting all previous ones. However, only CTR has a parallelizable encryption algorithm. After choosing the IV in CTR mode, you can generate any ciphertext block directly without first encrypting all previous blocks. CBC mode encryption is inherently sequential.

• If the block cipher is expensive, you might want to precompute block cipher evaluations and store the results early, even before the plaintext is chosen. CTR mode allows this, since only the IV affects the input given to the block cipher. In CBC mode, the plaintext influences the inputs to the block cipher, so these calls cannot be precomputed.

• It is relatively easy to modify CTR to support plaintexts that are not an exact multiple of the blocklength. It is less straightforward (although not difficult) to make CBC support such plaintexts. We discuss these issues later in section 8.6.

• So far all of the comparisons have favored CTR mode, so here is one important property that favors CBC mode. It is common for implementers to misunderstand the security implications of the IV in these modes. Many careless implementations may allow an IV to be reused. Rather than dumping the blame on the developer for an incorrect implementation, it is good design practice to anticipate likely misuses of a system and, when possible, make them noncatastrophic.

  CTR mode fails catastrophically when an IV is reused: It leaks the xor of the two plaintexts. CBC mode is more resilient to IV reuse: Depending on the specifics of the attack scenario, it can leak nothing in the case that the plaintexts have different first blocks (see exercise 8.30).

Proof of Security:

Both CBC and CTR modes have CPA security. Below we prove security of CBC mode:

8.6. Non-block-aligned plaintexts

So far we have been assuming that all plaintexts are an exact multiple of the blocklength, but this may not always be the case in practice. How can we adapt these encryption methods to support plaintexts of any length?

8.6.1. CTR mode

CTR requires almost no changes to support arbitrary plaintext lengths. The main idea behind CTR mode is to xor the plaintext with the long string:

To support plaintexts of arbitrary length, we can therefore simply truncate this long string to the correct length.

To be more precise, let us divide the plaintext $\ptxt$ as before into blocks $\ptxt_1 \| \cdots \| \ptxt_\ell$, except now the last piece $\ptxt_\ell$ may be only a partial block. We then truncate the last PRF output $F(\key,\ctxt_0 + \ell-1)$ to the same length as $\ptxt_\ell$, so the two strings can be xor'ed. These changes to CTR mode encryption are highlighted below:

The ciphertext will always be exactly one block longer than the plaintext, from the addition of the IV $\ctxt_0$.

8.6.2. CBC mode

CTR mode uses its plaintext blocks only for xor, an operation that can be performed on strings of any length. On the other hand, CBC mode processes plaintexts as $F(\key, \ctxt_{i-1} \oplus \hl{\ptxt_i})$, which makes sense only when $\ptxt_i$ is an entire block.

Hence, the easiest way to adapt CBC mode to arbitrary-length plaintexts is to encode all plaintexts into block-aligned data. This process is called padding, and there are many reasonable ways to do it.

When we augment CBC mode with a padding method, we obtain an encryption scheme that supports plaintexts of arbitrary length.

Below are a few possible padding methods. In the real world, data nearly always consists of bytes; when was the last time you needed to encrypt 5 bits? Thus, the standard padding methods below are described assuming that the input is a string of bytes.

8.7. ☆ Nonce-based encryption

We argued in section 8.2 that encryption cannot be deterministic; calling $\Enc(\key,\ptxt)$ twice with the same key and plaintext should not produce the same output. Something needs to be different each time $\Enc$ is called, even with the same key and plaintext. In a randomized encryption scheme, the $\Enc$ algorithm samples fresh random values each time it is called.

However, randomization is not the only way to make an encryption scheme “not deterministic.” Another alternative involves rethinking how we formally define what “encryption” is. We can insist that the encryption and decryption algorithms take an additional argument called a nonce, which is shorthand for “number used [only] once.” To use nonce-based encryption properly, you should use a different nonce each time $\Enc$ is called. The nonce therefore provides the necessary variability to overcome the limitations of deterministic encryption, even when plaintexts are repeated.

Randomized encryption is the more traditional way to define encryption. Nonce-based encryption is a newer paradigm, but is becoming more common because nonces are much less fragile than randomness.

The security of a randomized encryption scheme depends on its randomness being uniform and unpredictable. This is easy to get wrong in practice: Implementers may use poor randomness; they may use randomness that an adversary can predict; they may repeat randomness by accident. Even worse, they may leave this randomness up to the end-user, like many cryptography software libraries that require the end-user to provide IVs. In any of these cases, an ostensibly secure scheme could be catastrophically insecure in practice, since the reality of the implementation no longer reflects the CPA attack scenario.

The security of a nonce-based scheme depends only on the fact that nonces don't repeat—that's all. Nonces can be predictable; they can even be chosen by the adversary; all that matters is that they don't repeat.

In the formal security definition for nonce-based encryption, the adversary indeed gets to choose each nonce, just as it can choose each plaintext. The victim records the nonces it has seen previously, and refuses to use any nonce more than once. In this way, the security definition is limited to scenarios where nonces are distinct.

Nonce-based encryption has additional advantages:

• It can be deterministic by definition. Deterministic algorithms are easier to test and also harder to get wrong.

• The nonce can be included in the ciphertext (like an IV), but it does not need to be. In many settings the nonce is a value that both the sender and receiver already know. For example, the nonce might be a simple counter, or packet sequence number. In fact, it's preferable to not consider the nonce as part of the ciphertext for the purposes of the security definition, since the nonce need not look pseudorandom.

• Nonce-based encryption can avoid ciphertext expansion. If we don't consider the nonce as part of the ciphertext, then ciphertexts can be exactly as long as the plaintexts. This is not possible with randomized encryption.

• Nonce-reuse can be detected. A poor source of randomness can be difficult or even impossible to detect.

Finally, you can always choose to use uniformly sampled bits as the nonce if you like, and send this nonce along with the ciphertext. In other words, it is always safe to implement the nonce as an IV. Implementing a nonce-based scheme still leaves open the possibility of providing a randomized scheme.

However, the converse is not true; it is not always safe to treat the IV of a randomized encryption scheme as a nonce. Indeed, both CTR and CBC modes (as defined in this chapter) are insecure if their IV is treated as a nonce. Their security proofs rely crucially on the IV being sampled uniformly and unpredictable to the adversary, whereas a nonce can be chosen by the adversary.

The exercises explore these and other aspects of nonce-based encryption in greater depth.

Exercises

1. h$\star$ Suppose $\Sigma$ is an encryption scheme with $\Sigma.\M = \bits^*$. Show that it is not possible for $\Sigma$ to hide the length of the plaintext.

   More formally, show that the following two libraries are not indistinguishable:

   $\lib{sk-cpa-left}$

   $\key \gets \Sigma.\K$

   $\cpaenc(\ptxt_L, \ptxt_R)$:

   // if $|\ptxt_L| \ne |\ptxt_R|$: return $\myerr$

   $\ctxt := \Sigma.\Enc(\key,\hl{\ptxt_L})$

   return $\ctxt$

   $\indist$

   $\lib{sk-cpa-right}$

   $\key \gets \Sigma.\K$

   $\cpaenc(\ptxt_L, \ptxt_R)$:

   // if $|\ptxt_L| \ne |\ptxt_R|$: return $\myerr$

   $\ctxt := \Sigma.\Enc(\key, \hl{\ptxt_R})$

   return $\ctxt$

   Note: These libraries allow $\ptxt_L$ and $\ptxt_R$ to have different lengths.

   Fix a string $\ptxt_L$, and suppose $\ell$ is an integer that satisfies $\PR{ | \Enc(\key,\ptxt_L) | < \ell } \ge 1/2.$ Although you might not know $\ell$, you can define a calling program for each possible $\ell$ and argue that one of them succeeds in the attack.

   For a particular $\key$, how many possible values are there for $\Dec(\key,\ctxt)$, over all $\ctxt$ that are shorter than $\ell$ bits? If $\ptxt_R$ is not among these values, then $\ptxt_R$ can never be encrypted to a string shorter to $\ell$ bits, under this key. Now suppose $\ptxt_R$ is chosen uniformly from $\bits^{2\ell}$; what is the probability that $\ptxt_R$ is encrypted to a ciphertext shorter than $\ell$ bits?

2. Find a website with a moderate amount of static content, of varying lengths. Write a program to determine which page is being viewed when a victim browses this website over TLS, just by seeing a log/dump of the encrypted traffic.

3. Let $\Sigma_1$ and $\Sigma_2$ be encryption schemes with $\Sigma_1.\M = \Sigma_2.\M = \bits^n$. Define the following new scheme $\Sigma^*$:

   $\begin{aligned} \Sigma^*.\K &= \Sigma_1.\K \times \Sigma_2.\K \\ \Sigma^*.\M &= \bits^n \\ \Sigma^*.\C &= \Sigma_1.\C \times \Sigma_2.\C \end{aligned}$

   $\quad$

   $\Sigma^*.\Enc\bigl( (\key_1, \key_2), \ptxt \bigr)$:

   $R \gets \bits^n$

   $\ctxt_1 := \Sigma_1.\Enc(\key_1, R)$

   $\ctxt_2 := \Sigma_2.\Enc(\key_2, R \oplus \ptxt)$

   return $(\ctxt_1, \ctxt_2)$

   $\Sigma^*.\Dec\bigl( (\key_1, \key_2), (\ctxt_1,\ctxt_2) \bigr)$:

   $\ptxt_1 := \Sigma_1.\Dec(\key_1, \ctxt_1)$

   $\ptxt_2 := \Sigma_2.\Dec(\key_2, \ctxt_2)$

   return $\ptxt_1 \oplus \ptxt_2$

   Prove that $\Sigma^*$ is CPA-secure if one of $\Sigma_1$ and $\Sigma_2$ is CPA-secure. The proof should have two cases: one assuming $\Sigma_1$ is secure, and assuming nothing about $\Sigma_2$ except for its correctness; and vice versa.

4. Let $\Sigma$ be a CPA-secure encryption scheme such that $\Sigma.\C \subseteq \Sigma.\M$, so that any ciphertext in $\Sigma$ can be used as a plaintext as well. Prove that the scheme given by the following encryption algorithm is also CPA-secure:

   $\Sigma.\Enc\Bigl(\key, \Sigma.\Enc(\key, \ptxt)\Bigr).$

   Note that both calls to $\Sigma.\Enc$ use the same key.

5. Let $\Sigma$ be a CPA-secure encryption scheme with allowable plaintexts $\Sigma.\M = \bits^n$. Define the following scheme $\Sigma_2$ that supports plaintexts of length $2n$:

   $\begin{aligned} \Sigma_2.\K &= \Sigma.\K \\ \Sigma_2.\M &= \bits^{2n} \\ \Sigma_2.\C &= \Sigma.\C \times \Sigma.\C \end{aligned}$

   $\quad$

   $\Sigma_2.\Enc( \key, \ptxt_1 \| \ptxt_2 )$:

   $\ctxt_1 := \Sigma.\Enc(\key, \ptxt_1)$

   $\ctxt_2 := \Sigma.\Enc(\key, \ptxt_2)$

   return $(\ctxt_1, \ctxt_2)$

   $\quad$

   $\Sigma_2.\Dec( \key, (\ctxt_1,\ctxt_2))$:

   $\ptxt_1 := \Sigma.\Dec(\key, \ctxt_1)$

   $\ptxt_2 := \Sigma.\Dec(\key, \ctxt_2)$

   return $\ptxt_1 \| \ptxt_2$

   Prove that $\Sigma_2$ is also CPA-secure.

   In other words, it is safe to separately and independently encrypt different pieces of a plaintext. (You may wonder why such an “obvious” statement requires proof, but later in the book we study security definitions for encryption in which this modification of an encryption scheme is not safe.)

6. Give an example of an encryption scheme that satisfies left-or-right CPA security (definition 8.1.2) but not real-or-random CPA security (definition 8.1.1), and justify both properties of your answer. Your scheme does not need to be a natural/useful encryption scheme.

7. Prove that an encryption scheme $\Sigma$ achieves left-or-right CPA security (definition 8.1.2) if and only if the following two libraries are indistinguishable:

   $\lib{1}$

   $\key \gets \Sigma.\K$

   $\cpaenc(\ptxt)$:

   $\ctxt := \Sigma.\Enc(\key,\ptxt)$

   return $\ctxt$

   $\quad$

   $\lib{2}$

   $\key \gets \Sigma.\K$

   $\cpaenc(\ptxt)$:

   $\ctxt := \Sigma.\Enc(\key, \bit0^{|\ptxt|})$

   return $\ctxt$

   In other words, encryptions of a chosen $\ptxt$ are indistinguishable from encryptions of the all-zeros plaintext (of the same length).

8. Let $\Sigma$ be an encryption scheme, and write $\Sigma.\M(\ell)$ as shorthand for $\Sigma.\M \cap \bits^\ell$, the plaintexts of length $\ell$. Prove that an encryption scheme $\Sigma$ achieves left-or-right CPA security (definition 8.1.2) if and only if the following two libraries are indistinguishable:

   $\lib{1}$

   $\key \gets \Sigma.\K$

   $\cpaenc(\ptxt)$:

   $\ctxt := \Sigma.\Enc(\key,\ptxt)$

   return $\ctxt$

   $\quad$

   $\lib{2}$

   $\key \gets \Sigma.\K$

   $\cpaenc(\ptxt)$:

   $\ptxt^* \gets \Sigma.\M(|\ptxt|)$

   $\ctxt := \Sigma.\Enc(\key,\ptxt^*)$

   return $\ctxt$

   In other words, encryptions of a chosen $\ptxt$ are indistinguishable from encryptions of a uniformly chosen plaintext (of the same length).

9. h$\star$ For the purposes of this exercise, a (randomized) encryption scheme is called IV-based if there is a deterministic function $E$ such that encryption can be written as:

   $\Enc(\key,\ptxt)$:

   $R \gets \bits^\secpar$

   $C := E(\key,R,\ptxt)$

   return $R\|C$

   We call the scheme compact if $E(\key,R,\ptxt)$ always has the same length as $\ptxt$.

   Prove that if an encryption scheme is IV-based, compact, satisfies correctness, and achieves left-or-right CPA security (definition 8.1.2), then it also achieves real-or-random CPA security (definition 8.1.1). Usually the implication holds only in the other direction (real-or-random implies left-or-right).

   How are ciphertexts distributed when $\ptxt$ is chosen uniformly?

10. h In chapter 3, we defined security for secret sharing schemes using two interchangeable libraries. Furthermore, if the secret is $\ell$ bits, then shares must also be at least $\ell$ bits (exercise 3.4).

    Suppose we allow secret sharing schemes where the two libraries in definition 3.1.1 are merely indistinguishable. Construct a $t$-out-of-$n$ secret sharing scheme that can share an $\ell$-bit secret with shares of length $\ell/t + O(\secpar)$ bits. Prove that your scheme is secure.

    Start with the “sharing scheme” of exercise 3.17, which provides no secrecy, and encrypt its shares under a suitable key.

11. Suppose an encryption scheme $\Sigma$ satisfies correctness and has $| \Sigma.\M | = | \Sigma.\C |$. Prove that $\Sigma$ cannot be CPA-secure.

12. Suppose an encryption scheme $\Sigma$ satisfies correctness and has $\Sigma.\M = \bits^n$ and $\Sigma.\C = \bits^{n +\ell}$. The parameter $\ell$ measures the ciphertext expansion of the scheme. In this exercise you will prove that the expansion of a CPA-secure scheme cannot be too small.

    Consider the following calling program:

    $\A$

    $\ptxt \gets \M$

    $\ctxt_1 := \cpaenc(\ptxt)$

    $\ctxt_2 := \cpaenc(\ptxt)$

    return $\ctxt_1 == \ctxt_2$

    Say that “$\ctxt$ decrypts to $\ptxt$ under $\key$” if $\Dec(\key,\ctxt) = \ptxt$.

    1. Assume that for any $\key$ and any $\ptxt$, there are exactly $2^\ell$ values $\ctxt$ that decrypt to $\ptxt$ under $\key$. In this case, what is the advantage of $\A$ in distinguishing the $\lib{cpa-*}$ libraries?

    2. The previous part considers an optimistic case. In general, different keys and plaintexts can be associated with a different number of ciphertexts. Say that a plaintext $\ptxt$ is heavy with respect to key $\key$ if there are more than $2^{\ell+1}$ ciphertext values $\ctxt$ that decrypt to $\ptxt$ under $key$. What is the most number of heavy plaintexts there can be under one key? When $\A$ is linked to $\lib{cpa-real}$, $\A$ samples a plaintext $\ptxt$ and $\lib{cpa-real}$ samples a key $\key$. What is the maximum probability that $\ptxt$ is heavy with respect to $\key$?

    3. Assume that $n \ge \secpar$. Show that the advantage of $\A$ is at least $\frac{1}{2^{\ell+2}} - \frac{1}{2^\secpar}$.

13. Suppose $F$ is a secure PRP with blocklength $n + \secpar$. Prove that the following encryption scheme is CPA-secure and write its decryption algorithm:

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^n \\ \C &= \bits^{n+\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $C := F(\key, \ptxt \| R)$

    return $C$

14. Suppose $F$ is a secure PRP with blocklength $\secpar$. Prove that the following encryption scheme is CPA-secure and write its decryption algorithm:

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^\secpar \\ \C &= \bits^{3\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $S \gets \bits^\secpar$

    $X := F(\key, R \oplus \ptxt)$

    $Y := F(\key, R \oplus S)$

    return $S \| X \| Y$

15. Suppose $F$ is a secure PRP with blocklength $\secpar$. Prove that the following encryption scheme is CPA-secure and write its decryption algorithm:

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^\secpar \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $S := R \oplus \ptxt$

    $X := F(\key, S) \oplus \ptxt$

    return $S \| X$

16. Let $F$ be a secure PRP with blocklength $\secpar$. Prove that the following encryption scheme is CPA-secure and write its decryption algorithm:

    $\begin{aligned} \K &= \bits^{2\secpar} \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key_1 \| \key_2,\ptxt)$:

    $R \gets \bits^\secpar$

    $X := F(\key_1, R)$

    $Y := F(\key_2, R \oplus \ptxt)$

    return $X \| Y$

    (Compare to exercise 8.21.)

17. $\star$ Let $F$ be a secure PRP with blocklength $\secpar$. Prove that the following encryption scheme is CPA-secure and write its decryption algorithm:

    $\begin{aligned} \K &= \bits^{\secpar} \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $X := F(\key, R)$

    $Y := F\bigl(\key, R \oplus F(\key,\ptxt) \bigr)$

    return $X \| Y$

18. $\star$ Let $F$ be a secure PRP with blocklength $\secpar$. Prove that the following encryption scheme is CPA-secure and write its decryption algorithm:

    $\begin{aligned} \K &= \bits^{2\secpar} \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key_1 \| \key_2,\ptxt)$:

    $R \gets \bits^\secpar$

    $X := F(\key_1, R)$

    $Y := F(\key_1, R \oplus \ptxt \oplus \key_2)$

    return $X \| Y$

19. In exercise 7.8 we defined security for a weak PRF. Prove that construction 8.3.1 is CPA-secure when its underlying block cipher $F$ is a weak PRF.

20. Let $G$ be a PRG with stretch $\ell$. Write the decryption algorithm for the following encryption scheme, then show that it is not CPA-secure, even if $G$ is a secure PRG:

    $\begin{aligned} \K &= \bits^{\secpar+\ell} \\ \M &= \bits^{\secpar+\ell} \\ \C &= \bits^{2\secpar+\ell} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $C := G(R) \oplus \key \oplus \ptxt$

    return $R \| C$

21. Let $F$ be a secure PRP with blocklength $\secpar$. Write the decryption algorithm for the following encryption scheme, then show that it is not CPA-secure, even if $F$ is a secure PRP:

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $\ctxt_1 := F(\key, R)$

    $\ctxt_2 := F(\key, R \oplus \ptxt)$

    return $\ctxt_1 \| \ctxt_2$

    (Compare to exercise 8.16.)

22. $\star$ Let $F$ be a PRP with blocklength $\secpar$. Write the decryption algorithm for the following encryption scheme, then show that it is not CPA-secure, even if $F$ is a secure PRP:

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{2\secpar} \\ \C &= \bits^{3\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt_1 \| \ptxt_2)$:

    $R \gets \bits^\secpar$

    $S := F(\key, R \oplus \ptxt_1)$

    $T := F(\key, \ptxt_1)$

    $C := F(\key, R \oplus \ptxt_1 \oplus \ptxt_2 \oplus T)$

    return $R\|S\|C$

23. Let $F$ be a secure PRP with blocklength $\secpar$. Write the decryption algorithm for the following encryption scheme. Is the scheme CPA-secure or not? Either give an attack or security proof.

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $\ctxt := F(\key, R \oplus \ptxt)$

    return $R \| \ctxt$

24. Let $F$ be a secure PRP with blocklength $\secpar$. Write the decryption algorithm for the following encryption scheme. Is the scheme CPA-secure or not? Either give an attack or security proof.

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $\ctxt := F(\key, R \oplus \ptxt) \oplus R$

    return $R \| \ctxt$

25. Let $F$ be a secure PRP with blocklength $\secpar$. Write the decryption algorithm for the following encryption scheme. Is the scheme CPA-secure or not? Either give an attack or security proof.

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $X := F(\key, R)$

    $Y := R \oplus \ptxt$

    return $X \| Y$

26. Let $F$ be a secure PRP with blocklength $\secpar$. Write the decryption algorithm for the following encryption scheme. Is the scheme CPA-secure or not? Either give an attack or security proof.

    $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{\secpar} \\ \C &= \bits^{2\secpar} \end{aligned}$

    $\qquad$

    $\Enc(\key,\ptxt)$:

    $R \gets \bits^\secpar$

    $X := F(\key, R)$

    $Y := R \oplus F(\key,\ptxt)$

    return $X \| Y$

27. Suppose a victim encrypts two different ciphertexts with the same IV, either by chance or through some systematic problem with their implementation. What can the adversary infer about the two plaintexts $\ldots$

    1. $\ldots$ if the victim is using CBC mode encryption?

    2. $\ldots$ if the victim is using CTR mode encryption?

28. Suppose that a single bit of a valid ciphertext is flipped during transmission. How does this bit-flip affect the result of decryption $\ldots$

    1. $\ldots$ in CBC mode?

    2. $\ldots$ in CTR mode?

29. Suppose we instantiate CBC mode not with a secure PRP but with OTP. In other words, replace each expression $F(\key,X)$ in the description of CBC mode with $\key \oplus X$. Show that the resulting encryption scheme is not CPA-secure.

30. Consider a victim who uses CBC mode with a fixed but uniformly chosen and secret IV.

    1. $\star$ Prove that if this victim encrypts plaintexts with distinct first blocks, then the resulting ciphertexts (excluding the IV) are pseudorandom. In other words, prove that the following two libraries are indistinguishable, if the underlying PRP $F$ is secure.

       $\key \gets \bits^\secpar$

       $\ctxt_0 \gets \bits^\secpar$ // static IV

       $\cpaenc(\ptxt_1 \| \cdots \| \ptxt_\ell)$:

       if $\ptxt_1 \in \mathcal{E}$: return $\myerr$

       $\mathcal{E} := \mathcal{E} \cup \{ \ptxt_1 \}$

       // CBC mode with IV = $\ctxt_0$

       for $i = 1$ to $\ell$:

       $\ctxt_i := F(\key, \ctxt_{i-1} \oplus \ptxt_i)$

       // does not return IV:

       return $\ctxt_1 \| \cdots \| \ctxt_\ell$

       $\indist$

       $\cpaenc(\ptxt_1 \| \cdots \| \ptxt_\ell)$:

       if $\ptxt_1 \in \mathcal{E}$: return $\myerr$

       $\mathcal{E} := \mathcal{E} \cup \{ \ptxt_1 \}$

       for $i = 1$ to $\ell$:

       $\ctxt_i \gets \bits^\secpar$

       return $\ctxt_1 \| \cdots \| \ctxt_\ell$

       These libraries use a guard condition to enforce that $\ptxt_1$ values are globally distinct.

    2. What happens if the static IV is revealed to the adversary, for example, by another subroutine that returns $\ctxt_0$? Are the resulting libraries also indistinguishable?

31. Output feedback mode (OFB) is defined below. Prove that it is CPA-secure if $F$ is a secure PRF:

    $\Enc(\key, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $R := \ctxt_0 \gets \bits^\secpar$

    for $i = 1$ to $\ell$:

    $R := F(\key, R)$

    $\ctxt_i := R \oplus \ptxt_i$

    return $\ctxt_0 \| \ctxt_1 \| \cdots \| \ctxt_\ell$

    $\Dec(\key, \ctxt_0 \| \cdots \| \ctxt_\ell)$:

    $R := \ctxt_0$

    for $i = 1$ to $\ell$:

    $R := F(\key, R)$

    $\ptxt_i := R \oplus \ctxt_i$

    return $\ptxt_1 \| \cdots \| \ptxt_\ell$

    

32. h Below is a variant of CBC encryption called propagating CBC (PCBC) mode. Give its decryption algorithm and prove that it is CPA-secure.

    $\Enc(\key, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $\ctxt_0 \gets \bits^\secpar$

    $\hl{\ptxt_0 := \bit0^\secpar}$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\key, \ctxt_{i-1} \oplus \ptxt_i \hl{\oplus \ptxt_{i-1}})$

    return $\ctxt_0 \| \ctxt_1 \| \cdots \| \ctxt_\ell$

    

    There is a “one-line proof” that uses the fact that regular CBC mode is secure.

33. Prove that if the IV is fixed to the all-zeros string $\bit 0^\secpar$, then CBC mode still has (computational) one-time secrecy (definition 5.3.2).

34. Prove that CTR mode (construction 8.5.4) is a CPA-secure encryption scheme, when its underlying block cipher $F$ is a secure PRF.

35. $\star$ Suppose a victim uses both CBC and CTR modes with the same key. Formalize an attack scenario in which a victim encrypts plaintexts of the adversary's choice, under the scheme (either CBC or CTR) of the adversary's choice, with a single key. Prove that the ciphertexts are pseudorandom in this scenario.

36. Consider the following unholy amalgamation of CBC and CTR modes:

    $\Enc(\key, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $\ctxt_0 \gets \bits^\secpar$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F\bigl(\key, [\ctxt_0 + i] \oplus \ptxt_i \bigr)$

    return $\ctxt_0 \| \ctxt_1 \| \cdots \| \ctxt_\ell$

    The expression “$[\ctxt_0+i] \oplus \ptxt_i$” means: treat $\ctxt_0$ as a $\secpar$-bit integer, add integer $i$ (with unsigned addition), treat the result as a $\secpar$-bit string, and xor with $\ptxt_i$. Describe the corresponding decryption algorithm and show that the scheme is not CPA-secure.

37. In each block of CBC encryption, we call $F$ on the result of an xor. In CBC decryption, we xor the result of a call to $F$. Show that the following modification of CBC encryption, in which the xor and $F$ are reversed, is not CPA-secure:

    $\Enc(\key, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $\ctxt_0 \gets \bits^\secpar$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\key, \ptxt_i ) \oplus \ctxt_{i-1}$

    return $\ctxt_0 \| \ctxt_1 \| \cdots \| \ctxt_\ell$

38. Some implementers may be unclear about the distinction between a key and an IV, and therefore may be hesitant to include the IV in the ciphertext. Suppose someone has modified CBC mode so that the IV is passed through the PRP before being included in the ciphertext:

    $\Enc(\key, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $\ctxt_0 \gets \bits^\secpar$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\key, \ptxt_i \oplus \ctxt_{i-1} )$

    $\hl{\ctxt^*_0 := F(\key,\ctxt_0)}$

    return $\hl{\ctxt^*_0} \| \ctxt_1 \| \cdots \| \ctxt_\ell$

    1. Show that the resulting scheme is no longer CPA-secure.

    2. What if an independent PRP key is used for this step? In other words, $\ctxt^*_0$ is computed as $F(\hl{\key'},\ctxt_0)$. Is this modification to CBC mode CPA-secure?

39. In CBC encryption, we use the previous ciphertext block as the IV for the next block. But we always use a new/fresh IV to begin each separate ciphertext. It seems reasonable to instead use the last block of the previous ciphertext as the IV for the next ciphertext: This is what you would get if you encrypted both plaintexts at the same time, and it would also save an extra block of communication.

    Unfortunately, this optimization is insecure. The attack scenario could be formalized as follows:

    $\key \gets \bits^\secpar$

    $V \gets \bits^\secpar$ // “next IV”

    $\cpaenc(\ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $\ctxt_0 :=V$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\key, \ptxt_i \oplus \ctxt_{i-1})$

    $V:= \ctxt_{\ell}$

    // do not include IV = $\ctxt_0$ in output

    return $\ctxt_1 \| \cdots \| \ctxt_\ell$

    Show that ciphertexts are no longer pseudorandom in this attack scenario.

40. We proved the security of CBC mode assuming its block cipher is a secure PRP. A two-round Feistel cipher is not a secure PRP. Despite this, prove that CBC mode is CPA-secure, when its underlying block cipher is a 2-round Feistel cipher (whose round function is a secure PRF). A Feistel cipher has blocklength of $2\secpar$ bits, and its round function needs $\secpar$ bits of input and output. Therefore the CBC mode in this problem has blocks of length $2\secpar$ bits.

41. Formally specify the decryption algorithm for CTR mode corresponding to the encryption algorithm in section 8.6 that supports plaintexts of arbitrary length.

42. Prove that CTR mode for arbitrary plaintext lengths (section 8.6) has CPA security. Try to structure your proof so it uses the fact that CTR mode for block-aligned plaintexts (construction 8.5.4) has CPA security.

43. Prove that augmenting CBC mode with any padding method (definition 8.6.1) results in a CPA-secure encryption scheme that supports arbitrary plaintext length. Try to structure your proof so it uses the fact that CPA mode for block-aligned plaintexts (construction 8.5.3) has CPA security.

44. Propose a padding method that works for strings of bits, not just strings of bytes.

45. CBC-MAC (construction 6.6.1) is defined for strings whose length is an exact multiple of the blocklength. Explain how to modify CBC-MAC to support strings of any length, and argue why the modification retains its security. CBC-MAC also has a disclaimer about fixed vs variable input lengths; how does this disclaimer change with your modification?

46. In PKCS#7 padding for example, $\textsf{Pad}(X)$ never outputs any string whose last byte is $\byte{ff}$. Design a padding scheme in which every possible (block-aligned) string is a possible output of $\textsf{Pad}$.

47. Prove that CBC mode does not achieve nonce-based CPA security if we treat the IV as a nonce.

48. Prove that CTR mode does not achieve nonce-based CPA security if we treat the IV as a nonce.

49. Consider the following nonce-based variant of CTR mode, in which nonces are from the set $\N = \bits^{\secpar/2}$, and plaintexts are restricted to be less than $2^{\secpar/2}$ blocks (so that a counter of blocks can be represented in $\secpar/2$ bits). Prove that this variant achieves nonce-based CPA security (definition 8.7.2).

    $\Enc(\key, \nonce, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    for $i = 1$ to $\ell$:

    $\ctxt_i := F\bigl(\key, \nonce \| i\bigr) \oplus \ptxt_i$

    return $\ctxt_1 \| \cdots \| \ctxt_\ell$

    The expression “$\nonce \| i$” means: Write $i$ as a $\secpar/2$-bit integer and append it to the string $\nonce$.

50. Consider the following nonce-based variant of CBC mode which uses a PRF to convert the nonce to an IV.

    $\Enc\Bigl(\key_1\|\key_2, \nonce, \ptxt_1 \| \cdots \| \ptxt_\ell\Bigr)$:

    $\ctxt_0 \hl{:= F(\key_1, \nonce)}$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\key_2, \ctxt_{i-1} \oplus \ptxt_i)$

    // $\ctxt_0$ not needed in the output

    return $\ctxt_1 \| \cdots \| \ctxt_\ell$

    Prove that this variant achieves nonce-based CPA security (definition 8.7.2). You may use the fact that standard CBC mode is CPA-secure as a randomized scheme.

51. In the previous exercise, we used separate PRF keys to derive the IV and for CBC encryption. Show that if the same key is used, the result is no longer secure:

    $\Enc(\key, \nonce, \ptxt_1 \| \cdots \| \ptxt_\ell)$:

    $\ctxt_0 := F(\hl{\key}, \nonce)$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\hl{\key}, \ctxt_{i-1} \oplus \ptxt_i)$

    // $\ctxt_0$ not needed in the output

    return $\ctxt_1 \| \cdots \| \ctxt_\ell$

    Show that this encryption scheme does not achieve nonce-based CPA security.

52. Continuing the theme of the last few exercises: It can be awkward to invoke a PRF/PRP with different keys. Below is a nonce-based variant of CBC mode that only invokes its PRP on a single key. Prove that this variant achieves nonce-based CPA security (definition 8.7.2):

    $\Enc\Bigl(\key_1 \| \key_2, \nonce, \ptxt_1 \| \cdots \| \ptxt_\ell\Bigr)$:

    $\ctxt_0 := F(\key_1, \nonce \hl{\oplus \key_2})$

    for $i = 1$ to $\ell$:

    $\ctxt_i := F(\key_1, \ctxt_{i-1} \oplus \ptxt_i)$

    return $\ctxt_0 \| \ctxt_1 \| \cdots \| \ctxt_\ell$

53. Let $\Sigma$ be an encryption scheme that achieves nonce-based CPA security, and has allowable nonces $\Sigma.\N = \bits^\secpar$. We can convert $\Sigma$ into a randomized encryption scheme by sampling the nonce uniformly for each call to $\Enc$. Formalize the resulting randomized encryption scheme and prove that it satisfies standard CPA security.

54. $\star$ Design a nonce-based encryption scheme that achieves nonce-based security, but which fails catastrophically when any nonce is repeated just twice. Use your own interpretation of “catastrophic failure,” but often this means that the adversary can recover the key.