Understanding Cryptography by Christof Paar and Jan Pelzl
www.crypto-textbook.com
Chapter 4 – The Advanced Encryption Standard (AES)
ver. October 28, 2009
These slides were prepared by Daehyun Strobel, Christof Paar and Jan Pelzl
2/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Some legal stuff (sorry): Terms of Use
• The slides can used free of charge. All copyrights for the slides remain with Christof Paar and Jan Pelzl.
• The title of the accompanying book “Understanding Cryptography” by Springer and the author’s names must remain on each slide.
• If the slides are modified, appropriate credits to the book authors and the book title must remain within the slides.
• It is not permitted to reproduce parts or all of the slides in printed form whatsoever without written consent by the authors.
3/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Content of this Chapter
• Overview of the AES algorithm
• Internal structure of AES
• Byte Substitution layer
• Diffusion layer
• Key Addition layer
• Key schedule
• Decryption
• Practical issues
4/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Content of this Chapter
• Overview of the AES algorithm
• Internal structure of AES
• Byte Substitution layer
• Diffusion layer
• Key Addition layer
• Key schedule
• Decryption
• Practical issues
5/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Some Basic Facts
• AES is the most widely used symmetric cipher today
• ThealgorithmforAESwaschosenbytheUSNationalInstituteofStandards and Technology (NIST) in a multi-year selection process
• TherequirementsforallAEScandidatesubmissionswere: • Block cipher with 128-bit block size
• Three supported key lengths: 128, 192 and 256 bit • Security relative to other submitted algorithms
• Efficiency in software and hardware
6/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Chronology of the AES Selection
• The need for a new block cipher announced by NIST in January, 1997
• 15 candidates algorithms accepted in August, 1998
• 5 finalists announced in August, 1999: • Mars – IBM Corporation
• RC6 – RSA Laboratories
• Rijndael – J. Daemen & V. Rijmen • Serpent – Eli Biham et al.
• Twofish – B. Schneier et al.
• In October 2000, Rijndael was chosen as the AES
• AES was formally approved as a US federal standard in November 2001
7/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
AES: Overview
The number of rounds depends on the chosen key length:
Key length (bits)
Number of rounds
128 192 256
10 12 14
8/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
AES: Overview
• Iterated cipher with 10/12/14 rounds
• Each round consists of “Layers”
9/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Content of this Chapter
• Overview of the AES algorithm
• Internal structure of AES
• Byte Substitution layer
• Diffusion layer
• Key Addition layer
• Key schedule
• Decryption
• Practical issues
10/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Internal Structure of AES
• AES is a byte-oriented cipher
• The state A (i.e., the 128-bit data path) can be arranged in a 4×4 matrix:
with A0,…, A15 denoting the 16-byte input of AES
A0 A4 A8 A12 A1 A5 A9 A13
A2 A6 A10 A14
A3 A7 A11 A15
11/28
• Note: In the last round, the MixColumn tansformation is omitted Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Internal Structure of AES
• Round function for rounds 1,2,…,nr-1:
12/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Byte Substitution Layer
• The Byte Substitution layer consists of 16 S-Boxes with the
following properties:
The S-Boxes are
• identical
• the only nonlinear elements of AES, i.e.,
ByteSub(Ai) + ByteSub(Aj) ≠ ByteSub(Ai + Aj), for i,j = 0,…,15
• bijective, i.e., there exists a one-to-one mapping of input and output bytes
⇒ S-Box can be uniquely reversed
• In software implementations, the S-Box is usually realized as a lookup table
13/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Diffusion Layer The Diffusion layer
• provides diffusion over all input state bits
• consists of two sublayers:
• ShiftRows Sublayer: Permutation of the data on a byte level
• MixColumn Sublayer: Matrix operation which combines (“mixes”) blocks of four bytes
• performs a linear operation on state matrices A, B, i.e., DIFF(A) + DIFF(B) = DIFF(A + B)
14/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
ShiftRows Sublayer
• Rows of the state matrix are shifted cyclically:
Input matrix
B0 B4 B1 B5 B2 B6 B3 B7
B8 B12
B9 B13
B10 B14
B11 B15
Output matrix
B0 B4 B5 B9
B8 B12 B13 B1 B2 B6 B7 B11
no shift
← one position left shift ← two positions left shift ← three positions left shift
B10 B14 B15 B3
15/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
MixColumn Sublayer
• Linear transformation which mixes each column of the
state matrix
• Each 4-byte column is considered as a vector and multiplied by a fixed 4×4 matrix, e.g.,
C 02 03 01 01 B 0 0
C = 01 02 03 01 ⋅ B 1 5
C 01 01 02 03 B
2 C
10 03 01 01 02 B
3
where 01, 02 and 03 are given in hexadecimal notation
• All arithmetic is done in the Galois field GF(28) (for more information see Chapter 4.3 in Understanding Cryptography)
15
16/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Key Addition Layer
• Inputs:
• 16-byte state matrix C • 16-byte subkey ki
• Output: C ⊕ ki
• The subkeys are generated in the key schedule
17/28
• There are different key schedules for the different key sizes Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Key Schedule
• Subkeys are derived recursively from the original 128/192/256-bit input key
• Each round has 1 subkey, plus 1 subkey at the beginning of AES
Key length (bits)
Number of subkeys
128 192 256
11 13 15
• Key whitening: Subkey is used both at the input and output of AES ⇒ # subkeys = # rounds + 1
18/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Key Schedule
Example: Key schedule for 128-bit key AES
• Word-oriented: 1 word = 32 bits
• 11 subkeys are stored in W[0]…W[3], W[4]…W[7], … , W[40]…W[43]
• First subkey W[0]…W[3] is the original AES key
19/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Key Schedule
• Function g rotates its four input bytes and performs a bytewise S-Box substitution
⇒ nonlinearity
• The round coefficient RC is only added to the leftmost
byte and varies from round to round:
RC[1] = x0 = (00000001)2 RC[2] = x1 = (00000010)2 RC[3] = x2 = (00000100)2 …
RC[10] = x9 = (00110110)2
• xi represents an element in a Galois field
(again, cf. Chapter 4.3 of Understanding Cryptography)
20/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Content of this Chapter
• Overview of the AES algorithm
• Internal structure of AES
• Byte Substitution layer
• Diffusion layer
• Key Addition layer
• Key schedule
• Decryption
• Practical issues
21/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Decryption
• AES is not based on a Feistel network
⇒ All layers must be inverted for decryption:
• MixColumn layer → Inv MixColumn layer
• ShiftRows layer→ Inv ShiftRows layer
• Byte Substitution layer → Inv Byte Substitution layer
• Key Addition layer is its own inverse
22/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Decryption
• Inv MixColumn layer:
• To reverse the MixColumn operation, each column of the state matrix C must be multiplied with the inverse of the 4×4 matrix, e.g.,
B 0E 0B 0D 09C 0 0
B = 09 0E 0B 0D ⋅ C 1 1
B 0D 09 0E 0B C 2 2
B 0B 0D 09 0E C 3 3
where 09, 0B, 0D and 0E are given in hexadecimal notation
• Again, all arithmetic is done in the Galois field GF(28) (for more information see Chapter 4.3 in Understanding Cryptography)
23/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Decryption
• Inv ShiftRows layer:
• All rows of the state matrix B are shifted to the opposite direction:
Input matrix
B0 B4 B1 B5 B2 B6 B3 B7
B8 B12 B9 B13 B10 B14 B11 B15
Output matrix
B0 B4 B13 B1
B8 B12 B5 B9 B2 B6 B15 B3
no shift
→ one position right shift → two positions right shift → three positions right shift
B10 B14 B7 B11
24/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Decryption
• Inv Byte Substitution layer:
• Since the S-Box is bijective, it is possible to construct an inverse, such that
Ai = S-1(Bi) = S-1(S(Ai))
⇒ The inverse S-Box is used for decryption. It is usually realized as a lookup
table
• Decryption key schedule:
• Subkeys are needed in reversed order (compared to encryption)
• In practice, for encryption and decryption, the same key schedule is used. This requires that all subkeys must be computed before the encryption of the first block can begin
25/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Content of this Chapter
• Overview of the AES algorithm
• Internal structure of AES
• Byte Substitution layer
• Diffusion layer
• Key Addition layer
• Key schedule
• Decryption
• Practical issues
26/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Implementation in Software
• One requirement of AES was the possibility of an efficient software implementation
• Straightforward implementation is well suited for 8-bit processors (e.g., smart cards), but inefficient on 32-bit or 64-bit processors
• A more sophisticated approach: Merge all round functions (except the key addition) into one table look-up
• This results in four tables with 256 entries, where each entry is 32 bits wide • One round can be computed with 16 table look-ups
• Typical SW speeds are more than 1.6 Gbit/s on modern 64-bit processors
27/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl
Security
• Brute-force attack: Due to the key length of 128, 192 or 256
bits, a brute-force attack is not possible
• Analytical attacks: There is no analytical attack known that is better than brute-force
• Side-channel attacks:
• Several side-channel attacks have been published
• Note that side-channel attacks do not attack the underlying algorithm but the implementation of it
Lessons Learned
• AES is a modern block cipher which supports three key lengths of 128, 192 and 256 bit. It provides excellent long-term security against brute-force attacks.
• AES has been studied intensively since the late 1990s and no attacks have been found that are better than brute-force.
• AES is not based on Feistel networks. Its basic operations use Galois field arithmetic and provide strong diffusion and confusion.
• AES is part of numerous open standards such as IPsec or TLS, in addition to being the mandatory encryption algorithm for US government applications. It seems likely that the cipher will be the dominant encryption algorithm for many years to come.
• AES is efficient in software and hardware.
28/28
Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl