Cryptography

Chapter6PPT.pptx

Home >Information Systems homework help >Cryptography

Cryptography and Network Security: Principles and Practice

Eighth Edition

Chapter 6

Advanced Encryption Standard

Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings, Chapter 6 – “Advanced Encryption Standard”.

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.

[NECH01], available from NIST, summarizes 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. The essence of the criteria was to develop an algorithm with a high level of security and good performance on a range of systems.

It is worth making additional comment about the performance of AES. Because of the popularity of AES, a number of efforts have been made to improve performance through both software and hardware optimization. Most notably, in 2008, Intel introduced the Advanced Encryption Standard New Instructions (AES-NI) as a hardware extension to the x86 instruction set to improve the speed of encryption and decryption. The AES-NI instruction enables x86 processors to achieve a performance of 0.64 cycles/byte for an authenticated encryption mode known as AES-GCM (described in Chapter 12).

In 2018, Intel added vectorized instructions, referred to as VAES*, to the existing AES-NI for its high-end processors [INTE17]. These instructions are intended to push the performance of AES software further down, to a new theoretical throughput of 0.16 cycles/byte [DRUC18].

AES has become the most widely used symmetric cipher. 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 A. 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. One possible approach is to read the chapter first, then carefully read Appendix A and then re-read the main body of the chapter

Learning Objectives

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).

Finite Field Arithmetic (1 of 2)

In the Advanced Encryption Standard (A E S) all operations are performed on 8-bit bytes

The arithmetic operations of addition, multiplication, and division are performed over the finite field G F(28)

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 Zp consisting of all the integers {0, 1, . . . . , p − 1}, where p is a prime number and in which arithmetic is carried out modulo p

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 Zp consisting of all the integers {0, 1, . . . . , p - 1}, where p is a prime number and in which arithmetic is carried out modulo p .

Finite Field Arithmetic (2 of 2)

If one of the operations used in the algorithm is division, then we need to work in arithmetic defined over a field

Division requires that each nonzero element have a multiplicative inverse

For convenience and for implementation efficiency we would like to work with integers that fit exactly into a given number of bits with no wasted bit patterns

Integers in the range 0 through 2n – 1, which fit into an n-bit word

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

A finite field containing 2n elements is referred to as G F(2n)

Every polynomial in G F(2n) can be represented by an n-bit number

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 ).

Figure 6.1 A E S Encryption Process

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.

Figure 6.2 A E S Data Structures

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.

Table 6.1 A E S Parameters

Key Size (words/bytes/bits)	4/16/128	6/24/192	8/32/256
Plaintext Block Size (words/bytes/bits)	4/16/128	4/16/128	4/16/128
Number of Rounds	10	12	14
Round Key Size (words/bytes/bits)	4/16/128	4/16/128	4/16/128
Expanded Key Size (words/bytes)	44/176	52/208	60/240

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 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.

Figure 6.3 A E S Encryption and Decryption

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.

Detailed Structure (1 of 2)

Processes the entire data block as a single matrix during each round using substitutions and permutation

The key that is provided as input is expanded into an array of forty-four 32-bit words, w[i]

Four different stages are used:

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 X O R of the current block with a portion of the expanded key

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.

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 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.

8. As with most block ciphers, the decryption algorithm makes use of the expanded key in reverse order. However, the decryption algorithm is not 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.

Detailed Structure (2 of 2)

The cipher begins and ends with an AddRoundKey stage

Can view the cipher as alternating operations of X O R encryption (AddRoundKey) of a block, followed by scrambling of the block (the other three stages), followed by X O R encryption, and so on

Each stage is easily reversible

The decryption algorithm makes use of the expanded key in reverse order, however the decryption algorithm is not identical to the encryption algorithm

State is the same for both encryption and decryption

Final round of both encryption and decryption consists of only three stages

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.

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 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.

8. As with most block ciphers, the decryption algorithm makes use of the

expanded key in reverse order. However, the decryption algorithm is not

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.

Figure 6.4 A E S Encryption Round

Figure 6.4 depicts the structure of a full encryption round.

Figure 6.5 A E S Byte-Level Operations

The forward substitute byte transformation, called SubBytes, is a simple table lookup (Figure 6.5a).

Table 6.2 AES S-Boxes (1 of 2)

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}.

Table 6.2 AES S-Boxes (2 of 2)

The inverse substitute byte transformation , called InvSubBytes, makes use

of the inverse S-box shown in Table 6.2b.

Figure 6.6 Construction of S-Box and IS-Box

Construction of S-Box and IS-Box

S-Box Rationale

The S-box is designed to be resistant to known cryptanalytic attacks

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

The nonlinearity is due to the use of the multiplicative inverse

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.

Figure 6.7 A E S Row and Column Operations

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.

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.

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)

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 multiplications are

performed in GF(28 ).

Shift Row Rationale

More substantial than it may first appear

The State, as well as the cipher input and output, is treated as an array of four 4-byte columns

On encryption, the first 4 bytes of the plaintext are copied to the first column of State, and so on

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 distance of a multiple of 4 bytes

Transformation ensures that the 4 bytes of one column are spread out to four different columns

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

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.

Mix Columns Rationale

Coefficients of a matrix based on a linear code with maximal distance between code words 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

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

The 128 bits of State are bitwise XORed with the 128 bits of the round key

Operation is viewed as a columnwise operation between the 4 bytes of a State column and one word of the round key

Can also be viewed as a byte-level operation

Rationale:

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 A E S ensure security

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 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 Inputs for Single A E S Round

Figure 6.8 is another view of a single round of AES, emphasizing the mechanisms

and inputs of each transformation.

A E S Key Expansion

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 four-word round key for the initial AddRoundKey stage and each of the 10 rounds of the cipher

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 X O R is used

For a word whose position in the w array is a multiple of 4, a more complex function is used

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 four word

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 A E S Key Expansion

Figure 6.9 illustrates the generation of the expanded key, using the symbol g to represent that

complex function.

Key Expansion Rationale (1 of 2)

The Rijndael developers designed the expansion key algorithm to be resistant to known cryptanalytic attacks

Inclusion of a round-dependent round constant eliminates the symmetry between the ways in which round keys are generated in different rounds

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.

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.

Key Expansion Rationale (2 of 2)

The specific criteria that were used are:

Knowledge of a part of the cipher key or round key does not enable calculation of many other round-key bits

An invertible transformation

Speed on a wide range of processors

Usage of round constants to eliminate symmetries

Diffusion of cipher key differences into the round keys

Enough nonlinearity to prohibit the full determination of round key differences from cipher key differences only

Simplicity of description

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.

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.

Table 6.3 Example Round Key Calculation

Description	Value
i (decimal)	36
temp = w[i − 1]	7F8D292F
RotWord (temp)	8D292F7F
SubWord (RotWord (temp))	5DA515D2
Rcon (9)	1B000000
SubWord (RotWord (temp)) ⊕ Rcon (9)	46A515D2
w[i − 4]	EAD27321
w[i] = w[i − 4] ⊕ SubWord (RotWord (temp)) ⊕ Rcon (9)	AC7766F3

Table 6.3. Example Round Key Calculation

Table 6.4 Key Expansion for A E S Example (1 of 3)

Key Words	Auxiliary Function
w0 = 0f 15 71 c9 w1 = 47 d9 e8 59 w2 = 0c b7 ad d6 w3 = af 7f 67 98	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
w4 = w0 ⊕ z1 = dc 90 37 b0 w5 = w4 ⊕ w1 = 9b 49 df e9 w6 = w5 ⊕ w2 = 97 fe 72 3f w7 = w6 ⊕ w3 = 38 81 15 a7	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
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	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

Table 6.4 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 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.

Table 6.4 Key Expansion for A E S Example (2 of 3)

Key Words	Auxiliary Function
w12 = w8 ⊕ z3 = c0 af df 39 w13 = w12 ⊕ w9 = 89 2f 6b 67 w14 = w13 ⊕ w10 = 57 51 ad 06 w15 = w14 ⊕ w11 = b1 ae 7e c0	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
w16 = w12 ⊕ z4 = 2c 5c 65 f1 w17 = w16 ⊕ w13 = a5 73 0e 96 w18 = w17 ⊕ w14 = f2 22 a3 90 w19 = w18 ⊕ 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 = w16 ⊕ z5 = 58 9d 36 eb w21 = w20 ⊕ w17 = fd ee 38 7d w22 = w21 ⊕ w18 = 0f cc 9b ed w23 = w22 ⊕ 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

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.

Table 6.4 Key Expansion for A E S Example (3 of 3)

Key Words	Auxiliary Function
w24 = w20 ⊕ z6 = 71 c7 4c c2 w25 = w24 ⊕ w21 = 8c 29 74 bf w26 = w25 ⊕ w22 = 83 e5 ef 52 w27 = w26 ⊕ 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 = w24 ⊕ z7 = 37 14 93 48 w29 = w28 ⊕ w25 = bb 3d e7 f7 w30 = w29 ⊕ w26 = 38 d8 08 a5 w31 = w30 ⊕ 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 = w28 ⊕ z8 = 48 26 45 20 w33 = w32 ⊕ w29 = f3 1b a2 d7 w34 = w33 ⊕ w30 = cb c3 aa 72 w35 = w34 ⊕ 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 = w32 ⊕ z9 = fd 0d 42 cb w37 = w36 ⊕ w33 = 0e 16 e0 1c w38 = w37 ⊕ w34 = c5 d5 4a 6e w39 = w38 ⊕ 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 = w36 ⊕ z10 = b4 8e f3 52 w41 = w40 ⊕ w37 = ba 98 13 4e w42 = w41 ⊕ w38 = 7f 4d 59 20 w43 = w42 ⊕ w39 = 86 26 18 76

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.

Table 6.5 A E S Example (1 of 2)

Start of Round	After SubBytes	After ShiftRows	After MixColumns	Round Key
01 89 fe 76 23 ab dc 54 45 cd ba 32 67 ef 98 10				0f 47 0c af 15 d9 b7 7f 71 e8 ad 67 c9 59 d6 98
0e ce f2 d9 36 72 6b 2b 34 25 17 55 ae b6 4e 88	ab 8b 89 35 05 40 7f f1 18 3f f0 fc e4 4e 2f c4	ab 8b 89 35 40 7f f1 05 f0 fc 18 3f c4 e4 4e 2f	b9 94 57 75 e4 8e 16 51 47 20 9a 3f c5 d6 f5 3b	dc 9b 97 38 90 49 fe 81 37 df 72 15 b0 e9 3f a7
65 0f c0 4d 74 c7 e8 d0 70 ff e8 2a 75 3f ca 9c	4d 76 ba e3 92 c6 9b 70 51 16 9b e5 9d 75 74 de	4d 76 ba e3 c6 9b 70 92 9b e5 51 16 de 9d 75 74	8e 22 db 12 b2 f2 dc 92 df 80 f7 c1 2d c5 1e 52	d2 49 de e6 c9 80 7e ff 6b b4 c6 d3 b7 5e 61 c6
5c 6b 05 f4 7b 72 a2 6d b4 34 31 12 9a 9b 7f 94	4a 7f 6b bf 21 40 3a 3c 8d 18 c7 c9 b8 14 d2 22	4a 7f 6b bf 40 3a 3c 21 c7 c9 8d 18 22 b8 14 d2	b1 c1 0b cc ba f3 8b 07 f9 1f 6a c3 1d 19 24 5c	c0 89 57 b1 af 2f 51 ae df 6b ad 7e 39 67 06 c0
71 48 5c 7d 15 dc da a9 26 74 c7 bd 24 7e 22 9c	a3 52 4a ff 59 86 57 d3 f7 92 c6 7a 36 f3 93 de	a3 52 4a ff 86 57 d3 59 c6 7a f7 92 de 36 f3 93	d4 11 fe 0f 3b 44 06 73 cb ab 62 37 19 b7 07 ec	2c a5 f2 43 5c 73 22 8c 65 0e a3 dd f1 96 90 50
f8 b4 0c 4c 67 37 24 ff ae a5 c1 ea e8 21 97 bc	41 8d fe 29 85 9a 36 16 e4 06 78 87 9b fd 88 65	41 8d fe 29 9a 36 16 85 78 87 e4 06 65 9b fd 88	2a 47 c4 48 83 e8 18 ba 84 18 27 23 eb 10 0a f3	58 fd 0f 4c 9d ee cc 40 36 38 9b 46 eb 7d ed bd

Table 6.5 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.4. 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.

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 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.

Table 6.5 A E S Example (2 of 2)

Start of Round	After SubBytes	After ShiftRows	After MixColumns	Round Key
72 ba cb 04 1e 06 d4 fa b2 20 bc 65 00 6d e7 4e	40 f4 1f f2 72 6f 48 2d 37 b7 65 4d 63 3c 94 2f	40 f4 1f f2 6f 48 2d 72 65 4d 37 b7 2f 63 3c 94	7b 05 42 4a 1e d0 20 40 94 83 18 52 94 c4 43 fb	71 8c 83 cf c7 29 e5 a5 4c 74 ef a9 c2 bf 52 ef
0a 89 c1 85 d9 f9 c5 e5 d8 f7 f7 fb 56 7b 11 14	67 a7 78 97 35 99 a6 d9 61 68 68 0f b1 21 82 fa	67 a7 78 97 99 a6 d9 35 68 0f 61 68 fa b1 21 82	ec 1a c0 80 0c 50 53 c7 3b d7 00 ef b7 22 72 e0	37 bb 38 f7 14 3d d8 7d 93 e7 08 a1 48 f7 a5 4a
db a1 f8 77 18 6d 8b ba a8 30 08 4e ff d5 d7 aa	b9 32 41 f5 ad 3c 3d f4 c2 04 30 2f 16 03 0e ac	b9 32 41 f5 3c 3d f4 ad 30 2f c2 04 ac 16 03 0e	b1 1a 44 17 3d 2f ec b6 0a 6b 2f 42 9f 68 f3 b1	48 f3 cb 3c 26 1b c3 be 45 a2 aa 0b 20 d7 72 38
f9 e9 8f 2b 1b 34 2f 08 4f c9 85 49 bf bf 81 89	99 1e 73 f1 af 18 15 30 84 dd 97 3b 08 08 0c a7	99 1e 73 f1 18 15 30 af 97 3b 84 dd a7 08 08 0c	31 30 3a c2 ac 71 8c c4 46 65 48 eb 6a 1c 31 62	fd 0e c5 f9 0d 16 d5 6b 42 e0 4a 41 cb 1c 6e 56
cc 3e ff 3b a1 67 59 af 04 85 02 aa a1 00 5f 34	4b b2 16 e2 32 85 cb 79 f2 97 77 ac 32 63 cf 18	4b b2 16 e2 85 cb 79 32 77 ac f2 97 18 32 63 cf		b4 ba 7f 86 8e 98 4d 26 f3 13 59 18 52 4e 20 76
ff 08 69 64 0b 53 34 14 84 bf ab 8f 4a 7c 43 b9

Table 6.6 Avalanche Effect in A E S: Change in Plaintext (1 of 2)

Round		Number of Bits that Differ
	0123456789abcdeffedcba9876543210 0023456789abcdeffedcba9876543210	1
0	0e3634aece7225b6f26b174ed92b5588 0f3634aece7225b6f26b174ed92b5588	1
1	657470750fc7ff3fc0e8e8ca4dd02a9c c4a9ad090fc7ff3fc0e8e8ca4dd02a9c	20
2	5c7bb49a6b72349b05a2317ff46d1294 fe2ae569f7ee8bb8c1f5a2bb37ef53d5	58
3	7115262448dc747e5cdac7227da9bd9c ec093dfb7c45343d689017507d485e62	59
4	f867aee8b437a5210c24c1974cffeabc 43efdb697244df808e8d9364ee0ae6f5	61
5	721eb200ba06206dcbd4bce704fa654e 7b28a5d5ed643287e006c099bb375302	68

Using the example from Table 6.5, Table 6.6 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 equiva- lent 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 Avalanche Effect in A E S: Change in Plaintext (2 of 2)

Round		Number of Bits that Differ
6	0ad9d85689f9f77bc1c5f71185e5fb14 3bc2d8b6798d8ac4fe36a1d891ac181a	64
7	db18a8ffa16d30d5f88b08d777ba4eaa 9fb8b5452023c70280e5c4bb9e555a4b	67
8	f91b4fbfe934c9bf8f2f85812b084989 20264e1126b219aef7feb3f9b2d6de40	65
9	cca104a13e678500ff59025f3bafaa34 b56a0341b2290ba7dfdfbddcd8578205	61
10	ff0b844a0853bf7c6934ab4364148fb9 612b89398d0600cde116227ce72433f0	58

Table 6.7 Avalanche Effect in A E S: Change in Key (1 of 2)

Round		Number of Bits that Differ
	0123456789abcdeffedcba9876543210 0123456789abcdeffedcba9876543210	0
0	0e3634aece7225b6f26b174ed92b5588 0f3634aece7225b6f26b174ed92b5588	1
1	657470750fc7ff3fc0e8e8ca4dd02a9c c5a9ad090ec7ff3fc1e8e8ca4cd02a9c	22
2	5c7bb49a6b72349b05a2317ff46d1294 90905fa9563356d15f3760f3b8259985	58
3	7115262448dc747e5cdac7227da9bd9c 18aeb7aa794b3b66629448d575c7cebf	67
4	f867aee8b437a5210c24c1974cffeabc f81015f993c978a876ae017cb49e7eec	63
5	721eb200ba06206dcbd4bce704fa654e 5955c91b4e769f3cb4a94768e98d5267	81

Table 6.7 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.

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.

Table 6.7 Avalanche Effect in A E S: Change in Key (2 of 2)

Round		Number of Bits that Differ
6	0ad9d85689f9f77bc1c5f71185e5fb14 dc60a24d137662181e45b8d3726b2920	70
7	db18a8ffa16d30d5f88b08d777ba4eaa fe8343b8f88bef66cab7e977d005a03c	74
8	f91b4fbfe934c9bf8f2f85812b084989 da7dad581d1725c5b72fa0f9d9d1366a	67
9	cca104a13e678500ff59025f3bafaa34 0ccb4c66bbfd912f4b511d72996345e0	59
10	ff0b844a0853bf7c6934ab4364148fb9 fc8923ee501a7d207ab670686839996b	53

A E S Implementation

A E S decryption cipher is not identical to the encryption cipher

The sequence of transformations differs although the form of the key schedules is the same

Has the disadvantage that two separate software or firmware modules are needed for applications that require both encryption and decryption

Two separate changes are needed to bring the decryption structure in line with the encryption structure

The first two stages of the decryption round need to be interchanged

The second two stages of the decryption round need to be interchanged

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.

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 Inv SubBytes

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

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,

Interchanging AddRoundKey and InvMixColumns

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

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.

Figure 6.10 Equivalent Inverse Cipher

Figure 6.10 illustrates the equivalent decryption algorithm.

Implementation Aspects (1 of 2)

AES can be implemented very efficiently on an 8-bit processor

AddRoundKey is a bytewise XOR operation

ShiftRows is a simple byte-shifting operation

SubBytes operates at the byte level and only requires a table of 256 bytes

MixColumns requires matrix multiplication in the field GF(28), which means that all operations are carried out on bytes

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.

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

way that eliminates the shifts and conditional XORs.

Implementation Aspects (2 of 2)

Can efficiently implement on a 32-bit processor

Redefine steps to use 32-bit words

Can precompute 4 tables of 256-words

Then each column in each round can be computed using 4 table lookups + 4 XORs

At a cost of 4Kb to store tables

Designers believe this very efficient implementation was a key factor in its selection as the AES cipher

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.

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.

Summary

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)

Chapter 6 summary.

This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

.MsftOfcThm_Text1_Fill { fill:#000000; } .MsftOfcThm_MainDark1_Stroke { stroke:#000000; }