Return to Table of Contents

Block ciphers / PRPs can only act on a single block (element of {0,1}^blen) of data at a time. In the previous section we showed at least one way to use a PRP (in fact, a PRF sufficed) to achieve CPA-secure encryption of a single block of data. This prompts the question, can we use PRFs/PRPs to encrypt data that is longer than a single block?

A block cipher mode specifies how to handle data that spans multiple blocks. Block cipher modes are where block ciphers really shine. There are modes for (CPA-secure) encryption, modes for data integrity, modes that achieve both privacy and integrity, modes for hard drive encryption, modes that gracefully recover from errors in transmission, modes that are designed to croak upon transmission errors, and so on. There is something of a cottage industry of clever block cipher modes, each with their own unique character and properties. Think of this chapter as a tour through the most common modes.

9.1: Common Modes

In this section, we will consider encryption modes for long plaintexts. As usual, blen will denote the blocklength of the block cipher F. In our diagrams, we’ll write F_k as shorthand for F(k,·). When m is the plaintext, we will write m = m₁m₂ · · · m_ℓ, where each m_i is a single block (so ℓ is the length of the plaintext measured in blocks). For now, we will assume that m is an exact multiple of the block length.

ECB: Electronic Codebook

(NEVER NEVER USE THIS! NEVER‼)

The most obvious way to use a block cipher to encrypt a long message is to just apply the block cipher independently to each block. The only reason to know about this mode is to know never to use it (and to scold anyone who does). It can’t be said enough times: never use ECB mode! It does not provide security of encryption; can you see why?

Construction 9.1: ECB Mode

CBC: Cipher Block Chaining

CBC is by far the most common block cipher mode in everyday use. It is used primarily to achieve CPA (CPA$) security, but we will see later that a variant can also be used for data integrity properties.

Since CBC mode results in CPA-secure encryption, it’s no surprise that its encryption algorithm is randomized. In particular, CBC mode specifies that a random block is chosen, which is called the initialization vector (IV). The IV is included in the output, and as a result, encrypting ℓ blocks under CBC mode results in ℓ + 1 blocks of output.

Construction 9.2: CBC Mode

CTR: Counter

Counter mode, like CBC mode, begins with the choice of a random IV block r ← {0,1}^blen. Then the sequence

is used as a long one-time pad to mask the plaintext. Here, we interpret a block as an element of ℤ_2blen, so addition is performed modulo 2^blen.

Counter mode has a few nice features that lead many designers to favor it over CBC:

• Both encryption and decryption use F only in the forward direction (the decryption algorithm for CTR is left as an exercise). In particular, this means that F can be a PRF that is not a PRP. Modes with this property are sometimes called stream cipher modes. They can be easily adapted to support plaintexts that are not an exact multiple of the blocklength.
• It is one of the few modes for which encryption can be parallelized. That is, once the IV has been chosen, the ith block of ciphertext can be computed without first computing the previous i − 1 blocks.

Construction 9.3: CTR Mode

OFB: Output Feedback

OFB mode is another stream cipher mode that uses F only in the forward direction. As with the other modes, a random IV block r is chosen at the beginning. Then the sequence

is used as a one-time pad to mask the plaintext. The name “output feedback” comes from this idea of repeatedly feeding the output of F into itself.

OFB is not nearly as widespread as CBC or CTR, but we include it here for self-serving reasons: it has the easiest security proof!

Construction 9.4: OFB Mode

9.2: CPA Security for Variable-Length Plaintexts

Block cipher modes allow us to encrypt a plaintext consisting of any number of blocks. In these modes, the length of the ciphertext depends on the length of the plaintext. So in that regard, these encryption schemes do not hide all information about the plaintext — in particular, they do not hide its length! We would run into problems trying to prove CPA security of these modes with respect to plaintext space ? = ({0,1}^blen)∗. A successful distinguisher would break CPA security simply by choosing m_L and m_R of different lengths (measured in blocks) and then inspecting the length of the resulting ciphertext.

Leaking the length of the plaintext (measured in blocks) seems like a rather minor concession. But as we just described, it is necessary to modify our very conservative security definitions to allow any leakage at all.

For CPA security, we argued that if a distinguisher queries the CHALLENGE subroutine with plaintexts of different length in the CPA libraries, we cannot expect the libraries to be indistinguishable. The easiest way to avoid this situation is to simply insist that |m_L| = m_R|. This would allow the adversary to make the challenge plaintexts differ in any way of his/her choice, except in their length. We can interpret the resulting security definition to mean that the scheme would hide all partial information about the plaintext apart from its length.

From now on, when discussing encryption schemes that support variable-length plaintexts, CPA security will refer to the following updated libraries:

In the definition of CPA$ security (pseudorandom ciphertexts), the ℒ_cpa$-rand library responds to queries with uniform responses. Since these responses must look like ciphertexts, they must have the appropriate length. For example, for the modes discussed in this chapter, an ℓ-block plaintext is expected to be encrypted to an (ℓ + 1)-block ciphertext. So, based on the length of the plaintext that is provided, the library must choose the appropriate ciphertext length. We are already using Σ.? to denote the set of possible ciphertexts of an encryption scheme Σ. So let’s extend the notation slightly and write Σ.?(ℓ) denote the set of possible ciphertexts for plaintexts of length ℓ. Then when discussing encryption schemes supporting variable-length plaintexts, CPA$ security will refer to the following libraries:

In the exercises, you are asked to prove that, with respect to these updated security definitions, CPA$ security implies CPA security as before.

Don’t Take Length-Leaking for Granted!

We have just gone from requiring encryption to leak no partial information to casually allowing some specific information to leak. Let us not be too hasty about this!

If we want to truly support plaintexts of arbitrary length, then leaking the length is in fact unavoidable. But that doesn’t mean it is consequence-free. By observing only the length of encrypted network traffic, many serious attacks are possible. Here are several examples:

• When accessing Google maps, your browser receives many image tiles that comprise the map that you see. Each image tile has the same pixel dimensions. However, they are compressed to save resources, and not all images compress as significantly as others. Every region of the world has its own rather unique “fingerprint” of imagetile lengths. So even though traffic to and from Google maps is encrypted, the sizes of the image tiles are leaked. This can indeed be used to determine the region for which a user is requesting a map.¹ The same idea applies to auto-complete suggestions in a search form.

• Variable-bit-rate (VBR) encoding is a common technique in audio/video encoding. When the stream is carrying less information (e.g., a scene with a fixed camera position, or a quiet section of audio), it is encoded at a lower bit rate, meaning that each unit of time is encoded in fewer bits. In an encrypted video stream, the changes in bit rate are reflected as changes in packet length. When a user is watching a movie on Netflix or a Youtube video (as opposed to a live event stream), the bit-rate changes are consistent and predictable. It is therefore rather straight-forward to determine which video is being watched, even on an encrypted connection, just by observing the packet lengths.
• VBR is also used in many encrypted voice chat programs. Attacks on these tools have been increasing in sophistication. Initially, it was shown possible to identify speakers (from a set of candidates). Later, researchers developed techniques that could determine the language being spoken. Eventually, when combined with linguistic models, it was shown possible to even identify individual words to some extent!

It’s worth emphasizing again that none of these attacks involve any attempt to break the encryption. The attacks rely solely on the fact that encryption leaks the length of the plaintexts.

9.3: security of OFB Mode

In this section we will prove that OFB mode has pseudorandom ciphertexts (when the blocklength is blen = λ bits). OFB encryption and decryption both use the forward direction of F, so OFB provides security even when F is not invertible. Therefore we will prove security assuming F is simply a PRF.

Claim 9.5

OFB mode (Construction 9.4) has CPA$ security, if its underlying block cipher F is a secure PRF with parameters in = out = λ.

Proof

The general structure of the proof is very similar to the proof used for the PRF-based encryption scheme in the previous chapter (Construction 8.4). This no coincidence: if OFB mode is restricted to plaintexts of a single block, we obtain exactly Construction 8.4!

The idea is that each ciphertext block (apart from the IV) is computed as c_i := r ⊕ m_i. By the one-time pad rule, it suffices to show that the r values are independently pseudorandom. Each r value is the result of a call to the PRF. These PRF outputs will be independently pseudorandom only if all of the inputs to the PRF are distinct. In OFB mode, we use the output r of a previous PRF call as input to the next, so it is highly unlikely that this PRF output r matches a past PRF-input value. To argue this more precisely, the proof includes hybrids in which r is chosen without replacement (before changing r back to uniform sampling).

The formal sequence of hybrid libraries is given below:

The starting point is ℒ^OFB_cpa$-real, shown here with the details of OFB filled in.

The statements pertaining to the PRF F have been factored out in terms of ℒ^F_prf-real.

ℒ^F_prf-real has been replaced by ℒ^F_prf-rand. By the PRF security of F, the change is indistinguishable.

Next, all of the statements that involve sampling values for the variable r are factored out in terms of the ℒ_samp-L library from Lemma 4.7:

ℒ_samp-L is then replaced by ℒ_samp-R. By Lemma 4.7, this change is indistinguishable:

Arguments to QUERY are never repeated, so the middle library can be significantly simplified:

Next, ℒ_samp-R is replaced by ℒ_samp-L. By Lemma 4.7, this change is indistinguishable:

Subroutine calls to QUERY and SAMP are inlined:

Finally, the one-time pad rule is applied within the for-loop (omitting some common steps). Note that in the previous hybrid, each value of r is used only once as a one-time pad. The i = 0 case has also been absorbed into the for-loop. The result is ℒ^OFB_cpa$-rand, since OFB encrypts plaintexts of ℓ blocks into ℓ + 1 blocks.

The sequence of hybrids shows that ℒ^OFB_cpa$-real ≋ ℒ^OFB_cpa$-rand, and so OFB mode has pseudorandom ciphertexts.

We proved the claim assuming F is a PRF only, since OFB mode does not require F to be invertible. Since we assume a PRF with parameters in = out = λ, the PRP switching lemma (Lemma 7.3) shows that OFB is secure also when F is a PRP with blocklength n = λ.

9.4: Padding & Ciphertext Stealing

So far we have assumed that all plaintexts are exact multiples of the blocklength. But data in the real world is not always so accommodating. How are block ciphers used in practice with data that has arbitrary length?

Padding

While real-world data does not always come in multiples of the blocklength (typically 128 or 256 bits), it does almost always come in multiples of bytes (8 bits). So for now let us assume that the data is represented as bytes. We will write bytes in hex, for example 8f.

The most natural way to deal with plaintexts of odd lengths is to add some null bytes (byte 00, consisting of all zeroes) to fill out the last block. However, this leads to problems when decrypting: how can one distinguish between null bytes added for padding and null bytes that were part of the original plaintext?

A padding scheme is a method to encode arbitrary-length data into data that is a multiple of the blocklength. Importantly, the padding scheme must be reversible! Many padding schemes are in use, and we show just one below.

The ANSI X.923 standard defines a padding scheme, for block length 128 bits = 16 bytes. In the algorithms below, |x| refers to the length of string x, measured in bytes, not bits.

Construction 9.6

Example

Below are some blocks (16 bytes) with valid and invalid X.923 padding:

Note what happens in PAD(x) when x is already a multiple of 16 bytes in length. In that case, an additional 16 bytes are added — 00 · · · 00 10 , since 10 is the hex encoding of 16. This is necessary because the unpadded x might already end with something that looks like valid ANSI X.923 padding!

With a padding scheme available, one simply pads a string before encrypting and unpads the result after decrypting.

Ciphertext Stealing

Another approach with a provocative name is ciphertext stealing (CTS, if you are not yet tired of three-letter acronyms), which results in ciphertexts that are not a multiple of the blocklength. A plaintext of s bits will be encrypted to a ciphertext of blen + s bits, where blen is the length of the extra IV block.

As an example, we will show how ciphertext stealing applies to CBC mode. Suppose the blocklength is blen and the last plaintext block m_ℓ has blen − j bits. We extend m_ℓ with j zeroes and perform CBC encryption as usual.

Focus on the last j bits of block c_{ℓ – 1}. Because m_ℓhas been padded with zeroes, these final j bits of c_{ℓ – 1} are also the last j bits of F^-1(k,c_ℓ), as shown in the diagram below.

Now imagine if we simply threw away the last j bits of c_{ℓ – 1}. These bits are somewhat redundant, so the decryption procedure could reconstruct the “missing” j bits via F^-1(k,c_ℓ). Furthermore, the fact that the ciphertext would be j bits shorter than a full block is a signal about how many bits should be treated in this special way (and how long the plaintext should be).

In general, the ciphertext stealing technique is to simply remove a carefully selected portion of the ciphertext, in a way that signals the original length of the plaintext and allows for correct decryption. For CBC mode, the appropriate bits to remove are the last j bits of the next-to-last ciphertext block. When decrypting, the last j bits of F⁻¹(k,c_ℓ) can be appended to c_ℓ−1 and decryption can proceed as usual. The exercises ask you to prove the security of CBC mode with ciphertext stealing.

It is convenient in an implementation for the boundaries between blocks to be in predictable places. For that reason, it is slightly awkward to remove j bits from the middle of the ciphertext, as we have done here. So in practice, the last two blocks of the ciphertext are typically interchanged. For the example above, the resulting ciphertext (after ciphertext stealing) would be:

That way, all ciphertext blocks except the last one are the full blen bits long, and the boundaries between blocks appear consistently every blen bits. This optimization does add some significant edge cases to any implementation. One must also decide what to do when the plaintext is an exact multiple of the blocklength — should the final two ciphertext blocks be swapped even in this case? Below we present an implementation of ciphertext stealing (CTS) that does not swap the final two blocks in this case. This means that it collapses to plain CBC mode when the plaintext is +an exact multiple of the block length.

Construction 9.7: CBC-CTS)

Exercises:

9.1: Prove that a block cipher in ECB mode does not provide CPA security. Describe a distinguisher and compute its advantage.

9.2: Describe OFB decryption mode.

9.3: Describe CTR decryption mode.

9.4: CBC mode:

(a). In CBC-mode encryption, if a single bit of the plaintext is changed, which ciphertext blocks are affected (assume the same IV is used)?

(b). In CBC-mode decryption, if a single bit of the ciphertext is changed, which plaintext blocks are affected?

9.5: Prove that CPA$ security for variable-length plaintexts implies CPA security for variable length plaintexts. Where in the proof do you use the fact that |m_L| = |m_R|?

9.6: Suppose that instead of applying CBC mode to a block cipher, we apply it to one-time pad. In other words, we replace every occurrence of F(k,m) with k ⊕ m in the code for CBC encryption. Show that the result does not have CPA security. Describe a distinguisher and compute its advantage.

9.7: Prove that there is an attacker that runs in time O(2^λ/2) and that can break CPA security of CBC mode encryption with constant probability.

9.8: Below are several block cipher modes for encryption, applied to a PRP F with blocklength blen = λ. For each of the modes

• Describe the corresponding decryption procedure
• Show that the mode does not have CPA-security.  That means describe a distinguisher and compute its advantage.

Mode (a) is similar to CBC, except the XOR happens after, rather than before, the blockcipher application. Mode (c) us essentially the same as CBC decryption.

9.9: Suppose you observe a CBC ciphertext and two of its blocks happen to be identical. What can you deduce about the plaintext? State some non-trivial property of the plaintext that doesn’t depend on the encryption key.

9.10: The CPA$-security proof for CBC encryption has a slight complication compared to the proof of OFB encryption. Recall that the important part of the proof is arguing that all inputs to the PRF are distinct.

In OFB, outputs of the PRF were fed directly into the PRF as inputs. The adversary had no influence over this process, so it wasn’t so bad to argue that all PRF inputs were distinct (with probability negligibly close to 1).

By contrast, CBC mode takes an output block from the PRF, XOR’s it with a plaintext block (which is after all chosen by the adversary), and uses the result as input to the next PRF call. This means we have to be a little more careful when arguing that CBC mode gives distinct inputs to all PRF calls (with probability negligibly close to 1).

(a). Prove that the following two libraries are indistinguishable:

(b). Using part (a), and the security of the underlying PRF, prove the CPA$-security of CBC mode.

Hint: In ℒ_right, let R correspond to the set of all inputs sent to the PRF. Let m correspond to the next plaintext block. Instead of sampling r (the output of the PRF) uniformly as in ℒ_left, we sample r so that r ⊕ x has never been used as a PRF-input before. This guarantees that the next PRF call will be on a “fresh” input.

Note: Appreciate how important it is that the adversary chooses plaintext block m before “seeing” the output r from the PRF (which is included in the ciphertext).

9.11: Prove that CTR mode achieves CPA security. As in the previous problem, you will have to establish distinctness of the PRF inputs in a new way. But this time it’s up to you.

9.12: Let F be a secure PRF with out = in = λ and let F⁽²⁾ denote the function F⁽²⁾(k,r) = F(k,F(k,r)).

(a). Prove that F⁽²⁾ is also a secure PRF.

(b). What if F is a secure PRP with blocklength blen? Is F⁽²⁾ also a secure PRP?

9.13: In this question we investigate the subtleties of initialization vectors and how their choice contributes to CPA security. In CBC mode (indeed, in every mode discussed here), the IV is included in the ciphertext, so it is something that the adversary eventually sees anyway.

(a). Describe a modification to the CPA or CPA$ security definition that allows the adversary to choose the IV that is used. Then show that no such security is provided by CBC mode. In other words, describe a distinguisher for the new libraries you defined, and compute its advantage.

(b). Describe a modification to the CPA or CPA$ security definition that allows the adversary to choose the IV that is used, but is not allowed to re-use an IV. Does CBC mode satisfy this kind of security? If so, give a proof for your new kind of security notion; if not, then describe a distinguisher and compute its advantage.

(c). Describe a modification to the CPA or CPA$ security definition in which the library chooses IVs uniformly (as in the standard security definition) but allows the adversary to see in advance what the next IV will be, before choosing the plaintext. Does CBC mode satisfy this kind of security? If so, give a proof for your new kind of security notion; if not, then describe a distinguisher and compute its advantage.

In these problems, you are being asked to come up with a new security definition, so you must modify the libraries that comprise the security definition. There could be many “correct” ways to do this. All that matters is that the new interface of the libraries gives the calling program a way to do the things that are specified. In part (c) you might even want to add another subroutine to the interface.

9.14: The previous problem shows that the IV in CBC mode encryption is somewhat fragile. Suppose that in order to protect the IV, we send it through the block cipher before including it in the ciphertext. In other words, we modify CBC encryption as follows:

To decrypt, we first compute c₀ := F^-1(k,c’₀) and proceed as in usual CBC decryption.

(a). Show that the resulting scheme no longer satisfies CPA security. Describe a successful distinguisher and compute its advantage.

(b). Show that if we encrypt the IV c₀ with an independently chosen key k’, the resulting scheme does in fact still achieve CPA$ security. Your security proof can use the fact that standard CBC encryption has CPA$ security.

9.15: Describe how to extend CTR and OFB modes to deal with plaintexts of arbitrary length (without using padding). Why is it so much simpler than CBC ciphertext stealing?

9.16: The following technique for ciphertext stealing in CBC was proposed in the 1980s and was even adopted into commercial products. Unfortunately, it’s insecure.

Suppose the final plaintext block m_ℓ is blen − j bits long. Rather than padding the final block with zeroes, it is padded with the last j bits of ciphertext block c_ℓ−1. Then the padded block m_ℓ is sent through the PRP to produce the final ciphertext block c_ℓ. Since the final j bits of c_ℓ−1 are recoverable from c_ℓ, they can be discarded.

If the final block of plaintext is already blen bits long, then standard CBC mode is used.

Show that the scheme does not satisfy CPA$ security. Describe a distinguisher and compute its advantage.

Hint: ask for several encryptions of plaintexts whose last block is blen − 1 bits long.

9.17: Prove that any CPA-secure encryption remains CPA-secure when augmented by padding the input.

9.18: Prove that CBC with ciphertext stealing has CPA$ security. You may use the fact that CBC mode has CPA$ security when restricted to plaintexts whose length is an exact multiple of the blocklength (i.e., CBC mode without padding or ciphertext stealing).

Hint: Let CBC denote standard CBC mode restricted to plaintext space ? = ({0,1}^blen)^∗, and let CBC-CTS denote CBC mode with ciphertext stealing (so ? = {0,1}^∗). Observe that it is easy to implement a call to ℒ^CBC-CTS_cpa$-real by a related call to ℒ^CBC_cpa$-real plus a small amount of additional processing.

9.19: Propagating CBC (PCBC) mode refers to the following variant of CBC mode:

(a). Describe PCBC decryption.

(b). Assuming that standard CBC mode has CPA$-security (for plaintexts that are exact multiple of the block length), prove that PCBC mode also has CPA$-security (for the same plaintext space).

Hint: Write PCBC encryption using plain CBC encryption as a subroutine.

(c). Consider the problem of adapting CBC ciphertext stealing to PCBC mode. Suppose the final plaintext block m_ℓ has blen − j bits, and we pad it with the final j bits of the previous plaintext block m_ℓ−1. Show that discarding the last j bits of c_ℓ−1 still allows for correct decryption and results in CPA$ security.

Hint: See Exercise 9.18.

(d). Suppose the final plaintext block is padded using the final j bits of the previous ciphertext block c_ℓ−1. Although correct decryption is still possible, the construction is no longer secure. Show an attack violating the CPA$-security of this construction. Why doesn’t the proof approach from part (c) work?

Hint: Ask for several encryptions of plaintexts whose last block is 1 bit long.