▶ 9.3 Block Cipher Modes
Block ciphers suffer from a built-in shortcoming. If we feed a block cipher the same plaintext and the same key, it always yields the same ciphertext. This is what block ciphers do. By itself, this isn’t a vulnerability. It becomes a vulnerability when we encrypt data that has block-sized patterns in it.
For example, look at FIGURE 9.4. On the left, we have a plaintext image, originally rendered in three colors. On the right, we have the ciphertext after it was encrypted with a block cipher. The block cipher transformed the areas of uniform color into distinctive corduroy patterns. Each color in the plaintext yielded its own pattern in the ciphertext. Although this doesn’t yield a quality copy of the plaintext image, the ciphertext reveals the essence of the plaintext.
FIGURE 9.4 Encryption failure using a block cipher.
Courtesy of Dr. Richard Smith.
FIGURE 9.5 shows how this works. We encrypt the text “ABRACARDABRA” with a block cipher that works on 4-byte blocks. Given a particular key, a repeated block of four letters always encrypts to the same ciphertext. In this case, “ABRA” encrypts to the letters “HHIE” every time.
FIGURE 9.5 Identical blocks encrypt to identical ciphertext.
In the early days of encryption, people tried to avoid such patterns by restricting the data being sent. They might use an extra layer of encryption or encourage the radio clerks to rearrange messages to avoid patterns. This is hard to do effectively, because the clerk might change a message’s meaning when rearranging its text. In times of stress, when secrecy could be most important, a busy clerk might not rearrange messages at all and send several in a row with repeated patterns. Cryptanalysts would then focus on messages sent by hurried or careless clerks to crack the encryption.
The most effective way to avoid this problem is to build the solution into the encryption process. The solutions are called block cipher modes of operation (“modes” for short). Typically, a mode mixes data together from two separate encryptions. This scrambles the result and eliminates patterns in the ciphertext. This all takes place automatically when applying the mode. FIGURE 9.6 shows the result of applying a mixing mode while encrypting the smiley face.
FIGURE 9.6 Using a mixing mode with a block cipher.
Courtesy of Dr. Richard Smith.
Numerous modes have evolved over the years. Here we examine five common modes. Two of these modes are fairly well-behaved and are widely used. Two modes generate a key stream that we can use in a stream cipher.
■ Electronic codebook: encrypts block by block without mixing
■ Output feedback: generates a key stream
■ Counter: generates a key stream; recommended
■ Cipher feedback: a mix of stream and block cipher
■ Cipher block chaining: encrypts in blocks; recommended
These modes are specifically intended to keep information confidential. They do not, by themselves, protect information from modifications. In some cases, ciphertext errors or other changes affect only the specific bits modified. In other cases, small changes may damage entire blocks of decrypted plaintext.
When we encrypt data block by block, we call that the electronic codebook (ECB) mode. This term arises from the notion that a block cipher acts like a “codebook” in which every block of plaintext has a unique block of ciphertext associated with it. This is much like traditional codebooks published on paper that list plaintext messages and their corresponding code words.
We rarely use ECB mode because block-sized patterns in the plaintext will appear in the ciphertext. We only use ECB when encrypting data that fits within the cipher’s block size.
9.3.1 Stream Cipher Modes
We may use a block cipher to generate a key stream (following our discussion in Section 7.3.2). The simplest approach is the output feedback (OFB) mode, shown in FIGURE 9.7.
FIGURE 9.7 Key stream made with output feedback mode.
Note how it strongly resembles the key stream generator. (See Figure 7.12.) We use the block cipher to generate blocks of ciphertext that serve as the key stream. As shown earlier, we encrypt by applying xor to bits of the plaintext and corresponding bits of the key stream. To decrypt, we generate the matching key stream and apply xor to retrieve the plaintext.
Remember that we must never encrypt two messages with the same key stream. (See Section 8.2.) To avoid this, OFB introduces an extra data item, the initialization vector (IV). This is a nonce: We want it to be different from one plaintext message to another, and we don’t want it to be selected by a potential attacker. If we use the same key and IV for two different messages, we generate the same key stream.
When we use IVs, the ciphertext is always larger than the plaintext. Most applications can accommodate the larger ciphertext, although there are a few cases where the plaintext must match the size of the ciphertext. In those cases, we must use a mode that does not require a separate IV.
Ciphertext Errors
In Section 9.2, we explained how ciphertext errors affect block encryption. Errors behave differently when we use a mode. In OFB, the actual encryption and decryption use xor, so errors behave the same as in other stream ciphers. Modified or mistaken bits in the IV will change the key stream, and decryption will fail. Modified or mistaken ciphertext bits affect only corresponding plaintext bits. We do not recover the plaintext by running it through the block cipher. We see the same effects if we rearrange ciphertext data; every changed bit will decrypt incorrectly, but the rearrangement affects no other bits.
OFB in Practice
IVs aren’t exclusive to OFB; they are used in most modes. When we save the encrypted ciphertext, we must save the IV with it (FIGURE 9.8). Look at how we generate the key stream; we can’t reproduce the same key stream unless we keep the IV. We don’t encrypt the IV; we treat it.
FIGURE 9.8 Include the IV with the ciphertext when required.
FIGURE 9.9 shows OFB encrypting a series of data blocks: Plaintext 1, 2, and 3. We encrypt the initialization vector to produce the first block of key stream bits (Key Stream 1). We xor those bits with the first block of plaintext; then we use the block cipher on Key Stream 1 to generate the next block of key stream bits. We then apply xor to encrypt the next block of plaintext.
FIGURE 9.9 Mode encryption diagram: encrypting with OFB.
The process repeats until we have encrypted the entire ciphertext. Because we need the initialization vector to decrypt the ciphertext, we must include it with the ciphertext. To decrypt, we apply the same operations, except that we swap the plaintext with the ciphertext.
Note that Figures 9.7 and 9.9 use different ways to illustrate the same cipher mode. Figure 9.7 is a key stream diagram; it shows how the process generates a key stream. Figure 9.9 is a mode encryption diagram; it shows how successive blocks of plaintext and ciphertext interact to implement the mode. This second approach is used most often to illustrate modes. Not all modes generate a key stream independent of the message’s plaintext and ciphertext, so we can’t use the first style to portray every mode.
Weaknesses
OFB is a very simple mode, and we encounter security problems if we choose the IV poorly. If, by some chance, an IV appears as the output of the block cipher, then we produce a duplicated key stream.
For example, imagine that we use the value 123456 as our IV. Later, using the same key, we use a different IV in a second message. By coincidence, the second message’s key stream generates 123456 as one of its values. Look at what happens when we feed it back to the cipher: From that point on in the message, we use the same key stream as was used in the first message. Fortunately, this is unlikely to happen if the cipher’s block size is very large and we often change encryption keys.
Counter Mode
Counter (CTR) mode, like OFB, generates a key stream and applies xor to implement a stream cipher (FIGURE 9.10). Instead of using feedback, the counter mode encrypts successive values of a counter. This eliminates the OFB risk of an accidentally repeated IV and key stream. To avoid this, we never encrypt the same counter value with the same key. The initialization vector tells us where to start the counter.
FIGURE 9.10 Key stream with counter mode.
In practice, we can construct the counter in either of two ways. First, we can simply keep a running counter for every block we encrypt with a particular encryption key. We could start at a random value like 12345 and increment the value for each block we encrypt. If we encrypt 100 blocks, the counter will be 12444 when we encrypt the final block. We then use 12445 when we encrypt the 101st block.
For a different approach, we form the counter in two parts. A nonrepeating nonce provides the upper part. We increment the lower part. We may use either approach as long as we can guarantee not to reuse a counter value before we change to a different encryption key.
Because CTR is essentially a key stream generator that encrypts like a conventional stream cipher, it has the same ciphertext error properties as the OFB mode.
9.3.2 Cipher Feedback Mode
The cipher feedback (CFB) mode, shown in FIGURE 9.11, combines properties of stream ciphers and block ciphers. We generate a key stream one block at a time and combine it with the text using xor. Instead of feeding back the block cipher’s output, CFB feeds back the actual ciphertext block. CFB doesn’t face the same risk of repeated IVs that we have with OFB. Because each block of encryption depends on both the key stream and the message data, CFB won’t repeat the key stream unless we reencrypt exactly the same data with exactly the same IV.
FIGURE 9.11 Mode encryption diagram for cipher feedback mode.
Although we encrypt complete blocks of data to generate the key stream, the plaintext does not have to fit into an integral number of blocks. When we reach the final block, we may encrypt the remaining plaintext and discard any extra key stream bits.
Ciphertext Errors
Because CFB feeds the ciphertext through the block cipher to decrypt it, ciphertext errors affect it differently. Remember what happens if we change a single bit of a block cipher’s input: It affects the entire output block.
Note how CFB ciphertext affects the decrypted plaintext: Each block gets used twice. First, we xor the ciphertext with the key stream. Next, we use the ciphertext as input to the block cipher to produce the next block of key stream.
A single bit error produces two separate changes to the plaintext. First, the corresponding plaintext bit is inverted (as in a stream cipher error). Second, the next block of plaintext is completely scrambled. Thus, we see error propagation because this single error in the ciphertext damages additional plaintext when we decrypt. The error propagation affects only the following block.
If we rearrange ciphertext blocks encrypted with CFB, we get different results than with a straight block cipher or with a stream cipher. As noted, a misplaced block decrypts incorrectly and causes the block following it to decrypt incorrectly. However, if all subsequent blocks appear in the right order, they will all decrypt correctly. Because of this, CFB is called a “self-synchronizing” cipher; there is a limit to error propagation during decryption, after which the ciphertext decrypts into the correct plaintext. For example, let’s switch ciphertext blocks 2 and 3 before decryption and see what happens:
■ We retrieve plaintext block 1 correctly from the IV and from ciphertext block 1.
■ We generate key stream 2 correctly from ciphertext block 1.
■ We incorrectly generate plaintext block 2. We xor key stream 2 with the misplaced ciphertext block 3. This yields nonsense.
■ We incorrectly generate key stream 3. We decrypt the misplaced ciphertext block 3, which actually yields key stream 4. We use it in the place of key stream 3.
■ We incorrectly generate plaintext block 3. We xor the misplaced key stream 4 with misplaced ciphertext block 2. This yields nonsense.
■ We incorrectly generate key stream 4. We decrypt the misplaced ciphertext block 2, which actually yields key stream 3. We use it in the place of key stream 4.
■ We incorrectly generate plaintext block 4. We xor the misplaced key stream 3 with the properly placed ciphertext block 4.
■ Output returns to normal with plaintext block 5, because the undamaged ciphertext block 4 generates the correct key stream.
Thus, if we swap two adjacent ciphertext blocks, we see errors in three plaintext blocks when we decrypt. The same is true if we change one or more bits in two adjacent ciphertext blocks. The decryption resynchronizes and yields correct plaintext one block past the last ciphertext error.
9.3.3 Cipher Block Chaining
Last, and certainly not least, is the cipher block chaining (CBC) mode (FIGURE 9.12). CBC is one of the oldest and most widely used cipher modes. Unlike the other modes examined, this one is block-oriented. To use this mode, the plaintext must be a multiple of the cipher’s block size. If it is shorter, we must add padding.
FIGURE 9.12 Mode encryption diagram for cipher block chaining mode.
CBC encryption involves two steps. First, we scramble the plaintext by combining each plaintext block with the previous ciphertext block. As shown in the figure, we use xor to combine the plaintext and ciphertext. We combine the first plaintext block, which has no previous ciphertext, with the IV. The second step is block encryption. Its output provides the ciphertext block. We also use this ciphertext block when we encrypt the next plaintext block.
FIGURE 9.13 illustrates CBC decryption using a mode decryption diagram. We start by decrypting the first ciphertext block. Unlike other modes, we actually use the block cipher’s decryption procedure to decrypt the ciphertext. We combine the result with the IV to recover the first plaintext block. For subsequent blocks, we first decrypt the ciphertext block, and then we xor the result with the previous ciphertext block.
FIGURE 9.13 Mode decryption diagram for cipher block chaining.
Like CFB mode, we use each ciphertext block twice when decrypting. Unlike CFB, both the plaintext and the ciphertext must fit into an integral number of blocks.
Ciphertext Errors
CBC has similar error propagation and self-synchronizing properties to CFB. A single bit error in a ciphertext block will affect both the current block and the next block. Subsequent error-free blocks will decrypt correctly. If we rearrange ciphertext blocks, we lose the corresponding plaintext block contents, plus one block following the ones that moved.
9.3.4 Block Mode Standards
There are many standards organizations at the industry, national, and international level that publish cryptographic standards. In the United States, the federal standards body is NIST, and we will focus on NIST block mode standards.
The five modes introduced in this section have been standardized and used since the early 2000s; the earliest four date back to the introduction of DES in the 1970s. NIST publishes their recommended implementation in Special Publication 800-38A.
Newer modes have arisen for applications less suited for the traditional modes. Several modes apply to data authentication, and some combine authentication with encryption. An important mode, XTS, encrypts large storage devices. There are also modes for key wrapping and for encryption that preserves data formatting. Here is a summary of the NIST publications:
■ SP 800-38A: Block encryption modes ECB, CFB, OFB, CBC, CTR
■ SP 800-38B: cipher-based message authentication code (CMAC) mode for authentication
■ SP 800-38C: counter with cipher block chaining-message authentication code (CCM) mode for authentication and encryption
■ SP 800-38D: Galois/Counter Mode (GCM) and Galois Message Authentication Code (GMAC) for authenticated encryption
■ SP 800-38E: XTS mode for mass storage encryption
■ SP 800-38F: Key-wrapping methods
■ SP 800-38G: Format-preserving encryption