Chapter 6: Advanced Encryption Standard PDF

170 CHAPTER 5 / FINITE FIELDS 5.7 5.8 5.9 5.10 5.11 5.12 a. The product of monic polynomials is monic. b. The product of polynomials of degrees m and n has degree m + n. c. The sum of polynomials of degrees m and n has degree max [m, n]. For polynomial arithmetic with coefficients in Z1 1 , pe...

170 CHAPTER 5 / FINITE FIELDS 5.7 5.8 5.9 5.10 5.11 5.12 a. The product of monic polynomials is monic. b. The product of polynomials of degrees m and n has degree m + n. c. The sum of polynomials of degrees m and n has degree max [m, n]. For polynomial arithmetic with coefficients in Z1 1 , perform the following calculations. a. (x 2 + 2 x + 9 )(x 3 + 1 1 x 2 + x + 7 ) b. (8 x 2 + 3 x + 2 )(5 x 2 + 6 ) Determine which of the following polynomials are reducible over GF(2). a. x 2 + 1 b. x 2 + x + 1 c. x 4 + x + 1 Determine the gcd of the following pairs of polynomials. a. (x3 + 1) and (x2 + x + 1) over GF(2) b. (x3 + x + 1) and (x2 + 1) over GF(3) c. (x3 - 2x + 1) and (x2 - x - 2) over GF(5) d. (x4 + 8x3 + 7x + 8) and (2x3 + 9x2 + 10x + 1) over GF(11) Develop a set of tables similar to Table 5.3 for GF(3) with m(x) = x2 + x + 1. Determine the multiplicative inverse of x 2 + 1 in GF(2 3 ) with m (x ) = x 3 + x - 1 . Develop a table similar to Table 5.5 for GF(2 5 ) with m (x ) = x 5 + x 4 + x 3 + x + 1 . Programming Problems 5.13 5.14 Write a simple four-function calculator in GF(24). You may use table lookups for the multiplicative inverses. Write a simple four-function calculator in GF(28). You should compute the multiplicative inverses on the fly. CHAPTER Advanced Encryption Standard 6.1 Finite Field Arithmetic 6.2 AES Structure General Structure Detailed Structure 6.3 AES Transformation Functions Substitute Bytes Transformation ShiftRows Transformation MixColumns Transformation AddRoundKey Transformation 6.4 AES Key Expansion Key Expansion Algorithm Rationale 6.5 An AES Example Results Avalanche Effect 6.6 AES Implementation Equivalent Inverse Cipher Implementation Aspects 6.7 Key Terms, Review Questions, and Problems Appendix 6A Polynomials with Coefficients in GF(28) 171 172 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD LEARNING OBJECTIVES After studying this chapter, you should be able to: ◆ Present an overview of the general structure of Advanced Encryption Standard (AES). ◆ Understand the four transformations used in AES. ◆ Explain the AES key expansion algorithm. ◆ Understand the use of polynomials with coefficients in GF(28). The Advanced Encryption Standard (AES) was published by the National Institute of Standards and Technology (NIST) in 2001. AES is a symmetric block cipher that is intended to replace DES as the approved standard for a wide range of applications. Compared to public-key ciphers such as RSA, the structure of AES and most symmetric ciphers is quite complex and cannot be explained as easily as many other cryptographic algorithms. Accordingly, the reader may wish to begin with a simplified version of AES, which is described in Appendix I. 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 AES.1 One possible approach is to read the chapter first, then carefully read Appendix I, and then re-read the main body of the chapter. Appendix H looks at the evaluation criteria used by NIST to select from among the candidates for AES, plus the rationale for picking Rijndael, which was the winning candidate. This material is useful in understanding not just the AES design but also the criteria by which to judge any symmetric encryption algorithm. 6.1 FINITE FIELD ARITHMETIC In AES, all operations are performed on 8-bit bytes. In particular, the arithmetic operations of addition, multiplication, and division are performed over the finite field GF(28). Section 5.6 discusses such operations in some detail. For the reader who has not studied Chapter 5, and as a quick review for those who have, this section summarizes the important concepts. In essence, a field is a set in which we can do addition, subtraction, multiplication, and division without leaving the set. Division is defined with the following rule: a/b = a(b-1). An example of a finite field (one with a finite number of elements) is the set Z p consisting of all the integers {0, 1, c , p - 1}, where p is a prime number and in which arithmetic is carried out modulo p. 1 However, you may safely skip Appendix I, at least on a first reading. If you get lost or bogged down in the details of AES, then you can go back and start with simplified AES. Hiva-Network.Com 6.1 / FINITE FIELD ARITHMETIC 173 Virtually all encryption algorithms, both conventional and public-key, involve arithmetic operations on integers. If one of the operations used in the algorithm is division, then we need to work in arithmetic defined over a field; this is because division requires that each nonzero element have a multiplicative inverse. For convenience and for implementation efficiency, we would also like to work with integers that fit exactly into a given number of bits, with no wasted bit patterns. That is, we wish to work with integers in the range 0 through 2n - 1, which fit into an n-bit word. Unfortunately, the set of such integers, Z2n, using modular arithmetic, is not a field. For example, the integer 2 has no multiplicative inverse in Z2n, that is, there is no integer b, such that 2b mod 2n = 1. There is a way of defining a finite field containing 2n elements; such a field is referred to as GF(2n). Consider the set, S, of all polynomials of degree n - 1 or less with binary coefficients. Thus, each polynomial has the form n-1 f(x) = an - 1xn - 1 + an - 2xn - 2 + g + a1x + a0 = a aixi i=0 where each ai takes on the value 0 or 1. There are a total of 2n different polynomials in S. For n = 3, the 23 = 8 polynomials in the set are 0 1 x x + 1 x2 x2 + 1 x2 + x x2 + x + 1 With the appropriate definition of arithmetic operations, each such set S is a finite field. The definition consists of the following elements. 1. Arithmetic follows the ordinary rules of polynomial arithmetic using the basic rules of algebra with the following two refinements. 2. Arithmetic on the coefficients is performed modulo 2. This is the same as the XOR operation. 3. If multiplication results in a polynomial of degree greater than n - 1, then the polynomial is reduced modulo some irreducible polynomial m(x) of degree n. That is, we divide by m(x) and keep the remainder. For a polynomial f(x), the remainder is expressed as r(x) = f(x) mod m(x). A polynomial m(x) is called irreducible if and only if m(x) cannot be expressed as a product of two polynomials, both of degree lower than that of m(x). For example, to construct the finite field GF(23), we need to choose an irreducible polynomial of degree 3. There are only two such polynomials: (x3 + x2 + 1) and (x3 + x + 1). Addition is equivalent to taking the XOR of like terms. Thus, (x + 1) + x = 1. A polynomial in GF(2n) can be uniquely represented by its n binary coefficients (an - 1an - 2 c a0). Therefore, every polynomial in GF(2n) can be represented by an n-bit number. Addition is performed by taking the bitwise XOR of the two n-bit elements. There is no simple XOR operation that will accomplish multiplication in GF(2n). However, a reasonably straightforward, easily implemented, technique is available. In essence, it can be shown that multiplication of a number in GF(2n) by 174 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD 2 consists of a left shift followed by a conditional XOR with a constant. Multiplication by larger numbers can be achieved by repeated application of this rule. For example, AES uses arithmetic in the finite field GF(28) with the irreducible polynomial m(x) = x8 + x4 + x3 + x + 1. Consider two elements A = (a7a6 c a1a0) and B = (b7b6 c b1b0). The sum A + B = (c7c6 c c1c0), where ci = ai ⊕ bi. The multiplication {02} # A equals (a6 c a1a00) if a7 = 0 and equals (a6 c a1a00) ⊕ (00011011) if a7 = 1.2 To summarize, AES operates on 8-bit bytes. Addition of two bytes is defined as the bitwise XOR operation. Multiplication of two bytes is defined as multiplication in the finite field GF(28), with the irreducible polynomial3 m(x) = x8 + x4 + x3 + x + 1. The developers of Rijndael give as their motivation for selecting this one of the 30 possible irreducible polynomials of degree 8 that it is the first one on the list given in [LIDL94]. 6.2 AES STRUCTURE General Structure Figure 6.1 shows the overall structure of the AES encryption process. The cipher takes a plaintext block size of 128 bits, or 16 bytes. The key length can be 16, 24, or 32 bytes (128, 192, or 256 bits). The algorithm is referred to as AES-128, AES-192, or AES-256, depending on the key length. The input to the encryption and decryption algorithms is a single 128-bit block. In FIPS PUB 197, this block is depicted as a 4 * 4 square matrix of bytes. This block is copied into the State array, which is modified at each stage of encryption or decryption. After the final stage, State is copied to an output matrix. These operations are depicted in Figure 6.2a. Similarly, the key is depicted as a square matrix of bytes. This key is then expanded into an array of key schedule words. Figure 6.2b shows the expansion for the 128-bit key. Each word is four bytes, and the total key schedule is 44 words for the 128-bit key. Note that the ordering of bytes within a matrix is by column. So, for example, the first four bytes of a 128-bit plaintext input to the encryption cipher occupy the first column of the in matrix, the second four bytes occupy the second column, and so on. Similarly, the first four bytes of the expanded key, which form a word, occupy the first column of the w matrix. The cipher consists of N rounds, where the number of rounds depends on the key length: 10 rounds for a 16-byte key, 12 rounds for a 24-byte key, and 14 rounds for a 32-byte key (Table 6.1). The first N - 1 rounds consist of four distinct transformation functions: SubBytes, ShiftRows, MixColumns, and AddRoundKey, which are described subsequently. The final round contains only three transformations, and there is a initial single transformation (AddRoundKey) before the first round, which can be considered Round 0. Each transformation takes one or more 2 In FIPS PUB 197, a hexadecimal number is indicated by enclosing it in curly brackets. We use that convention in this chapter. 3 In the remainder of this discussion, references to GF(28) refer to the finite field defined with this polynomial. 6.2 / AES STRUCTURE Plaintext—16 bytes (128 bits) Input state (16 bytes) 175 Key—M bytes Round 0 key (16 bytes) Key (M bytes) Initial transformation Round 1 (4 transformations) Round 1 key (16 bytes) Round 1 output state (16 bytes) Round N – 1 (4 transformations) Key expansion State after initial transformation (16 bytes) Round N – 1 key (16 bytes) Round N – 1 output state (16 bytes) Round N (3 transformations) Round N key (16 bytes) Final state (16 bytes) Cipehertext—16 bytes (128 bits) No. of rounds Key Length (bytes) 10 16 12 24 14 32 Figure 6.1 AES Encryption Process 4 * 4 matrices as input and produces a 4 * 4 matrix as output. Figure 6.1 shows that the output of each round is a 4 * 4 matrix, with the output of the final round being the ciphertext. Also, the key expansion function generates N + 1 round keys, each of which is a distinct 4 * 4 matrix. Each round key serves as one of the inputs to the AddRoundKey transformation in each round. 176 in5 in6 in7 k4 k5 k6 k7 in1 in2 in3 k0 k1 k2 k3 k11 k10 k9 k8 in11 in10 in9 in8 k15 k14 k13 k12 in15 in14 in13 in12 Figure 6.2 AES Data Structures in4 in0 w0 s3,0 s2,0 s1,0 s0,0 w1 s3,1 s2,1 s1,1 s0,1 w2 s3,2 s2,2 s1,2 s0,2 s3,0 s2,0 s1,0 s0,0 (b) Key and expanded key (a) Input, state array, and output s3,3 s2,3 s1,3 s0,3



s3,1 s2,1 s1,1 s0,1 s3,2 s2,2 s1,2 s0,2 s3,3 s2,3 s1,3 s0,3 out3 out2 out1 out0 out9 out13 out8 out12 w42 w43 out7 out11 out15 out6 out10 out14 out5 out4 6.2 / AES STRUCTURE 177 Table 6.1 AES Parameters Key Size (words/bytes/bits) Plaintext Block Size (words/bytes/bits) Number of Rounds Round Key Size (words/bytes/bits) Expanded Key Size (words/bytes) 4/16/128 4/16/128 10 4/16/128 44/176 6/24/192 4/16/128 12 4/16/128 52/208 8/32/256 4/16/128 14 4/16/128 60/240 Detailed Structure Figure 6.3 shows the AES cipher in more detail, indicating the sequence of transformations in each round and showing the corresponding decryption function. As was done in Chapter 4, we show encryption proceeding down the page and decryption proceeding up the page. Before delving into details, we can make several comments about the overall AES structure. 1. One noteworthy feature of this structure is that it is not a Feistel structure. Recall that, in the classic Feistel structure, half of the data block is used to modify the other half of the data block and then the halves are swapped. AES instead processes the entire data block as a single matrix during each round using substitutions and permutation. 2. The key that is provided as input is expanded into an array of forty-four 32-bit words, w[i]. Four distinct words (128 bits) serve as a round key for each round; these are indicated in Figure 6.3. 3. Four different stages are used, one of permutation and three of substitution: ■ Substitute bytes: Uses an S-box to perform a byte-by-byte substitution of the block. ■ ShiftRows: A simple permutation. ■ MixColumns: A substitution that makes use of arithmetic over GF(28). ■ AddRoundKey: A simple bitwise XOR of the current block with a portion of the expanded key. 4. The structure is quite simple. For both encryption and decryption, the cipher begins with an AddRoundKey stage, followed by nine rounds that each includes all four stages, followed by a tenth round of three stages. Figure 6.4 depicts the structure of a full encryption round. 5. Only the AddRoundKey stage makes use of the key. For this reason, the cipher begins and ends with an AddRoundKey stage. Any other stage, applied at the beginning or end, is reversible without knowledge of the key and so would add no security. 6. The AddRoundKey stage is, in effect, a form of Vernam cipher and by itself would not be formidable. The other three stages together provide confusion, diffusion, and nonlinearity, but by themselves would provide no security because they do not use the key. We can view the cipher as alternating operations of XOR encryption (AddRoundKey) of a block, followed by scrambling of the Key (16 bytes) Expand key Plaintext (16 bytes) Add round key w[0, 3] Add round key Substitute bytes Inverse sub bytes Shift rows Inverse shift rows Mix columns Inverse mix cols w[4, 7] Inverse sub bytes , , , Inverse shift rows Substitute bytes Round 9 Add round key Shift rows . . . Mix columns Inverse mix cols Add round key w[36, 39] Add round key Substitute bytes Inverse sub bytes Shift rows Inverse shift rows Add round key Round 9 Add round key Round 10 Plaintext (16 bytes) w[40, 43] Round 1 Round 1 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD Round 10 178 Add round key Ciphertext (16 bytes) Ciphertext (16 bytes) (a) Encryption (b) Decryption Figure 6.3 AES Encryption and Decryption block (the other three stages), followed by XOR encryption, and so on. This scheme is both efficient and highly secure. 7. Each stage is easily reversible. For the Substitute Byte, ShiftRows, and MixColumns stages, an inverse function is used in the decryption algorithm. For the AddRoundKey stage, the inverse is achieved by XORing the same round key to the block, using the result that A ⊕ B ⊕ B = A. 8. As with most block ciphers, the decryption algorithm makes use of the expanded key in reverse order. However, the decryption algorithm is not 6.3 / AES TRANSFORMATION FUNCTIONS 179 State S SubBytes S S S S S S S S S S S S S S S State ShiftRows State MixColumns M M M M State r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 AddRoundKey State Figure 6.4 AES Encryption Round identical to the encryption algorithm. This is a consequence of the particular structure of AES. 9. Once it is established that all four stages are reversible, it is easy to verify that decryption does recover the plaintext. Figure 6.3 lays out encryption and decryption going in opposite vertical directions. At each horizontal point (e.g., the dashed line in the figure), State is the same for both encryption and decryption. 10. The final round of both encryption and decryption consists of only three stages. Again, this is a consequence of the particular structure of AES and is required to make the cipher reversible. 6.3 AES TRANSFORMATION FUNCTIONS We now turn to a discussion of each of the four transformations used in AES. For each stage, we describe the forward (encryption) algorithm, the inverse (decryption) algorithm, and the rationale for the stage. 180 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD Substitute Bytes Transformation F ORWARD AND I NVERSE T RANSFORMATIONS The forward substitute byte transformation, called SubBytes, is a simple table lookup (Figure 6.5a). AES defines a 16 * 16 matrix of byte values, called an S-box (Table 6.2a), that contains a permutation of all possible 256 8-bit values. Each individual byte of State is mapped into a new byte in the following way: The leftmost 4 bits of the byte are used as a row value and the rightmost 4 bits are used as a column value. These row and column values serve as indexes into the S-box to select a unique 8-bit output value. For example, the hexadecimal value {95} references row 9, column 5 of the S-box, which contains the value {2A}. Accordingly, the value {95} is mapped into the value {2A}. y x s0,0 s0,1 s0,2 s0,3 s1,0 ¿ s¿ s0,0 0,1 S-box s1,1 s 1,2 s1,3 ¿ s1,0 ¿ ¿ s0,2 s0,3 ¿ s1,1 ¿ ¿ s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 ¿ ¿ ¿ ¿ s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 ¿ ¿ ¿ s3,0 s3,1 s3,2 s¿3,3 (a) Substitute byte transformation s0,0 s1,0 s2,0 s3,0 s0,1 s1,1 s2,1 s3,1 s0,2 s0,3 s1,2 s1,3 ¿ s0,0 wi wi+1 wi+2 wi+3 s2,2 s2,3 ¿ s1,0 = s3,2 s3,3 s2,0 ¿ ¿ s3,0 (b) Add round key transformation Figure 6.5 AES Byte-Level Operations ¿ s0,1 s1,1 ¿ ¿ s2,1 s3,1 ¿ ¿ ¿ s0,2 s0,3 ¿ ¿ s1,2 s1,3 s2,2 s2,3 ¿ ¿ ¿ s3,2 s3,3 ¿ 6.3 / AES TRANSFORMATION FUNCTIONS 181 Table 6.2 AES S-Boxes y x 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 63 7C 77 7B F2 CA 82 C9 7D FA B7 FD 93 26 36 04 C7 23 C3 18 09 83 2C 1A 1B 53 D1 00 ED 20 D0 EF AA FB 43 51 A3 40 8F 92 CD 0C 13 EC 5F 60 81 4F DC 22 E0 32 3A 0A 49 E7 C8 37 6D 8D BA 78 25 2E 1C 70 3E B5 66 48 E1 F8 98 11 69 8C A1 89 0D BF 5 6B 59 3F 96 6E FC 4D 9D 97 2A 06 D5 A6 03 D9 E6 6 6F 47 F7 05 5A B1 33 38 44 90 24 4E B4 F6 8E 42 7 8 9 C5 30 01 F0 AD D4 CC 34 A5 9A 07 12 A0 52 3B 5B 6A CB 85 45 F9 F5 BC B6 17 C4 A7 88 46 EE 5C C2 D3 A9 6C 56 C6 E8 DD 0E 61 35 94 9B 1E 68 41 99 A B C D E F 67 2B FE D7 AB 76 A2 AF 9C A4 72 C0 E5 F1 71 D8 31 15 80 E2 EB 27 B2 75 D6 B3 29 E3 2F 84 BE 39 4A 4C 58 CF 02 7F 50 3C 9F A8 DA 21 10 FF F3 D2 7E 3D 64 5D 19 73 B8 14 DE 5E 0B DB AC 62 91 95 E4 79 F4 EA 65 7A AE 08 74 1F 4B BD 8B 8A 57 B9 86 C1 1D 9E 87 E9 CE 55 28 DF 2D 0F B0 54 BB 16 (a) S-box y x 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 52 09 7C E3 54 7B 08 2E 72 F8 6C 70 90 D8 D0 2C 3A 91 96 AC 47 F1 FC 56 1F DD 60 51 A0 E0 17 2B 2 6A 39 94 A1 F6 48 AB 1E 11 74 1A 3E A8 7F 3B 04 3 D5 82 32 66 64 50 00 8F 41 22 71 4B 33 A9 4D 7E 4 5 6 7 8 30 36 A5 38 BF 9B 2F FF 87 34 A6 C2 23 3D EE 28 D9 24 B2 76 86 68 98 16 D4 FD ED B9 DA 5E 8C BC D3 0A F7 CA 3F 0F 02 C1 4F 67 DC EA 97 E7 AD 35 85 E2 1D 29 C5 89 6F C6 D2 79 20 9A 88 07 C7 31 B1 19 B5 4A 0D 2D AE 2A F5 B0 C8 BA 77 D6 26 E1 (b) Inverse S-box Hiva-Network.Com 9 A B C D E 40 A3 9E 81 F3 D7 8E 43 44 C4 DE E9 4C 95 0B 42 FA C3 5B A2 49 6D 8B D1 A4 5C CC 5D 65 B6 15 46 57 A7 8D 9D E4 58 05 B8 B3 45 AF BD 03 01 13 8A F2 CF CE F0 B4 E6 F9 37 E8 1C 75 DF B7 62 0E AA 18 BE DB C0 FE 78 CD 5A 12 10 59 27 80 EC E5 7A 9F 93 C9 9C EB BB 3C 83 53 99 69 14 63 55 21 0C F FB CB 4E 25 92 84 06 6B 73 6E 1B F4 5F EF 61 7D 182 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD Here is an example of the SubBytes transformation: EA 04 65 85 87 F2 4D 97 83 45 5D 96 EC 6E 4C 90 5C 33 98 B0 F0 2D AD C5 S 4A C3 46 E7 8C D8 95 A6 The S-box is constructed in the following fashion (Figure 6.6a). Byte at row y, column x initialized to yx Byte at row y, column x initialized to yx yx Inverse in GF(28) Byte to bit column vector 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 b2¿ 1 b3¿ = 0 b4¿ 0 b5¿ 1 b6¿ 0 b7¿ b0¿ b1¿ Byte to bit column vector 1 0 b0¿ 1 1 b1¿ 1 1 b2¿ 1 1 b3¿ = 1 1 b4¿ 0 1 b5¿ 0 0 b6¿ 0 0 b7¿ yx 1 1 1 1 0 0 0 1 b0 1 b1 1 b2 0 b3 0 + b4 0 b5 1 b6 1 b7 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 b0 1 b1 0 b2 1 b3 0 + b4 0 b5 0 b6 0 b7 0 Bit column vector to byte Bit column vector to byte Inverse in GF(28) S(yx) IS(yx) (a) Calculation of byte at row y, column x of S-box (a) Calculation of byte at row y, column x of IS-box Figure 6.6 Constuction of S-Box and IS-Box 6.3 / AES TRANSFORMATION FUNCTIONS 183 1. Initialize the S-box with the byte values in ascending sequence row by row. The first row contains {00}, {01}, {02}, c , {0F}; the second row contains {10}, {11}, etc.; and so on. Thus, the value of the byte at row y, column x is {yx}. 2. Map each byte in the S-box to its multiplicative inverse in the finite field GF(28); the value {00} is mapped to itself. 3. Consider that each byte in the S-box consists of 8 bits labeled (b7, b6, b5, b4, b3, b2, b1, b0). Apply the following transformation to each bit of each byte in the S-box: bi= = bi ⊕ b(i + 4) mod 8 ⊕ b(i + 5) mod 8 ⊕ b(i + 6) mod 8 ⊕ b(i + 7) mod 8 ⊕ ci (6.1) where ci is the ith bit of byte c with the value {63}; that is, (c7c6c5c4c3c2c1c0) = (01100011). The prime (′) indicates that the variable is to be updated by the value on the right. The AES standard depicts this transformation in matrix form as follows. b0= 1 b1= 1 = b2 1 b3= 1 H =X = H b4 1 b5= 0 b6= 0 b7= 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 b0 1 1 b1 1 1 b2 0 1 b3 0 XH X + H X 0 b4 0 0 b5 1 0 b6 1 1 b7 0 (6.2) Equation (6.2) has to be interpreted carefully. In ordinary matrix multiplication,4 each element in the product matrix is the sum of products of the elements of one row and one column. In this case, each element in the product matrix is the bitwise XOR of products of elements of one row and one column. Furthermore, the final addition shown in Equation (6.2) is a bitwise XOR. Recall from Section 5.6 that the bitwise XOR is addition in GF(28). As an example, consider the input value {95}. The multiplicative inverse in GF(28) is {95}-1 = {8A}, which is 10001010 in binary. Using Equation (6.2), 1 1 1 1 H 1 0 0 0 4 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 XH X ⊕ H X = H X ⊕ H X = H X 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 For a brief review of the rules of matrix and vector multiplication, refer to Appendix E. 184 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD The result is {2A}, which should appear in row {09} column {05} of the S-box. This is verified by checking Table 6.2a. The inverse substitute byte transformation, called InvSubBytes, makes use of the inverse S-box shown in Table 6.2b. Note, for example, that the input {2A} produces the output {95}, and the input {95} to the S-box produces {2A}. The inverse S-box is constructed (Figure 6.6b) by applying the inverse of the transformation in Equation (6.1) followed by taking the multiplicative inverse in GF(28). The inverse transformation is bi= = b(i + 2) mod 8 ⊕ b(i + 5) mod 8 ⊕ b(i + 7) mod 8 ⊕ d i where byte d = {05}, or 00000101. We can depict this transformation as follows. 0 b0= b1= 1 = b2 0 b3= 1 H =X = H b4 0 b5= 0 b6= 1 b7= 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 b0 1 0 b1 0 1 b2 1 0 b3 0 XH X + H X 0 b4 0 1 b5 0 0 b6 0 0 b7 0 0 1 0 0 1 0 0 1 To see that InvSubBytes is the inverse of SubBytes, label the matrices in SubBytes and InvSubBytes as X and Y, respectively, and the vector versions of constants c and d as C and D, respectively. For some 8-bit vector B, Equation (6.2) becomes B= = XB ⊕ C. We need to show that Y(XB ⊕ C) ⊕ D = B. To multiply out, we must show YXB ⊕ YC ⊕ D = B. This becomes 0 1 0 1 H 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 XH 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 H 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 0 0 XH X ⊕ H X = 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 b0 1 b1 1 b2 1 b X H 3X ⊕ 0 b4 0 b5 0 b6 1 b7 6.3 / AES TRANSFORMATION FUNCTIONS 1 0 0 0 H 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 185 0 b0 1 1 b0 0 b1 0 0 b1 0 b2 1 1 b2 0 b3 0 0 b X H X ⊕ H X ⊕ H X = H 3X 0 b4 0 0 b4 0 b5 0 0 b5 b6 b6 0 0 0 b7 b7 1 0 0 We have demonstrated that YX equals the identity matrix, and the YC = D, so that YC ⊕ D equals the null vector. RATIONALE The S-box is designed to be resistant to known cryptanalytic attacks. Specifically, the Rijndael developers sought a design that has a low correlation between input bits and output bits and the property that the output is not a linear mathematical function of the input [DAEM01]. The nonlinearity is due to the use of the multiplicative inverse. In addition, the constant in Equation (6.1) was chosen so that the S-box has no fixed points [S@box(a) = a] and no “opposite fixed points” [S@box(a) = a], where a is the bitwise complement of a. Of course, the S-box must be invertible, that is, IS@box[S@box(a)] = a. However, the S-box does not self-inverse in the sense that it is not true that S@box(a) = IS@box(a). For example, S@box({95}) = {2A}, but IS@box({95}) = {AD}. ShiftRows Transformation FORWARD AND INVERSE TRANSFORMATIONS The forward shift row transformation, called ShiftRows, is depicted in Figure 6.7a. The first row of State is not altered. For the second row, a 1-byte circular left shift is performed. For the third row, a 2-byte circular left shift is performed. For the fourth row, a 3-byte circular left shift is performed. The following is an example of ShiftRows. 87 F2 4D 97 87 F2 4D 97 EC 6E 4C 90 6E 4C 90 EC 4A C3 46 E7 46 E7 4A C3 8C D8 95 A6 A6 8C D8 95 S The inverse shift row transformation, called InvShiftRows, performs the circular shifts in the opposite direction for each of the last three rows, with a 1-byte circular right shift for the second row, and so on. RATIONALE The shift row transformation is more substantial than it may first appear. This is because the State, as well as the cipher input and output, is treated as an array of four 4-byte columns. Thus, on encryption, the first 4 bytes of the plaintext are copied to the first column of State, and so on. Furthermore, as will be seen, the round key is applied to State column by column. Thus, a row shift moves an individual byte from one column to another, which is a linear 186 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD s0,0 s0,1 s0,2 s0,3 s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s1,1 s1,2 s1,3 s1,0 s2,0 s2,1 s2,2 s2,3 s2,2 s2,3 s2,0 s2,1 s3,0 s3,1 s3,2 s3,3 s3,3 s3,0 s3,1 s3,2 (a) Shift row transformation 2 1 1 3 3 2 1 1 1 3 2 1 1 1 * 3 2 = s0,0 s0,1 s0,2 s0,3 ¿ ¿ ¿ s0,0 s0,1 s0,2 s0,3 ¿ s1,0 s1,1 s1,2 s1,3 ¿ ¿ s1,2 ¿ ¿ s1,0 s1,1 s1,3 s2,0 s2,1 s2,2 s2,3 ¿ ¿ ¿ ¿ s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 ¿ ¿ ¿ ¿ s3,0 s3,1 s3,2 s3,3 (b) Mix column transformation Figure 6.7 AES Row and Column Operations distance of a multiple of 4 bytes. Also note that the transformation ensures that the 4 bytes of one column are spread out to four different columns. Figure 6.4 illustrates the effect. MixColumns Transformation FORWARD AND INVERSE TRANSFORMATIONS The forward mix column transformation, called MixColumns, operates on each column individually. Each byte of a column is mapped into a new value that is a function of all four bytes in that column. The transformation can be defined by the following matrix multiplication on State (Figure 6.7b): 02 01 D 01 03 03 02 01 01 01 03 02 01 01 s0,0 01 s1,0 TD 03 s2,0 02 s3,0 s0,1 s1,1 s2,1 s3,1 s0,2 s1,2 s2,2 s3,2 = s0,3 s0,0 s1,3 s= T = D 1,0 = s2,3 s2,0 = s3,3 s3,0 = s0,1 = s1,1 = s2,1 = s3,1 = s0,2 = s1,2 = s2,2 = s3,2 = s0,3 = s1,3 = T (6.3) s2,3 = s3,3 Each element in the product matrix is the sum of products of elements of one row and one column. In this case, the individual additions and multiplications5 are 5 We follow the convention of FIPS PUB 197 and use the symbol # to indicate multiplication over the finite field GF(28) and ⊕ to indicate bitwise XOR, which corresponds to addition in GF(28). 6.3 / AES TRANSFORMATION FUNCTIONS 187 performed in GF(28). The MixColumns transformation on a single column of State can be expressed as = # # s0, j = (2 s0, j) ⊕ (3 s1, j) ⊕ s2, j ⊕ s3, j = # # s1, j = s0, j ⊕ (2 s1, j) ⊕ (3 s2, j) ⊕ s3, j (6.4) = # # s2, j = s0, j ⊕ s1, j ⊕ (2 s2, j) ⊕ (3 s3, j) = # # s3, j = (3 s0, j) ⊕ s1, j ⊕ s2, j ⊕ (2 s3, j) The following is an example of MixColumns: 87 F2 4D 97 6E 46 4C 90 EC E7 4A C3 A6 8C D8 95 S 47 40 A3 4C 37 D4 70 9F 94 E4 3A 42 ED A5 A6 BC Let us verify the first column of this example. Recall from Section 5.6 that, in GF(28), addition is the bitwise XOR operation and that multiplication can be performed according to the rule established in Equation (4.14). In particular, multiplication of a value by x (i.e., by {02}) can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with (0001 1011) if the leftmost bit of the original value (prior to the shift) is 1. Thus, to verify the MixColumns transformation on the first column, we need to show that ({02} # {87}) {87} {87} ({03} # {87}) ⊕ ⊕ ⊕ ⊕ ({03} # {6E}) ({02} # {6E}) {6E} {6E} ⊕ ⊕ ⊕ ⊕ {46} ({03} # {46}) ({02} # {46}) {46} ⊕ ⊕ ⊕ ⊕ {A6} {A6} ({03} # {A6}) ({02} # {A6}) = = = = {47} {37} {94} {ED} For the first equation, we have {02} # {87} = (0000 1110) ⊕ (0001 1011) = (0001 0101) and {03} # {6E} = {6E} ⊕ ({02} # {6E}) = (0110 1110) ⊕ (1101 1100) = (1011 0010). Then, {02} # {87} {03} # {6E} {46} {A6} = = = = 0001 0101 1011 0010 0100 0110 1010 0110 0100 0111 = {47} The other equations can be similarly verified. The inverse mix column transformation, called InvMixColumns, is defined by the following matrix multiplication: 0E 09 D 0D 0B 0B 0E 09 0D 0D 0B 0E 09 09 s0,0 s1,0 0D TD s2,0 0B s3,0 0E s0,1 s1,1 s2,1 s3,1 s0,2 s1,2 s2,2 s3,2 = s0,3 s0,0 = s1,3 s1,0 T = D = s2,3 s2,0 = s3,3 s3,0 = s0,1 = s1,1 = s2,1 = s3,1 = s0,2 = s1,2 = s2,2 = s3,2 = s0,3 = s1,3 = T s2,3 = s3,3 (6.5) 188 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD It is not immediately clear that Equation (6.5) is the inverse of Equation (6.3). We need to show 0E 09 D 0D 0B 0B 0E 09 0D 0D 0B 0E 09 09 02 0D 01 TD 0B 01 0E 03 03 02 01 01 01 03 02 01 01 s0,0 01 s T D 1,0 03 s2,0 s3,0 02 s0,1 s1,1 s2,1 s3,1 s0,2 s1,2 s2,2 s3,2 s0,3 s0,0 s1,3 s T = D 1,0 s2,3 s2,0 s3,3 s0,3 s0,1 s1,1 s2,1 s3,1 s0,2 s1,2 s2,2 s3,2 s0,3 s1,3 T s2,3 s3,3 which is equivalent to showing 0E 09 D 0D 0B 0B 0E 09 0D 0D 0B 0E 09 09 02 0D 01 TD 0B 01 0E 03 03 02 01 01 01 03 02 01 01 1 01 0 T = D 03 0 02 0 0 1 0 0 0 0 1 0 0 0 T 0 1 (6.6) That is, the inverse transformation matrix times the forward transformation matrix equals the identity matrix. To verify the first column of Equation (6.6), we need to show ({0E} # {02}) ⊕ {0B} ⊕ {0D} ⊕ ({09} # {03}) ({09} # {02}) ⊕ {0E} ⊕ {0B} ⊕ ({0D} # {03}) ({0D} # {02}) ⊕ {09} ⊕ {0E} ⊕ ({0B} # {03}) ({0B} # {02}) ⊕ {0D} ⊕ {09} ⊕ ({0E} # {03}) = = = = {01} {00} {00} {00} For the first equation, we have {0E} # {02} = 00011100 and {09} # {03} = {09} ⊕ ({09} # {02}) = 00001001 ⊕ 00010010 = 00011011. Then {0E} # {02} {0B} {0D} {09} # {03} = = = = 00011100 00001011 00001101 00011011 00000001 The other equations can be similarly verified. The AES document describes another way of characterizing the MixColumns transformation, which is in terms of polynomial arithmetic. In the standard, MixColumns is defined by considering each column of State to be a four-term polynomial with coefficients in GF(28). Each column is multiplied modulo (x4 + 1) by the fixed polynomial a(x), given by a(x) = {03}x3 + {01}x2 + {01}x + {02} (6.7) Appendix 5A demonstrates that multiplication of each column of State by a(x) can be written as the matrix multiplication of Equation (6.3). Similarly, it can be seen that the transformation in Equation (6.5) corresponds to treating 6.3 / AES TRANSFORMATION FUNCTIONS 189 each column as a four-term polynomial and multiplying each column by b(x), given by b(x) = {0B}x3 + {0D}x2 + {09}x + {0E} (6.8) It readily can be shown that b(x) = a -1(x) mod (x4 + 1). RATIONALE The coefficients of the matrix in Equation (6.3) are based on a linear code with maximal distance between code words, which ensures a good mixing among the bytes of each column. The mix column transformation combined with the shift row transformation ensures that after a few rounds all output bits depend on all input bits. See [DAEM99] for a discussion. In addition, the choice of coefficients in MixColumns, which are all {01}, {02}, or {03}, was influenced by implementation considerations. As was discussed, multiplication by these coefficients involves at most a shift and an XOR. The coefficients in InvMixColumns are more formidable to implement. However, encryption was deemed more important than decryption for two reasons: 1. For the CFB and OFB cipher modes (Figures 7.5 and 7.6; described in Chapter 7), only encryption is used. 2. As with any block cipher, AES can be used to construct a message authentication code (Chapter 13), and for this, only encryption is used. AddRoundKey Transformation FORWARD AND INVERSE TRANSFORMATIONS In the forward add round key transformation, called AddRoundKey, the 128 bits of State are bitwise XORed with the 128 bits of the round key. As shown in Figure 6.5b, the operation is viewed as a columnwise operation between the 4 bytes of a State column and one word of the round key; it can also be viewed as a byte-level operation. The following is an example of AddRoundKey: 47 40 A3 4C AC 19 28 57 EB 59 8B 1B 37 D4 70 9F 77 FA D1 5C 40 2E A1 C3 94 E4 3A 42 66 DC 29 00 ED A5 A6 BC F3 21 41 6A ⊕ = F2 38 13 42 1E 84 E7 D6 The first matrix is State, and the second matrix is the round key. The inverse add round key transformation is identical to the forward add round key transformation, because the XOR operation is its own inverse. RATIONALE The add round key transformation is as simple as possible and affects every bit of State. The complexity of the round key expansion, plus the complexity of the other stages of AES, ensure security. Figure 6.8 is another view of a single round of AES, emphasizing the mechanisms and inputs of each transformation. 190 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD State matrix at beginning of round SubBytes S-box ShiftRows 02 01 01 03 03 02 01 01 01 03 02 01 01 01 03 02 MixColumns MixColumns matrix Round key AddRoundKey State matrix at end of round Constant inputs Figure 6.8 Variable input Inputs for Single AES Round 6.4 AES KEY EXPANSION Key Expansion Algorithm The AES key expansion algorithm takes as input a four-word (16-byte) key and produces a linear array of 44 words (176 bytes). This is sufficient to provide a fourword round key for the initial AddRoundKey stage and each of the 10 rounds of the cipher. The pseudocode on the next page describes the expansion. The key is copied into the first four words of the expanded key. The remainder of the expanded key is filled in four words at a time. Each added word w[i] depends on the immediately preceding word, w[i - 1], and the word four positions back, w[i - 4]. In three out of four cases, a simple XOR is used. For a word whose position in the w array is a multiple of 4, a more complex function is used. Figure 6.9 illustrates the generation of the expanded key, using the symbol g to represent that complex function. The function g consists of the following subfunctions. Hiva-Network.Com 6.4 / AES KEY EXPANSION 191 KeyExpansion (byte key[16], word w[44]) { word temp for (i = 0; i < 4; i++) w[i] = (key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]); for (i = 4; i < 44; i++) { temp = w[i − 1]; if (i mod 4 = 0) temp = SubWord (RotWord (temp)) ⊕ Rcon[i/4]; w[i] = w[i−4] ⊕ temp } } k0 k4 k8 k12 k1 k5 k9 k13 k2 k6 k10 k14 k3 k7 k11 k15 w0 w1 w2 w3 w g B0 B1 B2 B3 g B1 B2 B3 B0 S S S S B1' B2' B3' B0' w4 w5 w6 w7 RCj 0 wœ (b) Function g w40 w41 w42 w43 (a) Overall algorithm Figure 6.9 AES Key Expansion 0 0 192 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD 1. RotWord performs a one-byte circular left shift on a word. This means that an input word [B 0, B 1, B 2, B 3] is transformed into [B 1, B 2, B 3, B 0]. 2. SubWord performs a byte substitution on each byte of its input word, using the S-box (Table 6.2a). 3. The result of steps 1 and 2 is XORed with a round constant, Rcon[j]. The round constant is a word in which the three rightmost bytes are always 0. Thus, the effect of an XOR of a word with Rcon is to only perform an XOR on the leftmost byte of the word. The round constant is different for each round and is defined as Rcon[j] = (RC[j], 0, 0, 0), with RC[1] = 1, RC[j] = 2 # RC[j - 1] and with multiplication defined over the field GF(28). The values of RC[j] in hexadecimal are j 1 2 3 4 5 6 7 8 9 10 RC[j] 01 02 04 08 10 20 40 80 1B 36 For example, suppose that the round key for round 8 is EA D2 73 21 B5 8D BA D2 31 2B F5 60 7F 8D 29 2F Then the first 4 bytes (first column) of the round key for round 9 are calculated as follows: i (decimal) 36 temp After RotWord After SubWord Rcon (9) After XOR with Rcon w[i - 4] w[i] = temp ⊕ w[i - 4] 7F8D292F 8D292F7F 5DA515D2 1B000000 46A515D2 EAD27321 AC7766F3 Rationale The Rijndael developers designed the expansion key algorithm to be resistant to known cryptanalytic attacks. The inclusion of a round-dependent round constant eliminates the symmetry, or similarity, between the ways in which round keys are generated in different rounds. The specific criteria that were used are [DAEM99] ■ ■ ■ ■ ■ ■ ■ Knowledge of a part of the cipher key or round key does not enable calculation of many other round-key bits. An invertible transformation [i.e., knowledge of any Nk consecutive words of the expanded key enables regeneration of the entire expanded key (Nk = key size in words)]. Speed on a wide range of processors. Usage of round constants to eliminate symmetries. Diffusion of cipher key differences into the round keys; that is, each key bit affects many round key bits. Enough nonlinearity to prohibit the full determination of round key differences from cipher key differences only. Simplicity of description. 6.5 / AN AES EXAMPLE 193 The authors do not quantify the first point on the preceding list, but the idea is that if you know less than Nk consecutive words of either the cipher key or one of the round keys, then it is difficult to reconstruct the remaining unknown bits. The fewer bits one knows, the more difficult it is to do the reconstruction or to determine other bits in the key expansion. 6.5 AN AES 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 Plaintext: 0123456789abcdeffedcba9876543210 Key: 0f1571c947d9e8590cb7add6af7f6798 Ciphertext: ff0b844a0853bf7c6934ab4364148fb9 Results Table 6.3 shows the expansion of the 16-byte key into 10 round keys. As previously explained, this process is performed word by word, with each four-byte word occupying one column of the word round-key matrix. The left-hand column shows Table 6.3 Key Expansion for AES Example Key Words w0 w1 w2 w3 = = = = 0f 47 0c af 15 d9 b7 7f w4 w5 w6 w7 = = = = w0 w4 w5 w6 ⊕ ⊕ ⊕ ⊕ 71 e8 ad 67 z1 w1 w2 w3 Auxiliary Function c9 59 d6 98 = = = = dc 9b 97 38 90 49 fe 81 37 df 72 15 b0 e9 3f a7 w8 = w4 ⊕ z2 = d2 c9 6b b7 w9 = w8 ⊕ w5 = 49 80 b4 5e w10 = w9 ⊕ w6 = de 7e c6 61 w11 = w10 ⊕ w7 = e6 ff d3 c6 w12 w13 w14 w15 = = = = w8 ⊕ z3 = c0 af df 39 w12 ⊕ w9 = 89 2f 6b 67 w13 ⊕ w10 = 57 51 ad 06 w14 ⊕ w11 = b1 ae 7e c0 RotWord (w3) = 7f 67 98 af = x1 SubWord (x1) = d2 85 46 79 = y1 Rcon (1) = 01 00 00 00 y1 ⊕ Rcon (1) = d3 85 46 79 = z1 RotWord (w7) = 81 15 a7 38 = x2 SubWord (x2) = 0c 59 5c 07 = y2 Rcon (2) = 02 00 00 00 y2 ⊕ Rcon (2) = 0e 59 5c 07 = z2 RotWord (w11) = ff d3 c6 e6 = x3 SubWord (x3) = 16 66 b4 83 = y3 Rcon (3) = 04 00 00 00 y3 ⊕ Rcon (3) = 12 66 b4 8e = z3 RotWord (w15) = ae 7e c0 b1 = x4 SubWord (x4) = e4 f3 ba c8 = y4 Rcon (4) = 08 00 00 00 y4 ⊕ Rcon (4) = ec f3 ba c8 = 4 (Continued) 194 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD Table 6.3 Continued Key Words Auxiliary Function w16 w17 w18 w19 = = = = w12 w16 w17 w18 ⊕ ⊕ ⊕ ⊕ z4 = 2c 5c 65 f1 w13 = a5 73 0e 96 w14 = f2 22 a3 90 w15 = 43 8c dd 50 RotWord (w19) = 8c dd 50 43 = x5 SubWord (x5) = 64 c1 53 1a = y5 Rcon(5) = 10 00 00 00 y5 ⊕ Rcon (5) = 74 c1 53 1a = z5 w20 w21 w22 w23 = = = = w16 w20 w21 w22 ⊕ ⊕ ⊕ ⊕ z5 = 58 9d 36 eb w17 = fd ee 38 7d w18 = 0f cc 9b ed w19 = 4c 40 46 bd RotWord (w23) = 40 46 bd 4c = x6 SubWord (x6) = 09 5a 7a 29 = y6 Rcon(6) = 20 00 00 00 y6 ⊕ Rcon(6) = 29 5a 7a 29 = z6 w24 w25 w26 w27 = = = = w20 w24 w25 w26 ⊕ ⊕ ⊕ ⊕ z6 = 71 c7 4c c2 w21 = 8c 29 74 bf w22 = 83 e5 ef 52 w23 = cf a5 a9 ef RotWord (w27) = a5 a9 ef cf = x7 SubWord (x7) = 06 d3 bf 8a = y7 Rcon (7) = 40 00 00 00 y7 ⊕ Rcon(7) = 46 d3 df 8a = z7 w28 w29 w30 w31 = = = = w24 w28 w29 w30 ⊕ ⊕ ⊕ ⊕ z7 = 37 14 93 48 w25 = bb 3d e7 f7 w26 = 38 d8 08 a5 w27 = f7 7d a1 4a RotWord (w31) = 7d a1 4a f7 = x8 SubWord (x8) = ff 32 d6 68 = y8 Rcon (8) = 80 00 00 00 y8 ⊕ Rcon(8) = 7f 32 d6 68 = z8 w32 w33 w34 w35 = = = = w28 w32 w33 w34 ⊕ ⊕ ⊕ ⊕ z8 = 48 26 45 20 w29 = f3 1b a2 d7 w30 = cb c3 aa 72 w32 = 3c be 0b 3 RotWord (w35) = be 0b 38 3c = x9 SubWord (x9) = ae 2b 07 eb = y9 Rcon (9) = 1B 00 00 00 y9 ⊕ Rcon (9) = b5 2b 07 eb = z9 w36 w37 w38 w39 = = = = w32 w36 w37 w38 ⊕ ⊕ ⊕ ⊕ z9 = fd 0d 42 cb w33 = 0e 16 e0 1c w34 = c5 d5 4a 6e w35 = f9 6b 41 56 RotWord (w39) = 6b 41 56 f9 = x10 SubWord (x10) = 7f 83 b1 99 = y10 Rcon (10) = 36 00 00 00 y10 ⊕ Rcon (10) = 49 83 b1 99 = z10 w40 w41 w42 w43 = = = = w36 w40 w41 w42 ⊕ ⊕ ⊕ ⊕ z10 w37 w38 w39 = = = = b4 ba 7f 86 8e 98 4d 26 f3 13 59 18 52 4e 20 76 the four round-key words generated for each round. The right-hand column shows the steps used to generate the auxiliary word used in key expansion. We begin, of course, with the key itself serving as the round key for round 0. Next, Table 6.4 shows the progression of State through the AES encryption process. The first column shows the value of State at the start of a round. For the first row, State is just the matrix arrangement of the plaintext. The second, third, and fourth columns show the value of State for that round after the SubBytes, ShiftRows, and MixColumns transformations, respectively. The fifth column shows the round key. You can verify that these round keys equate with those shown in Table 6.3. The first column shows the value of State resulting from the bitwise XOR of State after the preceding MixColumns with the round key for the preceding round. Avalanche Effect If a small change in the key or plaintext were to produce a corresponding small change in the ciphertext, this might be used to effectively reduce the size of the 6.5 / AN AES EXAMPLE 195 Table 6.4 AES Example Start of Round After SubBytes After ShiftRows After MixColumns 01 23 45 67 0e 36 34 ae 65 74 70 75 5c 7b b4 9a 71 15 26 24 f8 67 ae e8 72 1e b2 00 0a d9 d8 56 db 18 a8 ff f9 1b 4f bf cc a1 04 a1 ff 0b 84 4a 89 ab cd ef ce 72 25 b6 0f c7 ff 3f 6b 72 34 9b 48 dc 74 7e b4 37 a5 21 ba 06 20 6d 89 f9 f7 7b a1 6d 30 d5 e9 34 c9 bf 3e 67 85 00 08 53 bf 7c fe dc ba 98 f2 6b 17 4e c0 e8 e8 ca 05 a2 31 7f 5c da c7 22 0c 24 c1 97 cb d4 bc e7 c1 c5 f7 11 f8 8b 08 d7 8f 2f 85 81 ff 59 02 5f 69 34 ab 43 76 54 32 10 d9 2b 55 88 4d d0 2a 9c f4 6d 12 94 7d a9 bd 9c 4c ff ea bc 04 fa 65 4e 85 e5 fb 14 77 ba 4e aa 2b 08 49 89 3b af aa 34 64 14 8f b9 ab 05 18 e4 4d 92 51 9d 4a 21 8d b8 a3 59 f7 36 41 85 e4 9b 40 72 37 63 67 35 61 b1 b9 ad c2 16 99 af 84 08 4b 32 f2 32 8b 40 3f 4e 76 c6 16 75 7f 40 18 14 52 86 92 f3 8d 9a 06 fd f4 6f b7 3c a7 99 68 21 32 3c 04 03 1e 18 dd 08 b2 85 97 63 89 7f f0 2f ba 9b 9b 74 6b 3a c7 d2 4a 57 c6 93 fe 36 78 88 1f 48 65 94 78 a6 68 82 41 3d 30 0e 73 15 97 0c 16 cb 77 cf 35 f1 fc c4 e3 70 e5 de bf 3c c9 22 ff d3 7a de 29 16 87 65 f2 2d 4d 2f 97 d9 0f fa f5 f4 2f ac f1 30 3b a7 e2 79 ac 18 ab 40 f0 c4 4d c6 9b de 4a 40 c7 22 a3 86 c6 de 41 9a 78 65 40 6f 65 2f 67 99 68 fa b9 3c 30 ac 99 18 97 a7 4b 85 77 18 8b 7f fc e4 76 9b e5 9d 7f 3a c9 b8 52 57 7a 36 8d 36 87 9b f4 48 4d 63 a7 a6 0f b1 32 3d 2f 16 1e 15 3b 08 b2 cb ac 32 89 f1 18 4e ba 70 51 75 6b 3c 8d 14 4a d3 f7 f3 fe 16 e4 fd 1f 2d 37 3c 78 d9 61 21 41 f4 c2 03 73 30 84 08 16 79 f2 63 35 05 3f 2f e3 92 16 74 bf 21 18 d2 ff 59 92 93 29 85 06 88 f2 72 b7 94 97 35 68 82 f5 ad 04 0e f1 af dd 0c e2 32 97 cf b9 e4 47 c5 8e b2 df 2d b1 ba f9 1d d4 3b cb 19 2a 83 84 eb 7b 1e 94 94 ec 0c 3b b7 b1 3d 0a 9f 31 ac 46 6a 94 8e 20 d6 22 f2 80 c5 c1 f3 1f 19 11 44 ab b7 47 e8 18 10 05 d0 83 c4 1a 50 d7 22 1a 2f 6b 68 30 71 65 1c 57 16 9a f5 db dc f7 1e 0b 8b 6a 24 fe 06 62 07 c4 18 27 0a 42 20 18 43 c0 53 00 72 44 ec 2f f3 3a 8c 48 31 75 51 3f 3b 12 92 c1 52 cc 07 c3 5c 0f 73 37 ec 48 ba 23 f3 4a 40 52 fb 80 c7 ef e0 17 b6 42 b1 c2 c4 eb 62 Round Key 0f 15 71 c9 dc 90 37 b0 d2 c9 6b b7 c0 af df 39 2c 5c 65 f1 58 9d 36 eb 71 c7 4c c2 37 14 93 48 48 26 45 20 fd 0d 42 cb b4 8e f3 52 47 d9 e8 59 9b 49 df e9 49 80 b4 5e 89 2f 6b 67 a5 73 0e 96 fd ee 38 7d 8c 29 74 bf bb 3d e7 f7 f3 1b a2 d7 0e 16 e0 1c ba 98 13 4e 0c b7 ad d6 97 fe 72 3f de 7e c6 61 57 51 ad 06 f2 22 a3 90 0f cc 9b ed 83 e5 ef 52 38 d8 08 a5 cb c3 aa 72 c5 d5 4a 6e 7f 4d 59 20 af 7f 67 98 38 81 15 a7 e6 ff d3 c6 b1 ae 7e c0 43 8c dd 50 4c 40 46 bd cf a5 a9 ef f7 7d a1 4a 3c be 0b 38 f9 6b 41 56 86 26 18 76 196 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD Table 6.5 Avalanche Effect in AES: Change in Plaintext Number of Bits that Differ Round 0 1 2 3 4 5 6 7 8 9 10 0123456789abcdeffedcba9876543210 0023456789abcdeffedcba9876543210 0e3634aece7225b6f26b174ed92b5588 0f3634aece7225b6f26b174ed92b5588 657470750fc7ff3fc0e8e8ca4dd02a9c c4a9ad090fc7ff3fc0e8e8ca4dd02a9c 5c7bb49a6b72349b05a2317ff46d1294 fe2ae569f7ee8bb8c1f5a2bb37ef53d5 7115262448dc747e5cdac7227da9bd9c ec093dfb7c45343d689017507d485e62 f867aee8b437a5210c24c1974cffeabc 43efdb697244df808e8d9364ee0ae6f5 721eb200ba06206dcbd4bce704fa654e 7b28a5d5ed643287e006c099bb375302 0ad9d85689f9f77bc1c5f71185e5fb14 3bc2d8b6798d8ac4fe36a1d891ac181a db18a8ffa16d30d5f88b08d777ba4eaa 9fb8b5452023c70280e5c4bb9e555a4b f91b4fbfe934c9bf8f2f85812b084989 20264e1126b219aef7feb3f9b2d6de40 cca104a13e678500ff59025f3bafaa34 b56a0341b2290ba7dfdfbddcd8578205 ff0b844a0853bf7c6934ab4364148fb9 612b89398d0600cde116227ce72433f0 1 1 20 58 59 61 68 64 67 65 61 58 plaintext (or key) space to be searched. What is desired is the avalanche effect, in which a small change in plaintext or key produces a large change in the ciphertext. Using the example from Table 6.4, Table 6.5 shows the result when the eighth bit of the plaintext is changed. The second column of the table shows the value of the State matrix at the end of each round for the two plaintexts. Note that after just one round, 20 bits of the State vector differ. After two rounds, close to half the bits differ. This magnitude of difference propagates through the remaining rounds. A bit difference in approximately half the positions in the most desirable outcome. Clearly, if almost all the bits are changed, this would be logically equivalent to almost none of the bits being changed. Put another way, if we select two plaintexts at random, we would expect the two plaintexts to differ in about half of the bit positions and the two ciphertexts to also differ in about half the positions. Table 6.6 shows the change in State matrix values when the same plaintext is used and the two keys differ in the eighth bit. That is, for the second case, the key is 0e1571c947d9e8590cb7add6af7f6798. Again, one round produces a significant change, and the magnitude of change after all subsequent rounds is roughly half the bits. Thus, based on this example, AES exhibits a very strong avalanche effect. 6.6 / AES IMPLEMENTATION 197 Table 6.6 Avalanche Effect in AES: Change in Key Number of Bits that Differ Round 0 1 2 3 4 5 6 7 8 9 10 0123456789abcdeffedcba9876543210 0123456789abcdeffedcba9876543210 0e3634aece7225b6f26b174ed92b5588 0f3634aece7225b6f26b174ed92b5588 657470750fc7ff3fc0e8e8ca4dd02a9c c5a9ad090ec7ff3fc1e8e8ca4cd02a9c 5c7bb49a6b72349b05a2317ff46d1294 90905fa9563356d15f3760f3b8259985 7115262448dc747e5cdac7227da9bd9c 18aeb7aa794b3b66629448d575c7cebf f867aee8b437a5210c24c1974cffeabc f81015f993c978a876ae017cb49e7eec 721eb200ba06206dcbd4bce704fa654e 5955c91b4e769f3cb4a94768e98d5267 0ad9d85689f9f77bc1c5f71185e5fb14 dc60a24d137662181e45b8d3726b2920 db18a8ffa16d30d5f88b08d777ba4eaa fe8343b8f88bef66cab7e977d005a03c f91b4fbfe934c9bf8f2f85812b084989 da7dad581d1725c5b72fa0f9d9d1366a cca104a13e678500ff59025f3bafaa34 0ccb4c66bbfd912f4b511d72996345e0 ff0b844a0853bf7c6934ab4364148fb9 fc8923ee501a7d207ab670686839996b 0 1 22 58 67 63 81 70 74 67 59 53 Note that this avalanche effect is stronger than that for DES (Table 4.2), which requires three rounds to reach a point at which approximately half the bits are changed, both for a bit change in the plaintext and a bit change in the key. 6.6 AES IMPLEMENTATION Equivalent Inverse Cipher As was mentioned, the AES decryption cipher is not identical to the encryption cipher (Figure 6.3). That is, the sequence of transformations for decryption differs from that for encryption, although the form of the key schedules for encryption and decryption is the same. This has the disadvantage that two separate software or firmware modules are needed for applications that require both encryption and decryption. There is, however, an equivalent version of the decryption algorithm that has the same structure as the encryption algorithm. The equivalent version has the same sequence of transformations as the encryption algorithm (with transformations replaced by their inverses). To achieve this equivalence, a change in key schedule is needed. 198 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD Two separate changes are needed to bring the decryption structure in line with the encryption structure. As illustrated in Figure 6.3, an encryption round has the structure SubBytes, ShiftRows, MixColumns, AddRoundKey. The standard decryption round has the structure InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns. Thus, the first two stages of the decryption round need to be interchanged, and the second two stages of the decryption round need to be interchanged. INTERCHANGING INVSHIFTROWS AND INVSUBBYTES InvShiftRows affects the sequence of bytes in State but does not alter byte contents and does not depend on byte contents to perform its transformation. InvSubBytes affects the contents of bytes in State but does not alter byte sequence and does not depend on byte sequence to perform its transformation. Thus, these two operations commute and can be interchanged. For a given State Si, InvShiftRows [InvSubBytes (Si)] = InvSubBytes [InvShiftRows (Si)] I NTERCHANGING A DD R OUND K EY AND I NV M IX C OLUMNS The transformations AddRoundKey and InvMixColumns do not alter the sequence of bytes in State. If we view the key as a sequence of words, then both AddRoundKey and InvMixColumns operate on State one column at a time. These two operations are linear with respect to the column input. That is, for a given State Si and a given round key wj, InvMixColumns (Si ⊕ wj) = [InvMixColumns (Si)] ⊕ [InvMixColumns (wj)] To see this, suppose that the first column of State Si is the sequence (y0, y1, y2, y3) and the first column of the round key wj is (k0, k1, k2, k3). Then we need to show 0E 09 D 0D 0B 0B 0E 09 0D 0D 0B 0E 09 09 y0 ⊕ k0 0E 0B 0D y1 ⊕ k1 09 0E TD T = D 0B y2 ⊕ k2 0D 09 0E y3 ⊕ k3 0B 0D 0D 0B 0E 09 09 y0 0E 0B 0D y1 09 0E TD T ⊕ D 0B y2 0D 09 0E y3 0B 0D 0D 0B 0E 09 09 k0 0D k T D 1T 0B k2 0E k3 Let us demonstrate that for the first column entry. We need to show [{0E} # (y0 ⊕ k0)] ⊕ [{0B} # (y1 ⊕ k1)] ⊕ [{0D} # (y2 ⊕ k2)] ⊕ [{09} # (y3 ⊕ k3)] = [{0E} # y0] ⊕ [{0B} # y1] ⊕ [{0D} # y2] ⊕ [{09} # y3] ⊕ [{0E} # k0] ⊕ [{0B} # k1] ⊕ [{0D} # k2] ⊕ [{09} # k3] This equation is valid by inspection. Thus, we can interchange AddRoundKey and InvMixColumns, provided that we first apply InvMixColumns to the round key. Note that we do not need to apply InvMixColumns to the round key for the input to the first AddRoundKey transformation (preceding the first round) nor to the last AddRoundKey transformation (in round 10). This is because these two AddRoundKey transformations are not interchanged with InvMixColumns to produce the equivalent decryption algorithm. Figure 6.10 illustrates the equivalent decryption algorithm. 6.6 / AES IMPLEMENTATION 199 Ciphertext Add round key w[40, 43] Inverse shift rows Inverse mix cols Inverse mix cols Round 1 Inverse sub bytes Add round key w[36, 39] ) ) ) Inverse shift rows Inverse mix cols w[4, 7] Add round key Inverse sub bytes Expand key Inverse shift rows w[0, 3] Add round key Key Plaintext Figure 6.10 Round 10 Inverse mix cols Round 9 Inverse sub bytes Equivalent Inverse Cipher Implementation Aspects The Rijndael proposal [DAEM99] provides some suggestions for efficient implementation on 8-bit processors, typical for current smart cards, and on 32-bit processors, typical for PCs. 8-BIT PROCESSOR AES can be implemented very efficiently on an 8-bit processor. AddRoundKey is a bytewise XOR operation. ShiftRows is a simple byteshifting operation. SubBytes operates at the byte level and only requires a table of 256 bytes. The transformation MixColumns requires matrix multiplication in the field GF(28), which means that all operations are carried out on bytes. MixColumns only requires multiplication by {02} and {03}, which, as we have seen, involved simple shifts, conditional XORs, and XORs. This can be implemented in a more efficient Hiva-Network.Com 200 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD way that eliminates the shifts and conditional XORs. Equation set (6.4) shows the equations for the MixColumns transformation on a single column. Using the identity {03} # x = ({02} # x) ⊕ x, we can rewrite Equation set (6.4) as follows. Tmp = s0, j ⊕ s1, j ⊕ s2, j ⊕ s3, j = # s0, j = s0, j ⊕ Tmp ⊕ [2 (s0, j ⊕ s1, j)] = # s1, (6.9) j = s1, j ⊕ Tmp ⊕ [2 (s1, j ⊕ s2, j)] = s2, j = s2, j ⊕ Tmp ⊕ [2 # (s2, j ⊕ s3, j)] = # s3, j = s3, j ⊕ Tmp ⊕ [2 (s3, j ⊕ s0, j)] Equation set (6.9) is verified by expanding and eliminating terms. The multiplication by {02} involves a shift and a conditional XOR. Such an implementation may be vulnerable to a timing attack of the sort described in Section 4.4. To counter this attack and to increase processing efficiency at the cost of some storage, the multiplication can be replaced by a table lookup. Define the 256-byte table X2, such that X2[i] = {02} # i. Then Equation set (6.9) can be rewritten as Tmp = s0, j ⊕ s1, j ⊕ s2, j ⊕ s3, j = s0, j = s0, j ⊕ Tmp ⊕ X2[s0, j ⊕ s1, j] = s1, c = s1, j ⊕ Tmp ⊕ X2[s1, j ⊕ s2, j] = s2, c = s2, j ⊕ Tmp ⊕ X2[s2, j ⊕ s3, j] = s3, j = s3, j ⊕ Tmp ⊕ X2[s3, j ⊕ s0, j] 32-BIT PROCESSOR The implementation described in the preceding subsection uses only 8-bit operations. For a 32-bit processor, a more efficient implementation can be achieved if operations are defined on 32-bit words. To show this, we first define the four transformations of a round in algebraic form. Suppose we begin with a State matrix consisting of elements ai, j and a round-key matrix consisting of elements ki, j. Then the transformations can be expressed as follows. SubBytes bi, j = S[ai, j] ShiftRows b0, j c0, j c1, j b1, j - 1 T = D T D c2, j b2, j - 2 c3, j b3, j - 3 MixColumns AddRoundKey d 0, j 02 d 1, j 01 D T = D d 2, j 01 d 3, j 03 03 02 01 01 01 03 02 01 c0, j 01 01 c1, j TD T 03 c2, j 02 c3, j e0, j d 0, j k0, j e1, j d 1, j k1, j D T = D T⊕D T e2, j d 2, j k2, j e3, j d 3, j k3, j 6.6 / AES IMPLEMENTATION 201 In the ShiftRows equation, the column indices are taken mod 4. We can combine all of these expressions into a single equation: e0, j 02 e1, j 01 D T = D e2, j 01 e3, j 03 03 02 01 01 01 03 02 01 01 S[a0, j] k0, j 01 S[a1, j - 1] k TD T ⊕ D 1, j T 03 S[a2, j - 2] k2, j 02 S[a3, j - 3] k3, j 03 01 02 02 # 03 01 # = § D T S[a0, j] ¥ ⊕ § D T S[a1, j - 1] ¥ ⊕ § D T # S[a2, j - 2] ¥ 01 02 01 01 01 03 01 k0, j 01 # k ⊕ § D T S[a3, j - 3] ¥ ⊕ D 1, j T 03 k2, j 02 k3, j In the second equation, we are expressing the matrix multiplication as a linear combination of vectors. We define four 256-word (1024-byte) tables as follows. 02 03 01 01 01 02 03 01 T0[x] = § D T # S[x] ¥ T1[x] = § D T # S[x] ¥ T2[x] = § D T # S[x] ¥ T3[x] = § D T # S[x] ¥ 01 01 02 03 03 01 01 02 Thus, each table takes as input a byte value and produces a column vector (a 32-bit word) that is a function of the S-box entry for that byte value. These tables can be calculated in advance. We can define a round function operating on a column in the following fashion. = s0, j = s1, D = j T = T0[s0, j] ⊕ T1[s1, j - 1] ⊕ T2[s2, j - 2] ⊕ T3[s3, j - 3] ⊕ s2, j = s3, j k0, j k D 1, j T k2, j k3, j As a result, an implementation based on the preceding equation requires only four table lookups and four XORs per column per round, plus 4 Kbytes to store the table. The developers of Rijndael believe that this compact, efficient implementation was probably one of the most important factors in the selection of Rijndael for AES. 202 CHAPTER 6 / ADVANCED ENCRYPTION STANDARD 6.7 KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS Key Terms Advanced Encryption Standard (AES) avalanche effect field finite field irreducible polynomial key expansion National Institute of Standards and Technology (NIST) Rijndael S-box Review Questions 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12 6.13 6.14 What was the original set of criteria used by NIST to evaluate candidate AES ciphers? What was the final set of criteria used by NIST to evaluate candidate AES ci