The natural manner for using a block cipher is to break a long piece of plaintext into appropriately sized blocks of plaintext and process each block separately with the encryption function $E_K$. This is known as the electronic codebook (ECB) mode of operation. The plaintext $P$ is broken into smaller chunks $P=[P_1\text{,}{P}_2\text{,}\cdots \text{,}{P}_L]$ and the ciphertext is

where $C_j=E_K(P_j)$ is the encryption of $P_j$ using the key $K$.

There is a natural weakness in the ECB mode of operation that becomes apparent when dealing with long pieces of plaintext. Say an adversary Eve has been observing communication between Alice and Bob for a long enough period of time. If Eve has managed to acquire some plaintext pieces corresponding to the ciphertext pieces that she has observed, she can start to build up a codebook with which she can decipher future communication between Alice and Bob. Eve never needs to calculate the key $K$; she just looks up a ciphertext message in her codebook and uses the corresponding plaintext (if available) to decipher the message.

This can be a serious problem since many real-world messages consist of repeated fragments. E-mail is a prime example. An e-mail between Alice and Bob might start with the following header:

Date: Tue, 29 Feb 2000 13:44:38 -0500 (EST)

The ciphertext starts with the encrypted version of “Date: Tu”. If Eve finds that this piece of ciphertext often occurs on a Tuesday, she might be able to guess, without knowing any of the plaintext, that such messages are e-mail sent on Tuesdays. With patience and ingenuity, Eve might be able to piece together enough of the message’s header and trailer to figure out the context of the message. With even greater patience and computer memory, she might be able to piece together important pieces of the message.

Another problem that arises in ECB mode occurs when Eve tries to modify the encrypted message being sent to Bob. She might be able to extract important portions of the message and use her codebook to construct a false ciphertext message that she can insert in the data stream.

One method for reducing the problems that occur in ECB mode is to use chaining. Chaining is a feedback mechanism where the encryption of a block depends on the encryption of previous blocks.

In particular, encryption proceeds as

while decryption proceeds as

where $C_0$ is some chosen initial value. As usual, $E_K$ and $D_K$ denote the encryption and decryption functions for the block cipher.

Thus, in CBC mode, the plaintext is XORed with the previous ciphertext block and the result is encrypted. Figure 6.1 depicts CBC.

Figure 6.1 Cipher Block Chaining Mode.

The initial value $C_0$ is often called the initialization vector, or the IV. If we use a fixed value for $C_0$, say $C_0=0$, and ever have the same plaintext message, the result will be that the resulting ciphertexts will be the same. This is undesirable since it allows the adversary to deduce that the same plaintext was created. This can be very valuable information, and can often be used by the adversary to infer the meaning of the original plaintext.

In practice, this problem is handled by always choosing $C_0$ randomly and sending $C_0$ in the clear along with the first ciphertext $C_1$. By doing so, even if the same plaintext message is sent repeatedly, an observer will see a different ciphertext each time.

One of the problems with both the CBC and ECB methods is that encryption (and hence decryption) cannot begin until a complete block of plaintext data is available. The cipher feedback mode operates in a manner that is very similar to the way in which LFSRs are used to encrypt plaintext. Rather than use linear recurrences to generate random bits, the cipher feedback mode is a stream mode of operation that produces pseudorandom bits using the block cipher $E_K$. In general, CFB operates in a $k\text{-bit}$ mode, where each application produces $k$ random bits for XORing with the plaintext. For our discussion, however, we focus on the eight-bit version of CFB. Using the eight-bit CFB allows one 8-bit piece of message (e.g., a single character) to be encrypted without having to wait for an entire block of data to be available. This is useful in interactive computer communications, for example.

For concreteness, let’s assume that our block cipher encrypts blocks of 64 bits and outputs blocks of 64 bits (the sizes of the registers can easily be adjusted for other block sizes). The plaintext is broken into 8-bit pieces: $P=[P_1\text{,}{P}_2\text{,}\dots ]$, where each $P_j$ has eight bits, rather than the 64 bits used in ECB and CBC. Encryption proceeds as follows. An initial 64-bit $X_1$ is chosen. Then for $j=1\text{,}2\text{,}3\text{,}\dots$, the following is performed:

where $L_8(X)$ denotes the 8 leftmost bits of $X$, $R_{56}(X)$ denotes the rightmost 56 bits of $X$, and $X\parallel Y$ denotes the string obtained by writing $X$ followed by $Y$. We present the CFB mode of operation in Figure 6.2.

Figure 6.2 Cipher Feedback Mode.

Decryption is done with the following steps:

We note that decryption does not involve the decryption function, $D_K$. This would be an advantage of running a block cipher in a stream mode in a case where the decryption function for the block cipher is slower than the encryption function.

Let’s step through one round of the CFB algorithm. First, we have a 64-bit register that is initialized with $X_1$. These 64 bits are encrypted using $E_K$ and the leftmost eight bits of $E_K(X_1)$ are extracted and XORed with the 8-bit $P_1$ to form $C_1$. Then $C_1$ is sent to the recipient. Before working with $P_2$, the 64-bit register $X_1$ is updated by extracting the rightmost 56 bits. The eight bits of $C_1$ are appended on the right to form $X_2=R_{56}(X_1)\parallel C_1$. Then $P_2$ is encrypted by the same process, but using $X_2$ in place of $X_1$. After $P_2$ is encrypted to $C_2$, the 64-bit register is updated to form

By the end of the 8th round, the initial $X_1$ has disappeared from the 64-bit register and $X_9=C_1\parallel C_2\parallel \cdots \parallel C_8$. The $C_j$ continue to pass through the register, so for example $X_{20}=C_{12}\parallel C_{13}\parallel \cdots \parallel C_{19}$.

Note that CFB encrypts the plaintext in a manner similar to one-time pads or LFSRs. The key $K$ and the numbers $X_j$ are used to produce binary strings that are XORed with the plaintext to produce the ciphertext. This is a much different type of encryption than the ECB and CBC, where the ciphertext is the output of DES.

In practical applications, CFB is useful because it can recover from errors in transmission of the ciphertext. Suppose that the transmitter sends the ciphertext blocks $C_1\text{,}{C}_2\text{,}\dots \text{,}{C}_k\text{,}\dots$, and $C_1$ is corrupted during transmission, so that the receiver observes ${\tilde{C}}_1\text{,}{C}_2\text{,}\dots$. Decryption takes ${\tilde{C}}_1$ and produces a garbled version of $P_1$ with bit errors in the locations that ${\tilde{C}}_1$ had bit errors. Now, after decrypting this ciphertext block, the receiver forms an incorrect $X_2$, which we denote ${\tilde{X}}_2$. If $X_1$ was $(\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast )$, then $\widetilde{X_2}=(\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}{\tilde{C}}_1)$. When the receiver gets an uncorrupted $C_2$ and decrypts, then a completely garbled version of $P_2$ is produced. When forming $X_3$, the decrypter actually forms ${\tilde{X}}_3=(\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}\ast \text{,}{\tilde{C}}_1\text{,}{C}_2)$. The decrypter repeats this process, ultimately getting bad versions of $P_1\text{,}{P}_2\text{,}\cdots \text{,}{P}_9$. When the decrypter calculates $X_9$, the error block has moved to the leftmost block of ${\tilde{X}}_9$ as ${\tilde{X}}_9=({\tilde{C}}_1\text{,}{C}_2\text{,}\cdots \text{,}{C}_8)$. At the next step, the error will have been flushed from the $X_{10}$ register, and $X_{10}$ and subsequent registers will be uncorrupted. For a simplified version of these ideas, see Exercise 18.

The CBC and CFB modes of operation exhibit a drawback in that errors propagate for a duration of time corresponding to the block size of the cipher. The output feedback mode (OFB) is another example of a stream mode of operation for a block cipher where encryption is performed by XORing the message with a pseudorandom bit stream generated by the block cipher. One advantage of the OFB mode is that it avoids error propagation.

Much like CFB, OFB may work on chunks of different sizes. For our discussion, we focus on the eight-bit version of OFB, where OFB is used to encrypt eight-bit chunks of plaintext in a streaming mode. Just as for CFB, we break our plaintext into eight-bit pieces, with $P=\left[P_1\text{,}{P}_2\text{,}\cdots \text{,}\right]$. We start with an initial value $X_1$, which has a length equal to the block length of the cipher, for example, 64 bits (the sizes of the registers can easily be adjusted for other block sizes). $X_1$ is often called the IV, and should be chosen to be random. $X_1$ is encrypted using the key $K$ to produce 64 bits of output, and the leftmost eight bits $O_1$ of the ciphertext are extracted. These are then XORed with the first eight bits $P_1$ of the plaintext to produce eight bits of ciphertext, $C_1$.

So far, this is the same as what we were doing in CFB. But OFB differs from CFB in what happens next. In order to iterate, CFB updates the register $X_2$ by extracting the right 56 bits of $X_1$ and appending $C_1$ to the right side. Rather than use the ciphertext, OFB uses the output of the encryption. That is, OFB updates the register $X_2$ by extracting the right 56 bits of $X_1$ and appending $O_1$ to the right side.

In general, the following procedure is performed for $j=1\text{,}2\text{,}3\text{,}\cdots$:

We depict the steps for the OFB mode of operation in Figure 6.3. Here, the output stream $O_j$ is the encryption of the register containing the previous output from the block cipher. This output is then treated as a keystream and is XORed with the incoming plaintexts $P_j$ to produce a stream of ciphertexts. Decryption is very simple. We get the plaintext $P_j$ by XORing the corresponding ciphertext $C_j$ with the output keystream $O_j$. Again, just like CFB, we do not need the decryption function $D_K$.

Figure 6.3 Output Feedback Mode.

So why would one want to build a stream cipher this way as opposed to the way the CFB stream cipher was built? There are a few key advantages to the OFB strategy. First, the generation of the $O_j$ output key stream may be performed completely without any plaintext. What this means is that the key stream can be generated in advance. This might be desirable for applications where we cannot afford to perform encryption operations as the plaintext message arrives.

Another advantage lies in its performance when errors are introduced to the ciphertext. Suppose a few errors are introduced to $C_j$ when it is delivered to the receiver. Then only those corresponding bits in the plaintext are corrupted when decryption is performed. Since we build future output streams using the encryption of the register, and not using the corrupted ciphertext, the output stream will always remain clean and the errors in the ciphertext will not propagate.

To summarize, CFB required the register to completely flush itself of errors, which produced an entire block length of garbled plaintext bits. OFB, on the other hand, will immediately correct itself.

There is one problem associated with OFB, however, that is common to all stream ciphers that are obtained by XORing pseudorandom numbers with plaintext. If Eve knows a particular plaintext $P_j$ and ciphertext $C_j$, she can conduct the following attack. She first calculates

to get out the key stream. She may then create any false plaintext $P_j^{\mathrm{\prime }}$ she wants. Now, to produce a ciphertext, she merely has to XOR with the output stream she calculated:

This allows her to modify messages.

The counter (CTR) mode builds upon the ideas that were used in the OFB mode. Just like OFB, CTR creates an output key stream that is XORed with chunks of plaintext to produce ciphertext. The main difference between CTR and OFB lies in the fact that the output stream $O_j$ in CTR is not linked to previous output streams.

CTR starts with the plaintext broken into eight-bit pieces, $P=\left[P_1\text{,}{P}_2\text{,}\cdots \right]$. We begin with an initial value $X_1$, which has a length equal to the block length of the cipher, for example, 64 bits. Now, $X_1$ is encrypted using the key $K$ to produce 64 bits of output, and the leftmost eight bits of the ciphertext are extracted and XORed with $P_1$ to produce eight bits of ciphertext, $C_1$.

Now, rather than update the register $X_2$ to contain the output of the block cipher, we simply take $X_2=X_1+1$. In this way, $X_2$ does not depend on previous output. CTR then creates new output stream by encrypting $X_2$. Similarly, we may proceed by using $X_3=X_2+1$, and so on. The $j\text{th}$ ciphertext is produced by XORing the left eight bits from the encryption of the $j\text{th}$ register with the corresponding plaintext $P_j$.

In general, the procedure for CTR is

for $j=2\text{,}3\text{,}\cdots$, and is presented in Figure 6.4. The reader might wonder what happens to $X_j$ if we continually add $1$ to it. Shouldn’t it eventually become too large? This is unlikely to happen, but if it does, we simply wrap around and start back at $0$.

Figure 6.4 Counter Mode.

Just like OFB, the registers $X_j$ can be calculated ahead of time, and the actual encryption of plaintext is simple in that it involves just the XOR operation. As a result, its performance is identical to OFB’s when errors are introduced in the ciphertext. The advantage of CTR mode compared to OFB, however, stems from the fact that many output chunks $O_j$ may be calculated in parallel. We do not have to calculate $O_j$ before calculating $O_{j+1}$. This makes CTR mode ideal for parallelizing.