Advanced Encryption

Standard (AES)

Raj Jain
Washington University in Saint Louis
Saint Louis, MO 63130
Jain@cse.wustl.edu
Audio/Video recordings of this lecture are available at:
http://www.cse.wustl.edu/~jain/cse571-17/
Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain
5-1
 Overview

1. AES Structure
2. AES Round Function
3. AES Key Expansion
4. AES Decryption

These slides are based on Lawrie Brown’s slides supplied with William Stalling’s
book “Cryptography and Network Security: Principles and Practice,” 7th Ed, 2017.
Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain
5-2
 Advanced Encryption Standard (AES)
 Published by NIST in Nov 2001: FIPS PUB 197
 Based on a competition won by Rijmen and Daemen (Rijndael)
from Belgium
 22 submissions, 7 did not satisfy all requirements
15 submissions 5 finalists: Mars, RC6, Rijndael, Serpent,
Twofish. Winner: Rijndael.
 Rijndael allows many block sizes and key sizes
 AES restricts it to:
 Block Size: 128 bits

 Key sizes: 128, 192, 256 (AES-128, AES-192, AES-256)

 An iterative rather than Feistel cipher

 operates on entire data block in every round

 Byte operations: Easy to implement in software

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain
5-3
 Basic Structure of AES
 # Rounds Nr = 6 + max{Nb, Nk}
 Nb = 32-bit words in the block
 Nk = 32-bit words in key
 AES-128: 10
 AES-192: 12
 AES-256: 14

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-4
 1. Substitute Bytes
 Each byte is replaced by byte indexed by row (left 4-bits) &
column (right 4-bits) of a 16x16 table

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-5
 2. Shift Rows
 1st row is unchanged
 2nd row does 1 byte circular shift to left
 3rd row does 2 byte circular shift to left
 4th row does 3 byte circular shift to left

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-6
 3. Mix Columns
 Effectively a matrix multiplication in GF(28) using
prime polynomial m(x) =x8+x4+x3+x+1

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-7
 AES Arithmetic
 Uses arithmetic in the finite field GF(28) with irreducible
polynomial
m(x) = x8 + x4 + x3 + x + 1
which is (1 0001 1011) or {11B}
 Example:
 {02} • {87} mod {11B}=(0000 0010)(1000 0111)
= x (x7+x2+x+1) mod (x8+x4+x3+x+1)
= (x8+x3+x2+x) mod (x8+x4+x3+x+1)
= x4+x2+1 = (0001 0101)
 {03} •{6E} = {11}{110 1110} = (x+1) (x6+x5+x3+x2+x) mod (…)
= (x7+x6+x4+x3+x2+x6+x5+x3+x2+x) mod (x8+x4+x3+x+1)
= x7+x5+x4+x ={1011 0010}
 0001 0101⊕1011 0010⊕0100 0110⊕1010 0110=0100 0111=47

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-8
 4. Add Round Key
 XOR state with 128-bits of the round key
Key=0f1571c947d9e8590cb7add6af7f6798
Text=0123456789abcdeffedcba9876543210

01 89 fe 76 0f 47 0c af 0e ce f2 d9
23 ab dc 54 ⊕ 15 d9 b7 7f = 36 72 6b 2b
45 cd ba 32 71 e8 ad 67 34 25 17 55
67 ef 98 10 c9 59 d6 98 ae b6 4e 88
128-bit Text 128-bit Key 128-bit Sum

w0 w1 w2 w3

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-9
 AES Key Expansion
 Use 4-byte subkeys wi. Subkey = 4 words.
For AES-128:
 First subkey (w0,w1,w2,w3) = cipher key
 Other words are calculated as follows:
wi = wi-1 ⊕ wi-4
for all values of i that are not multiples of 4.
 For the words with indices that are a multiple of 4 (w4k):
1. RotWord: Bytes of w4k-1 are rotated left shift (nonlinearity)
2. SubWord: SubBytes fn is applied to all four bytes. (Diffusion)
3. The result rsk is XOR'ed with w4k-4 and a round constant rconk
(breaks Symmetry):
w4k=rsk ⊕ w4k-4 ⊕ rconk
 For AES-192 and AES-256, the key expansion is more
complex.
Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain
5-10
 AES Example Key Expansion
Key=0f1571c947d9e8590cb7add6af7f6798

d6

1st

2nd

10th

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-11
 AES Example Encryption

w5=w4+w1
01+0f=0e dc 47 9b dc = 1101 1100
89+47=ce 90 ⊕ d9 = 49 47 = 0100 0111
37 e8 df 9b = 1001 1011
Washington University in St. Louis
b0http://www.cse.wustl.edu/~jain/cse571-17/
59 e9 ©2017 Raj Jain
5-12
 AES Example Avalanche

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-13
 AES Decryption
 AES decryption is not identical to encryption
 But each step has an inverse

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-14
 Summary

1. AES encrypts 128 bit blocks with 128-bit, 192-bit or 256-bit

keys using 10, 12, or 14 rounds, respectively.
2. Is not a Feistel cipher ⇒ All 128 bits are encrypted
3. Each round = 4 steps of SubBytes, ShiftRows, MixColumns,
and AddRoundKey.
4. Last round has only 3 steps. No MixColumns.
5. Decryption is not the same as encryption (as in DES).
Decryption consists of inverse steps.
Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain
5-15
 Homework 5
Given the plaintext [0001 0203 0405 0607 0809 0A0B 0C0D 0E0F] and the
key [0101 0101 0101 0101 0101 0101 0101 0101]
a. Show the original contents of state, displayed as a 4x4 matrix.
Hint: First Row: 00 04 08 0C
b. Show the value of state after initial AddRoundKey.
Hint: First Row: 01 05 09 0D
c. Show the value of State after SubBytes.
Hint: First Row: 7C 6B 01 D7
d. Show the value of State after ShiftRows.
Hint: First Row: 7C 6B 01 D7
e. Compute the value of State after MixColumns.
Show detailed computations for all elements of the first row.
To practice, you may compute 2nd, 3rd, 4th rows for step e but there is no
need to submit. Submit only the first row for step e.
For all other steps, show all 4 rows.
Hint: First Row: 75 87 0F B2

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-16
 Acronyms
 AES Advance Encryption Standard
 DES Data Encryption Standard
 FIPS Federal Information Processing Standard
 GF Galois Field
 NIST National Institute of Science and Technology
 RC Ron's Code
 XOR Exclusive OR

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-17
Scan This to Download These Slides

Raj Jain
http://rajjain.com

Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain

5-18
 Related Modules
CSE571S: Network Security (Spring 2017),
http://www.cse.wustl.edu/~jain/cse571-17/index.html

CSE473S: Introduction to Computer Networks (Fall 2016),

http://www.cse.wustl.edu/~jain/cse473-16/index.html
Wireless and Mobile Networking (Spring 2016),
http://www.cse.wustl.edu/~jain/cse574-16/index.html
CSE571S: Network Security (Fall 2014),
http://www.cse.wustl.edu/~jain/cse571-14/index.html
Audio/Video Recordings and Podcasts of
Professor Raj Jain's Lectures,
https://www.youtube.com/channel/UCN4-5wzNP9-ruOzQMs-8NUw
Washington University in St. Louis http://www.cse.wustl.edu/~jain/cse571-17/ ©2017 Raj Jain
5-19