Block Cipher -Modes of Operations

A mode of operation is a technique for enhancing the effect of a cryptographic algorithm or adapting the algorithm for an application, such as applying a block cipher to a sequence of data blocks or a data stream.

Five modes of operation have been standardized by NIST for use with symmetric block ciphers such as DES and AES: electronic codebook mode, cipher block chaining mode, cipher feedback mode, output feedback mode, and counter mode.

A block cipher takes a fixed-length block of text of length $b$  bits and a key as input and produces a $b$-bit block of ciphertext. If the amount of plaintext to be encrypted is greater than $b$ bits, then the block cipher can still be used by breaking the plaintext up into $b$-bit blocks.When multiple blocks of plaintext are encrypted using the same key, a number of security issues arise.To apply a block cipher in a variety of applications, five modes of operation have been defined by NIST (SP 800-38A). In essence, a mode of operation is a technique for enhancing the effect of a cryptographic algorithm or adapting the algorithm for an application, such as applying a block cipher to a sequence of data blocks or a data stream.The five modes are intended to cover a wide variety of applications of encryption for which a block cipher could be used. These modes are intended for use with any symmetric block cipher, including triple DES and AES. The modes are summarized in Table 6.1 and described in this and the following sections.

Electronic Codebook (ECB)

The simplest mode is the electronic codebook (ECB) mode, in which plaintext is handled one block at a time and each block of plaintext is encrypted using the same key (Figure 6.3). The term codebook is used because, for a given key, there is a unique ciphertext for every -bit block of plaintext. Therefore, we can imagine a gigantic codebook in which there is an entry for every possible -bit plaintext pattern showing its corresponding ciphertext. 

For a message longer than $b$ bits, the procedure is simply to break the message into $b$-bit blocks, padding the last block if necessary. Decryption is performed one block at a time, always using the same key. In Figure 6.3, the plaintext (padded as necessary) consists of a sequence of $b$-bit blocks, $P_1, P_2, \ldots , P_N$; the corresponding sequence of ciphertext blocks is $C_1,C_2, \ldots, C_N$. We can define ECB mode as follows.

The ECB method is ideal for a short amount of data, such as an encryption key.Thus, if you want to transmit a DES or AES key securely, ECB is the appropriate mode to use.

The most significant characteristic of ECB is that if the same $b$-bit block of plaintext appears more than once in the message, it always produces the same ciphertext.

For lengthy messages, the ECB mode may not be secure. If the message is highly structured, it may be possible for a cryptanalyst to exploit these regularities. For example, if it is known that the message always starts out with certain predefined fields, then the cryptanalyst may have a number of known plaintext–ciphertext pairs to work with. If the message has repetitive elements with a period of repetition a multiple of bits, then these elements can be identified by the analyst. This may help in the analysis or may provide an opportunity for substituting or rearranging blocks.

Cipher Block Chaining Mode ( CBC)

To overcome the security deficiencies of ECB, we would like a technique in which the same plaintext block, if repeated, produces different ciphertext blocks.A simple way to satisfy this requirement is the cipher block chaining (CBC) mode (Figure 6.4).

In this scheme, the input to the encryption algorithm is the XOR of the current plaintext block and the preceding ciphertext block; the same key is used for each block. In effect, we have chained together the processing of the sequence of plaintext blocks.The input to the encryption function for each plaintext block bears no fixed relationship to the plaintext block.Therefore, repeating patterns of bits are not exposed.As with the ECB mode, the CBC mode requires that the last block be padded to a full bits if it is a partial block.For decryption, each cipher block is passed through the decryption algorithm.The result is XORed with the preceding ciphertext block to produce the plaintext block.To see that this works, we can write

$$C_j = E(K, [C_{j-1} \oplus P_j])$$

Then

$C_{j-1} \oplus D(K, C_j) = C_{j-1} \oplus C_{j-1} \oplus P_j = P_j$

$D(K, C_j) = C_{j-1} \oplus  P_j$

$D(K, C_j) = D(K, E(K, [C_{j-1} \oplus P_j]))$

To produce the first block of ciphertext, an initialization vector (IV) is XORed with the first block of plaintext. On decryption, the IV is XORed with the output of the decryption algorithm to recover the first block of plaintext. The IV is a data block that is that same size as the cipher block.We can define CBC mode as

The IV must be known to both the sender and receiver but be unpredictable by a third party. In particular, for any given plaintext, it must not be possible to predict the IV that will be associated to the plaintext in advance of the generation of the IV. For maximum security, the IV should be protected against unauthorized changes. This could be done by sending the IV using ECB encryption.

In conclusion, because of the chaining mechanism of CBC, it is an appropriate mode for encrypting messages of length greater than $b$ bits.In addition to its use to achieve confidentiality, the CBC mode can be used for authentication.

Cipher Feed Back Mode ( CFB)

For AES, DES, or any block cipher, encryption is performed on a block of b bits. In the case of DES, b = 64 and in the case of AES, b = 128. However, it is possible to convert a block cipher into a stream cipher, using one of the three modes to be dis- cussed in this and the next two sections: cipher feedback (CFB) mode, output feed- back (OFB) mode, and counter (CTR) mode. A stream cipher eliminates the need to pad a message to be an integral number of blocks. It also can operate in real time. Thus, if a character stream is being transmitted, each character can be encrypted and transmitted immediately using a character-oriented stream cipher.

One desirable property of a stream cipher is that the ciphertext be of the same length as the plaintext. Thus, if 8-bit characters are being transmitted, each character should be encrypted to produce a ciphertext output of 8 bits. If more than 8 bits are produced, transmission capacity is wasted.

Figure 6.5 depicts the CFB scheme. In the figure, it is assumed that the unit of transmission is s bits; a common value is $s = 8$. As with CBC, the units of plaintext are chained together, so that the ciphertext of any plaintext unit is a function of all the preceding plaintext. In this case, rather than blocks of $b$ bits, the plaintext is divided into segments of $s$ bits.

First, consider encryption. The input to the encryption function is a $b$-bit shift register that is initially set to some initialisation vector (IV). The leftmost (most significant) $s$ bits of the output of the encryption function are XORed with the first segment of plaintext $P_1$ to produce the first unit of ciphertext $C_1$, which is then transmitted. In addition, the contents of the shift register are shifted left by $s$ bits, and $C_1$ is placed in the rightmost (least significant) $s$ bits of the shift register. This process continues until all plaintext units have been encrypted.

For decryption, the same scheme is used, except that the received ciphertext unit is XORed with the output of the encryption function to produce the plaintext unit. Note that it is the encryption function that is used, not the decryption function. This is easily explained. Let $MSB_s(X)$ be defined as the most significant $s$ bits of $X$. Then

$$C_1 = P_1 \oplus MSB_s[E(K, IV)] $$

Therefore, by rearranging terms:

$$P1 = C_1 \oplus MSB_s[E(K, IV)]$$

The same reasoning holds for subsequent steps in the process. 

Output Feedback Mode (OFB)

The output feedback (OFB) mode is similar in structure to that of CFB. As can be seen in Figure 6.6, it is the output of the encryption function that is fed back to the shift register in OFB, whereas in CFB, the ciphertext unit is fed back to the shift register. The other difference is that the OFB mode operates on full blocks of plaintext and ciphertext, not on an $s$-bit subset. Encryption can be expressed as

$$C_j = P_j \oplus E(K, [IV])$$

By rearranging terms, we can demonstrate that decryption works.

$$P_j = C_j \oplus E(K, [IV])$$

As with CBC and CFB, the OFB mode requires an initialization vector. In the case of OFB, the IV must be a nonce; that is, the IV must be unique to each execution of the encryption operation. The reason for this is that the sequence of encryption output blocks, $O_i,$ depends only on the key and the IV and does not depend on the plaintext. Therefore, for a given key and IV, the stream of output bits used to XOR with the stream of plaintext bits is fixed. If two different messages had an identical block of plaintext in the identical position, then an attacker would be able to determine that portion of the $O_i$ stream.

One advantage of the OFB method is that bit errors in transmission do not propagate. For example, if a bit error occurs in $C_1$, only the recovered value of $P_1$ is affected; subsequent plaintext units are not corrupted. With CFB, $C_1$ also serves as input to the shift register and therefore causes additional corruption downstream.

The disadvantage of OFB is that it is more vulnerable to a message stream modification attack than is CFB. Consider that complementing a bit in the ciphertext complements the corresponding bit in the recovered plaintext. Thus, controlled changes to the recovered plaintext can be made. This may make it possible for an opponent, by making the necessary changes to the checksum portion of the message as well as to the data portion, to alter the ciphertext in such a way that it is not detected by an error-correcting code.

OFB has the structure of a typical stream cipher, because the cipher generates a stream of bits as a function of an initial value and a key, and that stream of bits is XORed with the plaintext bits. The generated stream that is XORed with the plaintext is itself independent of the plaintext; this is highlighted by dashed boxes in Figure 6.6. One distinction from the stream ciphers  is that OFB encrypts plaintext a full block at a time, where typically a block is 64 or 128 bits. Many stream ciphers encrypt one byte at a time.

Counter Mode (CTR)

The application of counter (CTR) mode has increased recently with applications to ATM (asynchronous transfer mode) network security and IP sec (IP security).

Figure 6.7 depicts the CTR mode. A counter equal to the plaintext block size is used. The only requirement is that the counter value must be different for each plaintext block that is encrypted. 

Typically, the counter is initialized to some value and then incremented by 1 for each subsequent block (modulo $2^b$, where $b$ is the block size). For encryption, the counter is encrypted and then XORed with the plaintext block to produce the ciphertext block; there is no chaining. For decryption, the same sequence of counter values is used, with each encrypted counter XORed with a ciphertext block to recover the corresponding plaintext block. Thus, the initial counter value must be made available for decryption. Given a sequence of counters $T_1, T_2, \ldots, T_N,$ we can define CTR mode as follows. for each plaintext block that is encrypted. Typically, the counter is initialized to some value and then incremented by 1 for each subsequent block (modulo $2^b$, where $b$ is the block size). 

For encryption, the counter is encrypted and then XORed with the plaintext block to produce the ciphertext block; there is no chaining. For decryption, the same sequence of counter values is used, with each encrypted counter XORed with a ciphertext block to recover the corresponding plaintext block. Thus, the initial counter value must be made available for decryption. Given a sequence of counters $T_1, T_2, \ldots, T_N$, we can define CTR mode as follows.

For the last plaintext block, which may be a partial block of u bits, the most significant u bits of the last output block are used for the XOR operation; the remaining b-u bits are discarded. Unlike the ECB, CBC, and CFB modes, we do not need to use padding because of the structure of the CTR mode.

As with the OFB mode, the initial counter value must be a nonce; that is, $T_1$ must be different for all of the messages encrypted using the same key. Further, all $T_i$ values across all messages must be unique. If, contrary to this requirement, a counter value is used multiple times, then the confidentiality of all of the plaintext blocks corresponding to that counter value may be compromised. In particular, if any plain- text block that is encrypted using a given counter value is known, then the output of the encryption function can be determined easily from the associated ciphertext block. This output allows any other plaintext blocks that are encrypted using the same counter value to be easily recovered from their associated ciphertext blocks.One way to ensure the uniqueness of counter values is to continue to incre- ment the counter value by 1 across messages. That is, the first counter value of the each message is one more than the last counter value of the preceding message.

Advantages of CTR mode.

Hardware efficiency: Unlike the three chaining modes, encryption (or decryption) in CTR mode can be done in parallel on multiple blocks of plaintext or ciphertext. For the chaining modes, the algorithm must complete the computation on one block before beginning on the next block. This limits the maximum throughput of the algorithm to the reciprocal of the time for one execution of block encryption or decryption. In CTR mode, the throughput is only limited by the amount of parallelism that is achieved.

Software efficiency: Similarly, because of the opportunities for parallel execution in CTR mode, processors that support parallel features, such as aggressive pipelining, multiple instruction dispatch per clock cycle, a large number of reg- isters, and SIMD instructions, can be effectively utilized.

Preprocessing:The execution of the underlying encryption algorithm does not depend on input of the plaintext or ciphertext. Therefore, if sufficient memory is available and security is maintained, preprocessing can be used to prepare the output of the encryption boxes that feed into the XOR functions, as in Figure 6.7. When the plaintext or ciphertext input is presented, then the only computation is a series of XORs. Such a strategy greatly enhances throughput.

Random access: The $i$th block of plaintext or ciphertext can be processed in random-access fashion. With the chaining modes, block $C_i$ cannot be computed until the $i – 1$ prior block are computed. There may be applications in which a ciphertext is stored and it is desired to decrypt just one block; for such applications, the random access feature is attractive.

Provable security: It can be shown that CTR is at least as secure as the other modes discussed in this section.

Simplicity: Unlike ECB and CBC modes, CTR mode requires only the implementation of the encryption algorithm and not the decryption algorithm. This matters most when the decryption algorithm differs substantially from the encryption algorithm, as it does for AES. In addition, the decryption key scheduling need not be implemented.

Note that, with the exception of ECB, all of the NIST-approved block cipher modes of operation involve feedback. This is clearly seen in Figure 6.8. To highlight the feedback mechanism, it is useful to think of the encryption function as taking input from a input register whose length equals the encryption block length and with output stored in an output register. The input register is updated one block at a time by the feedback mechanism. After each update, the encryption algorithm is executed, producing a result in the output register. Meanwhile, a block of plaintext is accessed. Note that both OFB and CTR produce output that is independent of both the plaintext and the ciphertext. Thus, they are natural candidates for stream ciphers that encrypt plaintext by XOR one full block at a time.