chapter 4.pdf

3.6 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 117 Programming Problems 3.23 3.24 3.25 3.26 3.27 3.28 Write a program that can encrypt and decrypt using the general Caesar cipher, also known as an additive cipher. Write a program that can encrypt and decrypt using the affine cipher described i...

3.6 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 117 Programming Problems 3.23 3.24 3.25 3.26 3.27 3.28 Write a program that can encrypt and decrypt using the general Caesar cipher, also known as an additive cipher. Write a program that can encrypt and decrypt using the affine cipher described in Problem 3.1. Write a program that can perform a letter frequency attack on an additive cipher without human intervention. Your software should produce possible plaintexts in rough order of likelihood. It would be good if your user interface allowed the user to specify “give me the top 10 possible plaintexts.” Write a program that can perform a letter frequency attack on any monoalphabetic substitution cipher without human intervention. Your software should produce possible plaintexts in rough order of likelihood. It would be good if your user interface allowed the user to specify “give me the top 10 possible plaintexts.” Create software that can encrypt and decrypt using a 2 * 2 Hill cipher. Create software that can perform a fast known plaintext attack on a Hill cipher, given the dimension m. How fast are your algorithms, as a function of m? CHAPTER Block Ciphers and the Data Encryption Standard 4.1 Traditional Block Cipher Structure Stream Ciphers and Block Ciphers Motivation for the Feistel Cipher Structure The Feistel Cipher 4.2 The Data Encryption Standard DES Encryption DES Decryption 4.3 A DES Example Results The Avalanche Effect 4.4 The Strength of DES The Use of 56-Bit Keys The Nature of the DES Algorithm Timing Attacks 4.5 Block Cipher Design Principles Number of Rounds Design of Function F Key Schedule Algorithm 4.6 Key Terms, Review Questions, and Problems 118 Hiva-Network.Com 4.1 / TRADITIONAL BLOCK CIPHER STRUCTURE 119 LEARNING OBJECTIVES After studying this chapter, you should be able to ◆ Understand the distinction between stream ciphers and block ciphers. ◆ Present an overview of the Feistel cipher and explain how decryption is the inverse of encryption. ◆ Present an overview of Data Encryption Standard (DES). ◆ Explain the concept of the avalanche effect. ◆ Discuss the cryptographic strength of DES. ◆ Summarize the principal block cipher design principles. The objective of this chapter is to illustrate the principles of modern symmetric ciphers. For this purpose, we focus on the most widely used symmetric cipher: the Data Encryption Standard (DES). Although numerous symmetric ciphers have been developed since the introduction of DES, and although it is destined to be replaced by the Advanced Encryption Standard (AES), DES remains the most important such algorithm. Furthermore, a detailed study of DES provides an understanding of the principles used in other symmetric ciphers. This chapter begins with a discussion of the general principles of symmetric block ciphers, which are the principal type of symmetric ciphers studied in this book. The other form of symmetric ciphers, stream ciphers, are discussed in Chapter 8. Next, we cover full DES. Following this look at a specific algorithm, we return to a more general discussion of block cipher design. Compared to public-key ciphers, such as RSA, the structure of DES and most symmetric ciphers is very complex and cannot be explained as easily as RSA and similar algorithms. Accordingly, the reader may wish to begin with a simplified version of DES, which is described in Appendix G. This version allows the reader to perform encryption and decryption by hand and gain a good understanding of the working of the algorithm details. Classroom experience indicates that a study of this simplified version enhances understanding of DES.1 4.1 TRADITIONAL BLOCK CIPHER STRUCTURE Several important symmetric block encryption algorithms in current use are based on a structure referred to as a Feistel block cipher [FEIS73]. For that reason, it is important to examine the design principles of the Feistel cipher. We begin with a comparison of stream ciphers and block ciphers. Then we discuss the motivation for the Feistel block cipher structure. Finally, we discuss some of its implications. 1 However, you may safely skip Appendix G, at least on a first reading. If you get lost or bogged down in the details of DES, then you can go back and start with simplified DES. 120 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD Stream Ciphers and Block Ciphers A stream cipher is one that encrypts a digital data stream one bit or one byte at a time. Examples of classical stream ciphers are the autokeyed Vigenère cipher and the Vernam cipher. In the ideal case, a one-time pad version of the Vernam cipher would be used (Figure 3.7), in which the keystream (ki) is as long as the plaintext bit stream (pi). If the cryptographic keystream is random, then this cipher is unbreakable by any means other than acquiring the keystream. However, the keystream must be provided to both users in advance via some independent and secure channel. This introduces insurmountable logistical problems if the intended data traffic is very large. Accordingly, for practical reasons, the bit-stream generator must be implemented as an algorithmic procedure, so that the cryptographic bit stream can be produced by both users. In this approach (Figure 4.1a), the bit-stream generator is a key-controlled algorithm and must produce a bit stream that is cryptographically strong. That is, it must be computationally impractical to predict future portions of the bit stream based on previous portions of the bit stream. The two users need only share the generating key, and each can produce the keystream. A block cipher is one in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length. Typically, a block size of 64 or Key (K) Bit-stream generation algorithm Key (K) ki Plaintext (pi) Bit-stream generation algorithm ki Plaintext (pi) Ciphertext (ci) ENCRYPTION DECRYPTION (a) Stream cipher using algorithmic bit-stream generator Key (K) b bits b bits Plaintext Ciphertext Encryption algorithm Key (K) Ciphertext Plaintext b bits b bits (b) Block cipher Figure 4.1 Decryption algorithm Stream Cipher and Block Cipher 4.1 / TRADITIONAL BLOCK CIPHER STRUCTURE 121 128 bits is used. As with a stream cipher, the two users share a symmetric encryption key (Figure 4.1b). Using some of the modes of operation explained in Chapter 7, a block cipher can be used to achieve the same effect as a stream cipher. Far more effort has gone into analyzing block ciphers. In general, they seem applicable to a broader range of applications than stream ciphers. The vast majority of network-based symmetric cryptographic applications make use of block ciphers. Accordingly, the concern in this chapter, and in our discussions throughout the book of symmetric encryption, will primarily focus on block ciphers. Motivation for the Feistel Cipher Structure A block cipher operates on a plaintext block of n bits to produce a ciphertext block of n bits. There are 2n possible different plaintext blocks and, for the encryption to be reversible (i.e., for decryption to be possible), each must produce a unique ciphertext block. Such a transformation is called reversible, or nonsingular. The following examples illustrate nonsingular and singular transformations for n = 2. Reversible Mapping Irreversible Mapping Plaintext Ciphertext Plaintext Ciphertext 00 11 00 11 01 10 01 10 10 00 10 01 11 01 11 01 In the latter case, a ciphertext of 01 could have been produced by one of two plaintext blocks. So if we limit ourselves to reversible mappings, the number of different transformations is 2n!.2 Figure 4.2 illustrates the logic of a general substitution cipher for n = 4. A 4-bit input produces one of 16 possible input states, which is mapped by the substitution cipher into a unique one of 16 possible output states, each of which is represented by 4 ciphertext bits. The encryption and decryption mappings can be defined by a tabulation, as shown in Table 4.1. This is the most general form of block cipher and can be used to define any reversible mapping between plaintext and ciphertext. Feistel refers to this as the ideal block cipher, because it allows for the maximum number of possible encryption mappings from the plaintext block [FEIS75]. But there is a practical problem with the ideal block cipher. If a small block size, such as n = 4, is used, then the system is equivalent to a classical substitution cipher. Such systems, as we have seen, are vulnerable to a statistical analysis of the plaintext. This weakness is not inherent in the use of a substitution cipher but rather results from the use of a small block size. If n is sufficiently large and an arbitrary reversible substitution between plaintext and ciphertext is allowed, then the statistical characteristics of the source plaintext are masked to such an extent that this type of cryptanalysis is infeasible. 2 The reasoning is as follows: For the first plaintext, we can choose any of 2n ciphertext blocks. For the second plaintext, we choose from among 2n - 1 remaining ciphertext blocks, and so on. 122 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD 4-bit input 0 1 2 3 4 5 0 1 2 3 4 5 4 to 16 decoder 6 7 8 9 6 7 8 9 16 to 4 encoder 10 11 12 13 14 15 10 11 12 13 14 15 4-bit output Figure 4.2 General n-bit-n-bit Block Substitution (shown with n = 4) An arbitrary reversible substitution cipher (the ideal block cipher) for a large block size is not practical, however, from an implementation and performance point of view. For such a transformation, the mapping itself constitutes the key. Consider again Table 4.1, which defines one particular reversible mapping from Table 4.1 Encryption and Decryption Tables for Substitution Cipher of Figure 4.2 Plaintext Ciphertext Ciphertext Plaintext 0000 1110 0000 1110 0001 0100 0001 0011 0010 1101 0010 0100 0011 0001 0011 1000 0100 0010 0100 0001 0101 1111 0101 1100 0110 1011 0110 1010 0111 1000 0111 1111 1000 0011 1000 0111 1001 1010 1001 1101 1010 0110 1010 1001 1011 1100 1011 0110 1100 0101 1100 1011 1101 1001 1101 0010 1110 0000 1110 0000 1111 0111 1111 0101 4.1 / TRADITIONAL BLOCK CIPHER STRUCTURE 123 plaintext to ciphertext for n = 4. The mapping can be defined by the entries in the second column, which show the value of the ciphertext for each plaintext block. This, in essence, is the key that determines the specific mapping from among all possible mappings. In this case, using this straightforward method of defining the key, the required key length is (4 bits) * (16 rows) = 64 bits. In general, for an n-bit ideal block cipher, the length of the key defined in this fashion is n * 2n bits. For a 64-bit block, which is a desirable length to thwart statistical attacks, the required key length is 64 * 264 = 270 ≈ 1021 bits. In considering these difficulties, Feistel points out that what is needed is an approximation to the ideal block cipher system for large n, built up out of components that are easily realizable [FEIS75]. But before turning to Feistel’s approach, let us make one other observation. We could use the general block substitution cipher but, to make its implementation tractable, confine ourselves to a subset of the 2n! possible reversible mappings. For example, suppose we define the mapping in terms of a set of linear equations. In the case of n = 4, we have y1 = k11x1 + k12x2 + k13x3 + k14x4 y2 = k21x1 + k22x2 + k23x3 + k24x4 y3 = k31x1 + k32x2 + k33x3 + k34x4 y4 = k41x1 + k42x2 + k43x3 + k44x4 where the xi are the four binary digits of the plaintext block, the yi are the four binary digits of the ciphertext block, the kij are the binary coefficients, and arithmetic is mod 2. The key size is just n2, in this case 16 bits. The danger with this kind of formulation is that it may be vulnerable to cryptanalysis by an attacker that is aware of the structure of the algorithm. In this example, what we have is essentially the Hill cipher discussed in Chapter 3, applied to binary data rather than characters. As we saw in Chapter 3, a simple linear system such as this is quite vulnerable. The Feistel Cipher Feistel proposed [FEIS73] that we can approximate the ideal block cipher by utilizing the concept of a product cipher, which is the execution of two or more simple ciphers in sequence in such a way that the final result or product is cryptographically stronger than any of the component ciphers. The essence of the approach is to develop a block cipher with a key length of k bits and a block length of n bits, allowing a total of 2k possible transformations, rather than the 2n! transformations available with the ideal block cipher. In particular, Feistel proposed the use of a cipher that alternates substitutions and permutations, where these terms are defined as follows: ■ ■ Substitution: Each plaintext element or group of elements is uniquely replaced by a corresponding ciphertext element or group of elements. Permutation: A sequence of plaintext elements is replaced by a permutation of that sequence. That is, no elements are added or deleted or replaced in the sequence, rather the order in which the elements appear in the sequence is changed. 124 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD In fact, Feistel’s is a practical application of a proposal by Claude Shannon to develop a product cipher that alternates confusion and diffusion functions [SHAN49].3 We look next at these concepts of diffusion and confusion and then present the Feistel cipher. But first, it is worth commenting on this remarkable fact: The Feistel cipher structure, which dates back over a quarter century and which, in turn, is based on Shannon’s proposal of 1945, is the structure used by a number of significant symmetric block ciphers currently in use. In particular, the Feistel structure is used for Triple Data Encryption Algorithm (TDEA), which is one of the two encryption algorithms (along with AES), approved for general use by the National Institute of Standards and Technology (NIST). The Feistel structure is also used for several schemes for format-preserving encryption, which have recently come into prominence. In addition, the Camellia block cipher is a Feistel structure; it is one of the possible symmetric ciphers in TLS and a number of other Internet security protocols. Both TDEA and format-preserving encryption are covered in Chapter 7. DIFFUSION AND CONFUSION The terms diffusion and confusion were introduced by Claude Shannon to capture the two basic building blocks for any cryptographic system [SHAN49]. Shannon’s concern was to thwart cryptanalysis based on statistical analysis. The reasoning is as follows. Assume the attacker has some knowledge of the statistical characteristics of the plaintext. For example, in a human-readable message in some language, the frequency distribution of the various letters may be known. Or there may be words or phrases likely to appear in the message (probable words). If these statistics are in any way reflected in the ciphertext, the cryptanalyst may be able to deduce the encryption key, part of the key, or at least a set of keys likely to contain the exact key. In what Shannon refers to as a strongly ideal cipher, all statistics of the ciphertext are independent of the particular key used. The arbitrary substitution cipher that we discussed previously (Figure 4.2) is such a cipher, but as we have seen, it is impractical.4 Other than recourse to ideal systems, Shannon suggests two methods for frustrating statistical cryptanalysis: diffusion and confusion. In diffusion, the statistical structure of the plaintext is dissipated into long-range statistics of the ciphertext. This is achieved by having each plaintext digit affect the value of many ciphertext digits; generally, this is equivalent to having each ciphertext digit be affected by many plaintext digits. An example of diffusion is to encrypt a message M = m1, m2, m3, c of characters with an averaging operation: k yn = ¢ a mn + i ≤ mod 26 i=1 3 The paper is available at box.com/Crypto7e. Shannon’s 1949 paper appeared originally as a classified report in 1945. Shannon enjoys an amazing and unique position in the history of computer and information science. He not only developed the seminal ideas of modern cryptography but is also responsible for inventing the discipline of information theory. Based on his work in information theory, he developed a formula for the capacity of a data communications channel, which is still used today. In addition, he founded another discipline, the application of Boolean algebra to the study of digital circuits; this last he managed to toss off as a master’s thesis. 4 Appendix F expands on Shannon’s concepts concerning measures of secrecy and the security of cryptographic algorithms. 4.1 / TRADITIONAL BLOCK CIPHER STRUCTURE 125 adding k successive letters to get a ciphertext letter yn. One can show that the statistical structure of the plaintext has been dissipated. Thus, the letter frequencies in the ciphertext will be more nearly equal than in the plaintext; the digram frequencies will also be more nearly equal, and so on. In a binary block cipher, diffusion can be achieved by repeatedly performing some permutation on the data followed by applying a function to that permutation; the effect is that bits from different positions in the original plaintext contribute to a single bit of ciphertext.5 Every block cipher involves a transformation of a block of plaintext into a block of ciphertext, where the transformation depends on the key. The mechanism of diffusion seeks to make the statistical relationship between the plaintext and ciphertext as complex as possible in order to thwart attempts to deduce the key. On the other hand, confusion seeks to make the relationship between the statistics of the ciphertext and the value of the encryption key as complex as possible, again to thwart attempts to discover the key. Thus, even if the attacker can get some handle on the statistics of the ciphertext, the way in which the key was used to produce that ciphertext is so complex as to make it difficult to deduce the key. This is achieved by the use of a complex substitution algorithm. In contrast, a simple linear substitution function would add little confusion. As [ROBS95b] points out, so successful are diffusion and confusion in capturing the essence of the desired attributes of a block cipher that they have become the cornerstone of modern block cipher design. FEISTEL CIPHER STRUCTURE The left-hand side of Figure 4.3 depicts the encryption structure proposed by Feistel. The inputs to the encryption algorithm are a plaintext block of length 2w bits and a key K. The plaintext block is divided into two halves, LE0 and RE0. The two halves of the data pass through n rounds of processing and then combine to produce the ciphertext block. Each round i has as inputs LEi - 1 and REi - 1 derived from the previous round, as well as a subkey Ki derived from the overall K. In general, the subkeys Ki are different from K and from each other. In Figure 4.3, 16 rounds are used, although any number of rounds could be implemented. All rounds have the same structure. A substitution is performed on the left half of the data. This is done by applying a round function F to the right half of the data and then taking the exclusive-OR of the output of that function and the left half of the data. The round function has the same general structure for each round but is parameterized by the round subkey Ki. Another way to express this is to say that F is a function of right-half block of w bits and a subkey of y bits, which produces an output value of length w bits: F(REi, Ki + 1). Following this substitution, a permutation is performed that consists of the interchange of the two halves of the data.6 This structure is a particular form of the substitution-permutation network (SPN) proposed by Shannon. 5 Some books on cryptography equate permutation with diffusion. This is incorrect. Permutation, by itself, does not change the statistics of the plaintext at the level of individual letters or permuted blocks. For example, in DES, the permutation swaps two 32-bit blocks, so statistics of strings of 32 bits or less are preserved. 6 The final round is followed by an interchange that undoes the interchange that is part of the final round. One could simply leave both interchanges out of the diagram, at the sacrifice of some consistency of presentation. In any case, the effective lack of a swap in the final round is done to simplify the implementation of the decryption process, as we shall see. CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD Output (plaintext) RD17 = LE0 LD17 = RE0 Input (plaintext) Round 2 K1 Round 16 F LE1 LD16 = RE0 RD16 = LE0 RE0 K2 F LD14 = RE2 RD14 = LE2 LE14 RE14 LD2 = RE14 RD2 = LE14 RE15 F LE16 RE16 F K2 K15 LD1 = RE15 RD1 = LE15 K16 Round 1 LE15 K15 Round 2 RE2 Round 15 LE2 F K1 LD15 = RE1 RD15 = LE1 RE1 F F Round 15 Round 1 LE0 Round 16 126 F K16 LD0 = RE16 RD0 = LE16 Input (ciphertext) LE17 RE17 Output (ciphertext) Figure 4.3 Feistel Encryption and Decryption (16 rounds) The exact realization of a Feistel network depends on the choice of the following parameters and design features: ■ Block size: Larger block sizes mean greater security (all other things being equal) but reduced encryption/decryption speed for a given algorithm. The greater security is achieved by greater diffusion. Traditionally, a block size of 64 bits has been considered a reasonable tradeoff and was nearly universal in block cipher design. However, the new AES uses a 128-bit block size. 4.1 / TRADITIONAL BLOCK CIPHER STRUCTURE ■ ■ ■ ■ 127 Key size: Larger key size means greater security but may decrease encryption/ decryption speed. The greater security is achieved by greater resistance to brute-force attacks and greater confusion. Key sizes of 64 bits or less are now widely considered to be inadequate, and 128 bits has become a common size. Number of rounds: The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security. A typical size is 16 rounds. Subkey generation algorithm: Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis. Round function F: Again, greater complexity generally means greater resistance to cryptanalysis. There are two other considerations in the design of a Feistel cipher: ■ ■ Fast software encryption/decryption: In many cases, encryption is embedded in applications or utility functions in such a way as to preclude a hardware implementation. Accordingly, the speed of execution of the algorithm becomes a concern. Ease of analysis: Although we would like to make our algorithm as difficult as possible to cryptanalyze, there is great benefit in making the algorithm easy to analyze. That is, if the algorithm can be concisely and clearly explained, it is easier to analyze that algorithm for cryptanalytic vulnerabilities and therefore develop a higher level of assurance as to its strength. DES, for example, does not have an easily analyzed functionality. FEISTEL DECRYPTION ALGORITHM The process of decryption with a Feistel cipher is essentially the same as the encryption process. The rule is as follows: Use the ciphertext as input to the algorithm, but use the subkeys Ki in reverse order. That is, use Kn in the first round, Kn - 1 in the second round, and so on, until K1 is used in the last round. This is a nice feature, because it means we need not implement two different algorithms; one for encryption and one for decryption. To see that the same algorithm with a reversed key order produces the correct result, Figure 4.3 shows the encryption process going down the left-hand side and the decryption process going up the right-hand side for a 16-round algorithm. For clarity, we use the notation LEi and REi for data traveling through the encryption algorithm and LDi and RDi for data traveling through the decryption algorithm. The diagram indicates that, at every round, the intermediate value of the decryption process is equal to the corresponding value of the encryption process with the two halves of the value swapped. To put this another way, let the output of the ith encryption round be LEi ‘REi (LEi concatenated with REi). Then the corresponding output of the (16 - i)th decryption round is REi ‘LEi or, equivalently, LD16 - i ‘RD16 - i. Let us walk through Figure 4.3 to demonstrate the validity of the preceding assertions. After the last iteration of the encryption process, the two halves of the output are swapped, so that the ciphertext is RE16 ‘LE16. The output of that round is the ciphertext. Now take that ciphertext and use it as input to the same algorithm. The input to the first round is RE16 ‘LE16, which is equal to the 32-bit swap of the output of the sixteenth round of the encryption process. Hiva-Network.Com 128 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD Now we would like to show that the output of the first round of the decryption process is equal to a 32-bit swap of the input to the sixteenth round of the encryption process. First, consider the encryption process. We see that LE16 = RE15 RE16 = LE15 ⊕ F(RE15, K16) On the decryption side, LD1 = RD0 = LE16 = RE15 RD1 = LD0 ⊕ F(RD0, K16) = RE16 ⊕ F(RE15, K16) = [LE15 ⊕ F(RE15, K16)] ⊕ F(RE15, K16) The XOR has the following properties: [A ⊕ B] ⊕ C = A ⊕ [B ⊕ C] D⊕D = 0 E⊕0 = E Thus, we have LD1 = RE15 and RD1 = LE15. Therefore, the output of the first round of the decryption process is RE15 ‘LE15, which is the 32-bit swap of the input to the sixteenth round of the encryption. This correspondence holds all the way through the 16 iterations, as is easily shown. We can cast this process in general terms. For the ith iteration of the encryption algorithm, LEi = REi - 1 REi = LEi - 1 ⊕ F(REi - 1, Ki) Rearranging terms: REi - 1 = LEi LEi - 1 = REi ⊕ F(REi - 1, Ki) = REi ⊕ F(LEi, Ki) Thus, we have described the inputs to the ith iteration as a function of the outputs, and these equations confirm the assignments shown in the right-hand side of Figure 4.3. Finally, we see that the output of the last round of the decryption process is RE0 ‘LE0. A 32-bit swap recovers the original plaintext, demonstrating the validity of the Feistel decryption process. Note that the derivation does not require that F be a reversible function. To see this, take a limiting case in which F produces a constant output (e.g., all ones) regardless of the values of its two arguments. The equations still hold. To help clarify the preceding concepts, let us look at a specific example (Figure 4.4 and focus on the fifteenth round of encryption, corresponding to the second round of decryption. Suppose that the blocks at each stage are 32 bits (two 16-bit halves) and that the key size is 24 bits. Suppose that at the end of encryption round fourteen, the value of the intermediate block (in hexadecimal) is DE7F03A6. Then LE14 = DE7F and RE14 = 03A6. Also assume that the value of K15 is 12DE52. After round 15, we have LE15 = 03A6 and RE15 = F(03A6, 12DE52) ⊕ DE7F. 4.2 / THE DATA ENCRYPTION STANDARD Encryption round F(03A6, 12DE52) [F(03A6, 12DE52) DE7F] = DE7F 03A6 03A6 F 12DE52 F 03A6 Figure 4.4 Decryption round F(03A6, 12DE52) DE7F F(03A6, 12DE52) DE7F 12DE52 Round 2 Round 15 DE7F 129 03A6 Feistel Example Now let’s look at the decryption. We assume that LD1 = RE15 and RD1 = LE15, as shown in Figure 4.3, and we want to demonstrate that LD2 = RE14 and RD2 = LE14. So, we start with LD1 = F(03A6, 12DE52) ⊕ DE7F and RD1 = 03A6. Then, from Figure 4.3, LD2 = 03A6 = RE14 and RD2 = F(03A6, 12DE52) ⊕ [F(03A6, 12DE52) ⊕ DE7F] = DE7F = LE14. 4.2 THE DATA ENCRYPTION STANDARD Until the introduction of the Advanced Encryption Standard (AES) in 2001, the Data Encryption Standard (DES) was the most widely used encryption scheme. DES was issued in 1977 by the National Bureau of Standards, now the National Institute of Standards and Technology (NIST), as Federal Information Processing Standard 46 (FIPS PUB 46). The algorithm itself is referred to as the Data Encryption Algorithm (DEA).7 For DEA, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption. Over the years, DES became the dominant symmetric encryption algorithm, especially in financial applications. In 1994, NIST reaffirmed DES for federal use for another five years; NIST recommended the use of DES for applications other than the protection of classified information. In 1999, NIST issued a new version of its standard (FIPS PUB 46-3) that indicated that DES should be used only for legacy systems and that triple DES (which in essence involves repeating the DES algorithm three times on the plaintext using two or three different keys to produce the ciphertext) be used. We study triple DES in Chapter 7. Because the underlying encryption and decryption algorithms are the same for DES and triple DES, it remains important to understand the DES cipher. This section provides an overview.For the interested reader, Appendix S provides further detail. 7 The terminology is a bit confusing. Until recently, the terms DES and DEA could be used interchangeably. However, the most recent edition of the DES document includes a specification of the DEA described here plus the triple DEA (TDEA) described in Chapter 7. Both DEA and TDEA are part of the Data Encryption Standard. Further, until the recent adoption of the official term TDEA, the triple DEA algorithm was typically referred to as triple DES and written as 3DES. For the sake of convenience, we will use the term 3DES. 130 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD DES Encryption The overall scheme for DES encryption is illustrated in Figure 4.5. As with any encryption scheme, there are two inputs to the encryption function: the plaintext to be encrypted and the key. In this case, the plaintext must be 64 bits in length and the key is 56 bits in length.8 Looking at the left-hand side of the figure, we can see that the processing of the plaintext proceeds in three phases. First, the 64-bit plaintext passes through an initial permutation (IP) that rearranges the bits to produce the permuted input. 64-bit plaintext 64-bit key %%%%%%%%% %%%%%%%%% Initial permutation Permuted choice 1 64 Round 1 56 K1 48 K2 48 Permuted choice 2 56 Left circular shift 64 Round 2 Round 16 56 K16 48 Permuted choice 2 Permuted choice 2 56 56 Left circular shift Left circular shift 32-bit swap 64 bits Inverse initial permutation %%%%%%%%% 64-bit ciphertext Figure 4.5 General Depiction of DES Encryption Algorithm 8 Actually, the function expects a 64-bit key as input. However, only 56 of these bits are ever used; the other 8 bits can be used as parity bits or simply set arbitrarily. 4.3 / A DES EXAMPLE 131 This is followed by a phase consisting of sixteen rounds of the same function, which involves both permutation and substitution functions. The output of the last (sixteenth) round consists of 64 bits that are a function of the input plaintext and the key. The left and right halves of the output are swapped to produce the preoutput. Finally, the preoutput is passed through a permutation [IP -1] that is the inverse of the initial permutation function, to produce the 64-bit ciphertext. With the exception of the initial and final permutations, DES has the exact structure of a Feistel cipher, as shown in Figure 4.3. The right-hand portion of Figure 4.5 shows the way in which the 56-bit key is used. Initially, the key is passed through a permutation function. Then, for each of the sixteen rounds, a subkey (Ki) is produced by the combination of a left circular shift and a permutation. The permutation function is the same for each round, but a different subkey is produced because of the repeated shifts of the key bits. DES Decryption As with any Feistel cipher, decryption uses the same algorithm as encryption, except that the application of the subkeys is reversed. Additionally, the initial and final permutations are reversed. 4.3 A DES EXAMPLE We now work through an example and consider some of its implications. Although you are not expected to duplicate the example by hand, you will find it informative to study the hex patterns that occur from one step to the next. For this example, the plaintext is a hexadecimal palindrome. The plaintext, key, and resulting ciphertext are as follows: Plaintext: 02468aceeca86420 Key: 0f1571c947d9e859 Ciphertext: da02ce3a89ecac3b Results Table 4.2 shows the progression of the algorithm. The first row shows the 32-bit values of the left and right halves of data after the initial permutation. The next 16 rows show the results after each round. Also shown is the value of the 48-bit subkey generated for each round. Note that Li = Ri - 1. The final row shows the left- and right-hand values after the inverse initial permutation. These two values combined form the ciphertext. The Avalanche Effect A desirable property of any encryption algorithm is that a small change in either the plaintext or the key should produce a significant change in the ciphertext. In particular, a change in one bit of the plaintext or one bit of the key should produce 132 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD Table 4.2 DES Example Round Ki IP Li Ri 5a005a00 3cf03c0f 1 1e030f03080d2930 3cf03c0f bad22845 2 0a31293432242318 bad22845 99e9b723 3 23072318201d0c1d 99e9b723 0bae3b9e 4 05261d3824311a20 0bae3b9e 42415649 5 3325340136002c25 42415649 18b3fa41 6 123a2d0d04262a1c 18b3fa41 9616fe23 7 021f120b1c130611 9616fe23 67117cf2 8 1c10372a2832002b 67117cf2 c11bfc09 9 04292a380c341f03 c11bfc09 887fbc6c 10 2703212607280403 887fbc6c 600f7e8b 11 2826390c31261504 600f7e8b f596506e 12 12071c241a0a0f08 f596506e 738538b8 13 300935393c0d100b 738538b8 c6a62c4e 14 311e09231321182a c6a62c4e 56b0bd75 15 283d3e0227072528 56b0bd75 75e8fd8f 16 2921080b13143025 75e8fd8f 25896490 da02ce3a 89ecac3b IP − 1 Note: DES subkeys are shown as eight 6-bit values in hex format a change in many bits of the ciphertext. This is referred to as the avalanche effect. If the change were small, this might provide a way to reduce the size of the plaintext or key space to be searched. Using the example from Table 4.2, Table 4.3 shows the result when the fourth bit of the plaintext is changed, so that the plaintext is 12468aceeca86420. The second column of the table shows the intermediate 64-bit values at the end of each round for the two plaintexts. The third column shows the number of bits that differ between the two intermediate values. The table shows that, after just three rounds, 18 bits differ between the two blocks. On completion, the two ciphertexts differ in 32 bit positions. Table 4.4 shows a similar test using the original plaintext of with two keys that differ in only the fourth bit position: the original key, 0f1571c947d9e859, and the altered key, 1f1571c947d9e859. Again, the results show that about half of the bits in the ciphertext differ and that the avalanche effect is pronounced after just a few rounds. 4.3 / A DES EXAMPLE 133 Table 4.3 Avalanche Effect in DES: Change in Plaintext D Round 02468aceeca86420 12468aceeca86420 1 9 c11bfc09887fbc6c 99f911532eed7d94 32 1 3cf03c0fbad22845 3cf03c0fbad32845 1 10 887fbc6c600f7e8b 2eed7d94d0f23094 34 2 bad2284599e9b723 bad3284539a9b7a3 5 11 600f7e8bf596506e d0f23094455da9c4 37 3 99e9b7230bae3b9e 39a9b7a3171cb8b3 18 12 f596506e738538b8 455da9c47f6e3cf3 31 4 0bae3b9e42415649 171cb8b3ccaca55e 34 13 738538b8c6a62c4e 7f6e3cf34bc1a8d9 29 5 4241564918b3fa41 ccaca55ed16c3653 37 14 c6a62c4e56b0bd75 4bc1a8d91e07d409 33 6 18b3fa419616fe23 d16c3653cf402c68 33 15 56b0bd7575e8fd8f 1e07d4091ce2e6dc 31 7 9616fe2367117cf2 cf402c682b2cefbc 32 16 75e8fd8f25896490 1ce2e6dc365e5f59 32 8 67117cf2c11bfc09 2b2cefbc99f91153 33 IP − 1 da02ce3a89ecac3b 057cde97d7683f2a 32 Round Table 4.4 D Avalanche Effect in DES: Change in Key D Round 02468aceeca86420 02468aceeca86420 0 9 c11bfc09887fbc6c 548f1de471f64dfd 34 1 3cf03c0fbad22845 3cf03c0f9ad628c5 3 10 887fbc6c600f7e8b 71f64dfd4279876c 36 2 bad2284599e9b723 9ad628c59939136b 11 11 600f7e8bf596506e 4279876c399fdc0d 32 3 99e9b7230bae3b9e 9939136b768067b7 25 12 f596506e738538b8 399fdc0d6d208dbb 28 4 0bae3b9e42415649 768067b75a8807c5 29 13 738538b8c6a62c4e 6d208dbbb9bdeeaa 33 5 4241564918b3fa41 5a8807c5488dbe94 26 14 c6a62c4e56b0bd75 b9bdeeaad2c3a56f 30 6 18b3fa419616fe23 488dbe94aba7fe53 26 15 56b0bd7575e8fd8f d2c3a56f2765c1fb 27 7 9616fe2367117cf2 aba7fe53177d21e4 27 16 75e8fd8f25896490 2765c1fb01263dc4 30 8 67117cf2c11bfc09 177d21e4548f1de4 32 IP − 1 da02ce3a89ecac3b ee92b50606b62b0b 30 Round D 134 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD 4.4 THE STRENGTH OF DES Since its adoption as a federal standard, there have been lingering concerns about the level of security provided by DES. These concerns, by and large, fall into two areas: key size and the nature of the algorithm. The Use of 56-Bit Keys With a key length of 56 bits, there are 256 possible keys, which is approximately 7.2 * 1016 keys. Thus, on the face of it, a brute-force attack appears impractical. Assuming that, on average, half the key space has to be searched, a single machine performing one DES encryption per microsecond would take more than a thousand years to break the cipher. However, the assumption of one encryption per microsecond is overly conservative. As far back as 1977, Diffie and Hellman postulated that the technology existed to build a parallel machine with 1 million encryption devices, each of which could perform one encryption per microsecond [DIFF77]. This would bring the average search time down to about 10 hours. The authors estimated that the cost would be about $20 million in 1977 dollars. With current technology, it is not even necessary to use special, purpose-built hardware. Rather, the speed of commercial, off-the-shelf processors threaten the security of DES. A recent paper from Seagate Technology [SEAG08] suggests that a rate of 1 billion (109) key combinations per second is reasonable for today’s multicore computers. Recent offerings confirm this. Both Intel and AMD now offer hardware-based instructions to accelerate the use of AES. Tests run on a contemporary multicore Intel machine resulted in an encryption rate of about half a billion encryptions per second [BASU12]. Another recent analysis suggests that with contemporary supercomputer technology, a rate of 1013 encryptions per second is reasonable [AROR12]. With these results in mind, Table 4.5 shows how much time is required for a brute-force attack for various key sizes. As can be seen, a single PC can break DES in about a year; if multiple PCs work in parallel, the time is drastically shortened. And today’s supercomputers should be able to find a key in about an hour. Key sizes of 128 bits or greater are effectively unbreakable using simply a brute-force approach. Even if we managed to speed up the attacking system by a factor of 1 trillion (1012), it would still take over 100,000 years to break a code using a 128-bit key. Fortunately, there are a number of alternatives to DES, the most important of which are AES and triple DES, discussed in Chapters 6 and 7, respectively. The Nature of the DES Algorithm Another concern is the possibility that cryptanalysis is possible by exploiting the characteristics of the DES algorithm. The focus of concern has been on the eight substitution tables, or S-boxes, that are used in each iteration (described in Appendix S). Because the design criteria for these boxes, and indeed for the entire algorithm, were not made public, there is a suspicion that the boxes were constructed in such a way that cryptanalysis is possible for an opponent who knows 4.5 / BLOCK CIPHER DESIGN PRINCIPLES 135 Table 4.5 Average Time Required for Exhaustive Key Search Time Required at 109 Decryptions/s Time Required at 1013 Decryptions/s Key Size (bits) Cipher Number of Alternative Keys 56 DES 256 ≈ 7.2 * 1016 255 ns = 1.125 years 1 hour 128 AES 2128 ≈ 3.4 * 1038 2127 ns = 5.3 * 1021 years 5.3 * 1017 years 168 Triple DES 2168 ≈ 3.7 * 1050 2167 ns = 5.8 * 1033 years 5.8 * 1029 years 192 AES 2 ns = 9.8 * 10 years 9.8 * 1036 years 256 AES 2256 ≈ 1.2 * 1077 2255 ns = 1.8 * 1060 years 1.8 * 1056 years 26 characters (permutation) Monoalphabetic 2! = 4 * 1026 2 * 1026 ns = 6.3 * 109 years 6.3 * 106 years 192 ≈ 6.3 * 10 57 191 2 40 the weaknesses in the S-boxes. This assertion is tantalizing, and over the years a number of regularities and unexpected behaviors of the S-boxes have been discovered. Despite this, no one has so far succeeded in discovering the supposed fatal weaknesses in the S-boxes.9 Timing Attacks We discuss timing attacks in more detail in Part Two, as they relate to public-key algorithms. However, the issue may also be relevant for symmetric ciphers. In essence, a timing attack is one in which information about the key or the plaintext is obtained by observing how long it takes a given implementation to perform decryptions on various ciphertexts. A timing attack exploits the fact that an encryption or decryption algorithm often takes slightly different amounts of time on different inputs. [HEVI99] reports on an approach that yields the Hamming weight (number of bits equal to one) of the secret key. This is a long way from knowing the actual key, but it is an intriguing first step. The authors conclude that DES appears to be fairly resistant to a successful timing attack but suggest some avenues to explore. Although this is an interesting line of attack, it so far appears unlikely that this technique will ever be successful against DES or more powerful symmetric ciphers such as triple DES and AES. 4.5 BLOCK CIPHER DESIGN PRINCIPLES Although much progress has been made in designing block ciphers that are cryptographically strong, the basic principles have not changed all that much since the work of Feistel and the DES design team in the early 1970s. In this section we look at three critical aspects of block cipher design: the number of rounds, design of the function F, and key scheduling. 9 At least, no one has publicly acknowledged such a discovery. 136 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD Number of Rounds The cryptographic strength of a Feistel cipher derives from three aspects of the design: the number of rounds, the function F, and the key schedule algorithm. Let us look first at the choice of the number of rounds. The greater the number of rounds, the more difficult it is to perform cryptanalysis, even for a relatively weak F. In general, the criterion should be that the number of rounds is chosen so that known cryptanalytic efforts require greater effort than a simple brute-force key search attack. This criterion was certainly used in the design of DES. Schneier [SCHN96] observes that for 16-round DES, a differential cryptanalysis attack is slightly less efficient than brute force: The differential cryptanalysis attack requires 255.1 operations,10 whereas brute force requires 255. If DES had 15 or fewer rounds, differential cryptanalysis would require less effort than a brute-force key search. This criterion is attractive, because it makes it easy to judge the strength of an algorithm and to compare different algorithms. In the absence of a cryptanalytic breakthrough, the strength of any algorithm that satisfies the criterion can be judged solely on key length. Design of Function F The heart of a Feistel block cipher is the function F, which provides the element of confusion in a Feistel cipher. Thus, it must be difficult to “unscramble” the substitution performed by F. One obvious criterion is that F be nonlinear, as we discussed previously. The more nonlinear F, the more difficult any type of cryptanalysis will be. There are several measures of nonlinearity, which are beyond the scope of this book. In rough terms, the more difficult it is to approximate F by a set of linear equations, the more nonlinear F is. Several other criteria should be considered in designing F. We would like the algorithm to have good avalanche properties. Recall that, in general, this means that a change in one bit of the input should produce a change in many bits of the output. A more stringent version of this is the strict avalanche criterion (SAC) [WEBS86], which states that any output bit j of an S-box (see Appendix S for a discussion of S-boxes) should change with probability 1/2 when any single input bit i is inverted for all i, j. Although SAC is expressed in terms of S-boxes, a similar criterion could be applied to F as a whole. This is important when considering designs that do not include S-boxes. Another criterion proposed in [WEBS86] is the bit independence criterion (BIC), which states that output bits j and k should change independently when any single input bit i is inverted for all i, j, and k. The SAC and BIC criteria appear to strengthen the effectiveness of the confusion function. 10 Differential cryptanalysis of DES requires 247 chosen plaintext. If all you have to work with is known plaintext, then you must sort through a large quantity of known plaintext–ciphertext pairs looking for the useful ones. This brings the level of effort up to 255.1. Hiva-Network.Com 4.6 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 137 Key Schedule Algorithm With any Feistel block cipher, the key is used to generate one subkey for each round. In general, we would like to select subkeys to maximize the difficulty of deducing individual subkeys and the difficulty of working back to the main key. No general principles for this have yet been promulgated. Adams suggests [ADAM94] that, at minimum, the key schedule should guarantee key/ciphertext Strict Avalanche Criterion and Bit Independence Criterion. 4.6 KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS Key Terms avalanche effect block cipher confusion Data Encryption Standard (DES) diffusion Feistel cipher irreversible mapping key permutation product cipher reversible mapping round round function subkey substitution Review Questions 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Briefly define a nonsingular transformation. What is the difference between a block cipher and a stream cipher? Why is it not practical to use an arbitrary reversible substitution cipher of the kind shown in Table 4.1? Briefly define the terms substitution and permutation. What is the difference between diffusion and confusion? Which parameters and design choices determine the actual algorithm of a Feistel cipher? What are the critical aspects of Feistel cipher design? Problems 4.1 a. In Section 4.1, under the subsection on the motivation for the Feistel cipher structure, it was stated that, for a block of n bits, the number of different reversible mappings for the ideal block cipher is 2n!. Justify. b. In that same discussion, it was stated that for the ideal block cipher, which allows all possible reversible mappings, the size of the key is n * 2n bits. But, if there are 2n! possible mappings, it should take log 2 2n! bits to discriminate among the different mappings, and so the key length should be log 2 2n!. However, log 2 2n! 6 n * 2n. Explain the discrepancy. 138 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD 4.2 Consider a Feistel cipher composed of sixteen rounds with a block length of 128 bits and a key length of 128 bits. Suppose that, for a given k, the key scheduling algorithm determines values for the first eight round keys, k1, k2, c k8, and then sets k9 = k8, k10 = k7, k11 = k6, c , k16 = k1 4.3 4.4 4.5 Suppose you have a ciphertext c. Explain how, with access to an encryption oracle, you can decrypt c and determine m using just a single oracle query. This shows that such a cipher is vulnerable to a chosen plaintext attack. (An encryption oracle can be thought of as a device that, when given a plaintext, returns the corresponding ciphertext. The internal details of the device are not known to you and you cannot break open the device. You can only gain information from the oracle by making queries to it and observing its responses.) Let p be a permutation of the integers 0, 1, 2, c , (2n - 1), such that p(m) gives the permuted value of m, 0 … m 6 2n. Put another way, p maps the set of n-bit integers into itself and no two integers map into the same integer. DES is such a permutation for 64-bit integers. We say that p has a fixed point at m if p(m) = m. That is, if p is an encryption mapping, then a fixed point corresponds to a message that encrypts to itself. We are interested in the number of fixed points in a randomly chosen permutation p. Show the somewhat unexpected result that the number of fixed points for p is 1 on an average, and this number is independent of the size of the permutation. Consider a block encryption algorithm that encrypts blocks of length n, and let N = 2n. Say we have t plaintext–ciphertext pairs Pi, Ci = E(K, Pi), where we assume that the key K selects one of the N! possible mappings. Imagine that we wish to find K by exhaustive search. We could generate key K′ and test whether Ci = E(K′, Pi) for 1 … i … t. If K′ encrypts each Pi to its proper Ci, then we have evidence that K = K′. However, it may be the case that the mappings E(K, # ) and E(K′, # ) exactly agree on the t plaintext–cipher text pairs Pi, Ci and agree on no other pairs. a. What is the probability that E(K, # ) and E(K′, # ) are in fact distinct mappings? b. What is the probability that E(K, # ) and E(K′, # ) agree on another t′ plaintext– ciphertext pairs where 0 … t′ … N - t? For any block cipher, the fact that it is a nonlinear function is crucial to its security. To see this, suppose that we have a linear block cipher EL that encrypts 256-bit blocks of plaintext into 256-bit blocks of ciphertext. Let EL(k, m) denote the encryption of a 256-bit message m under a key k (the actual bit length of k is irrelevant). Thus, EL(k, [m1 ⊕ m2]) = EL(k, m1) ⊕ EL(k, m2) for all 128@bit patterns m1, m2. 4.6 Describe how, with 256 chosen ciphertexts, an adversary can decrypt any ciphertext without knowledge of the secret key k. (A “chosen ciphertext” means that an adversary has the ability to choose a ciphertext and then obtain its decryption. Here, you have 256 plaintext/ciphertext pairs to work with and you have the ability to choose the value of the ciphertexts.) Suppose the DES F function mapped every 32-bit input R, regardless of the value of the input K, to; a. 32-bit string of zero b. R Then 1. What function would DES then compute? 2. What would the decryption look like? Hint: Use the following properties of the XOR operation: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (A ⊕ A) = 0 (A ⊕ 0 ) = A A ⊕ 1 = bitwise complement of A 4.6 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 4.7 4.8 139 where A,B,C are n-bit strings of bits 0 is an n-bit string of zeros 1 is an n-bit string of one Show that DES decryption is, in fact, the inverse of DES encryption. The 32-bit swap after the sixteenth iteration of the DES algorithm is needed to make the encryption process invertible by simply running the ciphertext back through the algorithm with the key order reversed. This was demonstrated in the preceding problem. However, it still may not be entirely clear why the 32-bit swap is needed. To demonstrate why, solve the following exercises. First, some notation: A‘B = the concatenation of the bit strings A and B Ti(R ‘L) = the transformation defined by the ith iteration of the encryption algorithm for 1 … I … 16 TDi(R ‘L) = the transformation defined by the ith iteration of the decryption algorithm for 1 … I … 16 T17(R ‘L) = L ‘R, where this transformation occurs after the sixteenth iteration of the encryption algorithm a. Show that the composition TD1(IP(IP-1(T17(T16(L15 ‘R15))))) is equivalent to the transformation that interchanges the 32-bit halves, L15 and R15. That is, show that TD1(IP(IP-1(T17(T16(L15 ‘R15))))) = R15 ‘L15 b. Now suppose that we did away with the final 32-bit swap in the encryption algorithm. Then we would want the following equality to hold: TD1(IP(IP-1(T16(L15 ‘R15)))) = L15 ‘R15 Does it? Note: The following problems refer to details of DES that are described in Appendix S. 4.9 4.10 4.11 Consider the substitution defined by row 1 of S-box S1 in Table S.2. Show a block diagram similar to Figure 4.2 that corresponds to this substitution. Compute the bits number 4, 17, 41, and 45 at the output of the first round of the DES decryption, assuming that the ciphertext block is composed of all ones and the external key is composed of all ones. This problem provides a numerical example of encryption using a one-round version of DES. We start with the same bit pattern for the key K and the plaintext, namely: Hexadecimal notation: 0123456789ABCDEF Binary notation: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Derive K1, the first-round subkey. Derive L0, R0. Expand R0 to get E[R0], where E[ # ] is the expansion function of Table S.1. Calculate A = E[R0] ⊕ K1. Group the 48-bit result of (d) into sets of 6 bits and evaluate the corresponding S-box substitutions. f. Concatenate the results of (e) to get a 32-bit result, B. a. b. c. d. e. 140 CHAPTER 4 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD 4.12 4.13 4.14 g. Apply the permutation to get P(B). h. Calculate R1 = P(B) ⊕ L0. i. Write down the ciphertext. Analyze the amount of left shifts in the DES key schedule by studying Table S.3 (d). Is there a pattern? What could be the reason for the choice of these constants? When using the DES algorithm for decryption, the 16 keys (K1, K2, c , K16) are used in reverse order. Therefore, the right-hand side of Figure S.1 is not valid for decryption. Design a key-generation scheme with the appropriate shift schedule (analogous to Table S.3d) for the decryption process. a. Let X′ be the bitwise complement of X. Prove that if the complement of the plaintext block is taken and the complement of an encryption key is taken, then the result of DES encryption with these values is the complement of the original ciphertext. That is, If Then 4.15 Y Y′ = = E(K, X) E(K′, X′) Hint: Begin by showing that for any two bit strings of equal length, A and B, (A ⊕ B)′ = A′ ⊕ B. b. It has been said that a brute-force attack on DES requires searching a key space of 256 keys. Does the result of part (a) change that? a. We say that a DES key K is weak if DESK is an involution. Exhibit four weak keys for DES. b. We say that a DES key K is semi-weak if it is not weak and if there exists a key K′ such that DESK- 1 = DESK′. Exhibit four semi-weak keys for DES. Note: The following problems refer to simplified DES, described in Appendix G. 4.16 Refer to Figure G.3, which explains encryption function for S-DES. a. How important is the initial permutation IP? b. How important is the SW function in the middle? 4.17 The equations for the variables q and r for S-DES are defined in the section on S-DES analysis. Provide the equations for s and t. 4.18 Using S-DES, decrypt the string 01000110 using the key 1010000010 by hand. Show intermediate results after each function (IP, FK, SW, FK, IP -1). Then decode the first 4 bits of the plaintext string to a letter and the second 4 bits to another letter where we encode A through P in base 2 (i.e., A = 0000, B = 0001, c , P = 1111). Hint: As a midway check, after the xoring with K2, the string should be 11000001. Programming Problems 4.19 4.20 Create software that can encrypt and decrypt using a general substitution block cipher. Create software that can encrypt and decrypt using S-DES. Test data: use plaintext, ciphertext, and key of Problem 4.18. CHAPTER Finite Fields 5.1 Groups Groups Abelian Group Cyclic Group 5.2 Rings 5.3 Fields 5.4 Finite Fields of the Form GF(p) Finite Fields of Order p Finding the Multiplicative Inverse in GF(p) Summary 5.5 Polynomial Arithmetic Ordinary Polynomial Arithmetic Polynomial Arithmetic with Coefficients in Z p Finding the Greatest Common Divisor Summary 5.6 Finite Fields of the form GF(2n) Motivation Modular Polynomial Arithmetic Finding the Multiplicative Inverse Computational Considerations Using a Generator Summary 5.7 Key Terms, Review Questions, and Problems 141 142 CHAPTER 5 / FINITE FIELDS LEARNING OBJECTIVES After studying this chapter, you should be able to: ◆ Distinguish among groups, rings, and fields. ◆ Define finite fields of the form GF(p). ◆ Explain the differences among ordinary polynomial arithmetic, polynomial arithmetic with coefficients in Z p, and modular polynomial arithmetic in GF(2n). ◆ Define finite fields of the form GF(2n). ◆ Explain the two different uses of the mod operator. Finite fields have become increasingly important in cryptography. A number of cryptographic algorithms rely heavily on properties of finite fields, notably the Advanced Encryption Standard (AES) and elliptic curve cryptography. Other examples include the message authentication code CMAC and the authenticated encryption scheme GCM. This chapter provides the reader with sufficient background on the concepts of finite fields to be able to understand the design of AES and other cryptographic algorithms that use finite fields. Because students unfamiliar with abstract algebra may find the concepts behind finite fields somewhat difficult to grasp, we approach the topic in a way designed to enhance understanding. Our plan of attack is as follows: 1. Fields are a subset of a larger class of algebraic structures called rings, which are in turn a subset of the larger class of groups. In fact, as shown in Figure 5.1, both groups and rings can be further differentiated. Groups are defined by a simple set of properties and are easily understood. Each successive subset (abelian group, ring, commutative ring, and so on) adds additional properties and is thus more complex. Sections 5.1 through 5.3 will examine groups, rings, and fields, successively. 2. Finite fields are a subset of fields, consisting of those fields with a finite number of elements. These are the class of fields that are found in cryptographic algorithms. With the concepts of fields in hand, we turn in Section 5.4 to a specific class of finite fields, namely those with p elements, where p is prime. Certain asymmetric cryptographic algorithms make use of such fields. 3. A more important class of finite fields, for cryptography, comprises those with 2n elements depicted as fields of the form GF(2n). These are used in a wide variety of cryptographic algorithms. However, before discussing these fields, we need to analyze the topic of polynomial arithmetic, which is done in Section 5.5. 4. With all of this preliminary work done, we are able at last, in Section 5.6, to discuss finite fields of the form GF(2n). Before proceeding, the reader may wish to review Sections 2.1 through 2