Introduction To Network Security: Theory And Practice (2015)
Chapter 2. Data Encryption Algorithms
2.4 Advanced Encryption Standard
Researchers have never stopped searching for better encryption algorithms that are more efficient, more secure, and more flexible. New encryption algorithms should be able to use longer keys and handle larger blocks. In some applications, people may also want to specify their own key length and block size. Thus, it would be desirable to have key length and block size as parameters.
A number of encryption algorithms have since been devised. Some of the early ones include Blowfish, CAST, GOST (the former Soviet Encryption Standard), International Data Encryption Algorithm (IDEA), LOKI, RC4, RC5, REDOCII, REDOCIII, SAFER, and Skipjack. Most of these encryption algorithms are Feistel ciphers.
Realizing the urgent need to establish a new encryption standard, NIST launched in 1997 the advanced encryption standard competition for selecting a successor to DES. The following encryption algorithms were submitted for consideration: CAST256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER, Serpent, and Twofish, where MARS, RC6, Rijndael, Serpent, and Twofish were selected semifinalists. In November 2001, NIST officially chose Rijndael to be the new AES. Rijndael was devised by Belgian cryptographers Joan Daemen and Vincent Rijmen.
2.4.1 AES Basic Structures
AES is a block cipher, but it is not a Feistel cipher. Its encryption and decryption, although similar, are not symmetrical. The basic computation unit in AES is a byte, rather than a bit as in DES. A byte is an 8bit binary string. AES divides the plaintext string into 128bit blocks. AES can use encryption keys of three different key lengths. An AESencryption key can be 16byte long, 24byte long, or 32byte long. Regardless of what key length is used, AES will generate and use 16byte subkeys, also called round keys. AES can also run a different number of operation rounds. To generate a sufficient number of round keys, AES expands encryption keys depending on the number of rounds and the length of the encryption key specified by the users. Table 2.2 depicts the relations between key lengths, the number of rounds, and the length of expanded encryption keys, where a word is a binary string of length equal to four bytes.
Table 2.2 AES key lengths, the number of rounds, and the length of expanded encryption keys
Key length 
Number of Rounds 
Expansion key length 

Words 
Bytes 
Bits 
Words 
Bytes 
Bits 

4 
16 
128 
10 
44 
176 
1408 
6 
24 
192 
12 
52 
208 
1664 
8 
32 
256 
14 
60 
240 
1920 
AES treats a 128bit block as a sequence of 16 bytes and represents it as a square matrix, where each element is a byte in the block. In particular, let be a plaintext block, where each is a byte. Then AES rewrites as Matrix 2.11:
2.11
We refer to a matrix of bytes as a state matrix. AES encryption executes in each round (except the last round) the same sequence of simple operations on state matrices that transforms the plaintext block into a ciphertext block. These operations are substitutebytes, shiftrows, mixcolumns, and addroundkey.
1. The operation of substitutebytes is a nonlinear operation based on a specially designed substitution box. The purpose of this operation is to resist differential cryptanalysis, linear cryptanalysis, and other mathematical attacks.
2. The operation of shiftrows is an elementary operation on state matrices. It is a linear operation. The purpose of this operation is to produce diffusion.
3. The operation of mixcolumns is also an elementary operation on state matrices. Its purpose is the same as shiftrows.
4. The operation of addroundkey is a simple set of exclusiveOR operations on state matrices. It is a linear operation. The purpose of this operation is to produce confusion.
It is customary to use AES128, AES192, and AES256 to denote, respectively, AES under 128bit keys, 192bit keys, and 256bit keys. These three variants of AES all have the same encryption and decryption structures. They differ only on the number of rounds, where each round uses a different round key.
We describe AES using AES128. AES128 first expands the 128bit key into an array of words. It then rewrites as a sequence of eleven 128bit round keys . In other words,
where .
For convenience, we use sub to denote the operation of substitutebytes, shr the operation of shiftrows, mic the operation of mixcolumns, and ark the operation of addroundkey. Denote by inv_sub (or ) the inverse operation of sub, inv_shr (or ) the inverse operation of shr, and inv_mic (or ) the inverse operation of mic. Figure 2.2 depicts the AES128 encryption and decryption block diagram.
Figure 2.2 AES128 encryption and decryption diagram
In the following several subsections, we describe AES SBoxes, the subkey generation algorithm, the operations of ark, sub, shr, mic, and their inverse operations. We then introduce the Galois field and show how SBoxes are constructed. Skipping the last two topics will not affect the understanding of AES encryption and decryption operations.
2.4.2 AES SBoxes
AES uses only one SBox. It is used to generate subkeys and define the operation of substitute bytes. The AES SBox is a matrix of bytes, which is defined on the basis of the multiplication operation of the Galois field . Unlike the SBoxes used in DES, the AES SBox is a permutation of all 256 bytes. Its reverse permutation is called the reverse SBox.
We only present the SBox and the reverse SBox in this subsection, where each element and index is represented by two hexadecimal digits. We describe how they are constructed in Section 2.4.11. We use
to denote the AES SBox and
to denote its reverse. The SBox is given in Table 2.3, and the reverse SBox is given in Table 2.4.
Table 2.3 The SBox of AES
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
a 
b 
c 
d 
e 
f 

0 
63 
7c 
77 
7b 
f2 
6b 
6f 
c5 
30 
01 
67 
2b 
fe 
d7 
ab 
76 
1 
ca 
82 
c9 
7d 
fa 
59 
47 
f0 
ad 
d4 
a2 
af 
9c 
a4 
72 
c0 
2 
b7 
fd 
93 
26 
36 
3f 
f7 
cc 
34 
a5 
e5 
f1 
71 
d8 
31 
15 
3 
04 
c7 
23 
c3 
18 
96 
05 
9a 
07 
12 
80 
e2 
eb 
27 
b2 
75 
4 
09 
83 
2c 
1a 
1b 
6e 
5a 
a0 
52 
3b 
d6 
b3 
29 
e3 
2f 
84 
5 
53 
d1 
00 
ed 
20 
fc 
b1 
5b 
6a 
cb 
be 
39 
4a 
4c 
58 
cf 
6 
d0 
ef 
aa 
fb 
43 
4d 
33 
85 
45 
f9 
02 
7f 
50 
3c 
9f 
a8 
7 
51 
a3 
40 
8f 
92 
9d 
38 
f5 
bc 
b6 
da 
21 
10 
ff 
f3 
d2 
8 
cd 
0c 
13 
ec 
5f 
97 
44 
17 
c4 
a7 
7e 
3d 
64 
5d 
19 
73 
9 
60 
81 
4f 
dc 
22 
2a 
90 
88 
46 
ee 
b8 
14 
de 
5e 
0b 
db 
a 
e0 
32 
3a 
0a 
49 
06 
24 
5c 
c2 
d3 
ac 
62 
91 
95 
e4 
79 
b 
e7 
c8 
37 
6d 
8d 
d5 
4e 
a9 
6c 
56 
f4 
ea 
65 
7a 
ae 
08 
c 
ba 
78 
25 
2e 
1c 
a6 
b4 
c6 
e8 
dd 
74 
1f 
4b 
bd 
8b 
8a 
d 
70 
3e 
b5 
66 
48 
03 
f6 
0e 
61 
35 
57 
b9 
86 
c1 
1d 
9e 
e 
e1 
f8 
98 
11 
69 
d9 
8e 
94 
9b 
1e 
87 
e9 
ce 
55 
28 
df 
f 
8c 
a1 
89 
0d 
bf 
e6 
42 
68 
41 
99 
2d 
0f 
b0 
54 
bb 
16 
Table 2.4 The reverse SBox of AES
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
a 
b 
c 
d 
e 
f 

0 
52 
09 
6a 
d5 
30 
36 
a5 
38 
bf 
40 
a3 
9e 
81 
f3 
d7 
fb 
1 
7c 
e3 
39 
82 
9b 
2f 
ff 
87 
34 
8e 
43 
44 
c4 
de 
e9 
cb 
2 
54 
7b 
94 
32 
a6 
c2 
23 
3d 
ee 
4c 
95 
0b 
42 
fa 
c3 
4e 
3 
08 
2e 
a1 
66 
28 
d9 
24 
b2 
76 
5b 
a2 
49 
6d 
8b 
d1 
25 
4 
72 
f8 
f6 
64 
86 
68 
98 
16 
d4 
a4 
5c 
cc 
5d 
65 
b6 
92 
5 
6c 
70 
48 
50 
fd 
ed 
b9 
da 
5e 
15 
46 
57 
a7 
8d 
9d 
84 
6 
90 
d8 
ab 
00 
8c 
bc 
d3 
0a 
f7 
e4 
58 
05 
b8 
b3 
45 
06 
7 
d0 
2c 
1e 
8f 
ca 
3f 
0f 
02 
c1 
af 
bd 
03 
01 
13 
8a 
6b 
8 
3a 
91 
11 
41 
4f 
67 
dc 
ea 
97 
f2 
cf 
ce 
f0 
b4 
e6 
73 
9 
96 
ac 
74 
22 
e7 
ad 
35 
85 
e2 
f9 
37 
e8 
1c 
75 
df 
6e 
a 
47 
f1 
1a 
71 
1d 
29 
c5 
89 
6f 
b7 
62 
0e 
aa 
18 
be 
1b 
b 
fc 
56 
3e 
4b 
c6 
d2 
79 
20 
9a 
db 
c0 
fe 
78 
cd 
5a 
f4 
c 
1f 
dd 
a8 
33 
88 
07 
c7 
31 
b1 
12 
10 
59 
27 
80 
ec 
5f 
d 
60 
51 
7f 
a9 
19 
b5 
4a 
0d 
2d 
e5 
7a 
9f 
93 
c9 
9c 
ef 
e 
a0 
e0 
3b 
4d 
ae 
2a 
f5 
b0 
c8 
eb 
bb 
3c 
83 
53 
99 
61 
f 
17 
2b 
04 
7e 
ba 
77 
d6 
26 
e1 
69 
14 
63 
55 
21 
0c 
7d 
Let be a byte, where each is a bit. Define a bytesubstitution function as follows: let denote the binary representation of the row index and denote the binary representation of a column index of in the SBox. Then
2.12
2.13
That is, () is the element on the intersection of the th row and the th column in the SBox . Likewise, is the element on the intersection of the th row and the th column in the inverse SBox .
For example, let , then , and .
It is straightforward to see from the SBox and its reverse that, for any 8bit string , we have
2.4.3 AES128 Round Keys
Let be a 4word encryption key, where each is a 32bit binary string, . AES expands into a 44word array . We first define a byte transformation function as follows:
2.14
where each is a bit. We see in Section 2.4.10 that represents a multiplication operation of 00000010 and over Galois field .
For example,
Let be a nonnegative number. Define () as follows:
2.15
We see in Section 2.4.10 that function () represents the result of multiplying the element 00000010 by itself for times.
We now define a wordsubstitution function that transforms a 32bit string to a 32bit string on the basis of parameter and the AES SBox. Let , where each is a byte. Let be a positive integer. Let
where is the bytesubstitution function defined by Equality 2.12.
We now expand to obtain as follows:
2.4.4 Add Round Keys
Let be an AES128 round key, where . Rewrite as a matrix of bytes:
where each element is a byte and .
In what follows we use
to represent the current state matrix. Initially, (see Matrix 2.11). The addroundkey operation ark is defined as follows:
The inverse operation is the same as ark. That is, . It is straightforward to verify that
2.4.5 SubstituteBytes
The substitutebytes operation sub is defined as follows:
where is the bytesubstitution function defined in Section 2.4.2 (see formula 2.12).
It is straightforward to verify that the inverse operation is given by
where is defined in Section 2.4.2 (see formula 2.13). This is because for any byte , we have , which implies that
2.4.6 ShiftRows
The shiftrow operation shr performs a leftcircularshift times on the th row in the state matrix , where . Its inverse performs a rightcircularshift times on the th row. That is,
It is straightforward to verify that
2.4.7 MixColumns
The mixcolumns operation mic is defined as follows:
where each element in is determined by the following operations
For example, let
2.16
We verify as follows:
The reader is asked to verify the rest of the elements.
Let be a byte and a positive integer. Define
Let
2.17
2.18
2.19
2.20
The inverse operation of is defined by
where each column in is defined as follows:
2.21
2.22
2.23
2.24
We show in Section 2.4.10 that for any state matrix the following relation holds:
2.25
2.4.8 AES128 Encryption
Let be a sequence of state matrices, where is the initial state matrix (i.e., Matrix 2.11), represents the input state matrix at round , and is the ciphertext block , which is in the form of state matrix. Given below are the encryption steps of AES128:
2.4.9 AES128 Decryption and Correctness Proof
Let be a sequence of state matrices, where is the ciphertext block represents the input state matrix at round , and is the output state matrix at round 10. The following are the decryption steps of AES128:
We now show that . We first show the following equality using mathematical induction:
2.26
A proof of Equality 2.26 goes as follows. When , we have
Thus, Equality 2.26 holds. Assume that Equality 2.26 holds for . We have
Thus, Equality 2.26 is true.
Finally, we have
This completes the correctness proof of AES128 decryption.
2.4.10 Galois Fields
In addition to the shiftrows operation, the basic operations of AES are based on the XOR operation and a special multiplication operation on 8bit strings. These two operations and the set of all 8bit strings form a finite field.
A field is an algebraic structure that consists of a set and two operations on elements in . These two operations are addition and multiplication, denoted by and , respectively, which satisfy the following conditions:
1. Closure: .
2. Associativity: :
3. Distributivity: :
4. Unit element: There are elements , where , such that :
The element is called the unit element of the addition operation and the unit element of the multiplication operation.
5. Inverse:
Elements are called, respectively, the additive inverse (denoted by ) and the multiplicative inverse (denoted by .)
6. Commutativity: .
7. Nonzero divisor: If and , then or .
We use to denote a field. It is called a finite field if is a finite set and an infinite field otherwise. The field of real numbers, for example, is the set of all real numbers with the ordinary addition and multiplication operations.
Finite fields have a nice property; namely, any finite field consists of exactly elements for some prime number and integer . A prime number is a positive integer that is divisible only by 1 and by itself. Elements in a finite field of size can be uniquely represented by polynomials of degree with coefficients in the set . A finite field with its elements written in this form is called a Galois field, denoted by . Each element in is represented by the following polynomial
denoted in short by , where each coefficient
The addition operation over is addition modulo of coefficients for terms of the same degree. The multiplication operation first multiplies two polynomials in the normal way. If the degree of the resulting polynomial is greater than , then divide it by a fixedirreducible polynomial of degree , and take the remainder as the result of the multiplication. A polynomial is irreducible if it cannot be expressed as a product of two polynomials whose degrees are at least 1.
Modern electronic computers operate on binary operations using memory with bytes as basic units. Thus, choosing to form the basic operation space for encryption algorithms becomes natural. consists of all 8bit binary strings as elements, where each element represents the following polynomial:
where the addition operation “” is the exclusiveOR operation , and we use them interchangeably when there is no confusion. Thus, the inverse element of any element is . We use to denote the multiplication operation on . The definition of the multiplication operation depends on the chosen irreducible polynomial. AES chooses the following irreducible polynomial:
This irreducible polynomial makes multiplication simple. We use () mod () to denote the remainder polynomial of dividing () by (). It is straightforward to verify that
Hence, we have
Denoting this formula using binary strings and XOR, we have
This is the definition of function defined in Section 2.4.3 (see Formula 2.14). That is,
The function () defined in Section 2.4.3 is the result of multiplying 00000010 by itself for times. That is,
where the number of is .
We now verify Equality 2.25. We first note that and are the products of the following matrix multiplications:
2.27
2.28
The matrix multiplication in this case follows the standard rule, with being the addition operation and the multiplication operation. In particular, we can verify Equality 2.27 from Equalities 2.17 –2.20 by noting that
Likewise, we can verify Equality 2.28 from Equalities 2.21 –2.24 by noting that
Hence,
We can therefore show that by verifying the following equalities, where is the identity matrix of size 4:
2.29
2.30
For example, the first element at the righthand side in Equality 2.29 is
2.4.11 Construction of the AES SBox and Its Inverse
The SBox used by AES is constructed as follows:
1. Initially, is a matrix of all 8bit strings in the lexicographical order. That is, its first row is vector , its second row is vector , and so on, and its last row is vector .
2. Keep the first two elements in (i.e., 00 and 01) unchanged, and replace any other element with its inverse .
For example, as 02's multiplication inverse is 8d, the element 02 is replaced with 8d.
3. Replace each element with , where each bit is determined by
and .
For example, from Step 2 we know that the element at the intersection of the first row and the third column is . Thus,
Hence, .
It is required that each element in the inverse SBox must satisfy the following relations:
Element , where , can be calculated as follows: first find the element ij in . Let . Then let .
For example, as , we have .
2.4.12 AES Security Strength
AES is designed to resist differential cryptanalysis and linear cryptanalysis. It uses 128bit (or longer) encryption keys to resist bruteforce attacks. It modifies each element in the current state matrix in each round, and so it will achieve good diffusion and confusion effects after a few rounds of execution. AES is believed to be superior to DES.
In June 2003, the U.S. government decided that classified government information should be encrypted using AES128, and for TOP SECRET information, AES192 or AES256 must be used. The New European Schemes for Signatures, Integrity, and Encryption (NESSIE) also supported the use of AES. In June 2004, the Institute of Electrical and Electronics Engineers (IEEE) adopted AES in its 802.11i wireless security standard. IEEE 802.11i is also known as WirelessFidelity Protected Access 2 (WiFi WPA 2). Today, AES has been used in almost all network security protocols and software products.
No methods have been found that are efficient enough to be considered serious threats to AES, although certain types of side channel attacks have been discovered. Algebraic attacks, however, have attracted attentions. For example, if the attacker knows a pair of AES128 plaintext and ciphertext blocks, then the attacker may be able to calculate the AES encryption key by solving a system of 1600 quadratic equations of 8000 unknowns. Although solving a system of quadratic equations of this magnitude by today's mathematical theory and computing technology is hopeless, this study opens up a new direction of investigation.