CSC432 – INFORMATION SECURITY
Dr. Muhammad Sharjeel
muhammadsharjeel@cuilahore.edu.pk
Lecture No 5
ADVANCED ENCRYPTION STANDARD
Origins of AES
Because of the exhaustive key search and theoretical attacks to break it,
clearly a replacement for DES was needed
Triple-DES can be used but its slow and has small blocks
NIST issued call for ciphers in 1997, 22 submissions, 15 candidates accepted
in Jun 1998
5 were shortlisted in Aug 1999, MARS, RC6, Rijndael, Serpent, Twofish
Winner: Rijndael, two Belgian cryptographers Joan Daemen and Vincent
Rijmen
A slight variation of the Rijndael cipher was selected as AES in Oct 2000
Published by NIST as FIPS PUB 197 standard in Nov 2001
Rijndael Cipher
It is an iterative cipher (operates on entire data block in every round) rather
than Feistel (operate on halves at a time)
It was designed to have characteristics of:
Resistance against all known attacks
Speed and code compactness on a wide range of platforms
Design simplicity
Rijndael allows many block sizes and key sizes
Advanced Encryption Standard
AES is a block cipher with a block length of 128 bits
Allows for three different key lengths: 128, 192, or 256 bits
Encryption consists of 10 rounds of processing for 128-bit keys, 12 rounds
for 192-bit keys, and 14 rounds for 256-bit keys
Nr (number of rounds) = 6 + max{Nb, Nk}
Nb = 32-bit words in the block Nk = 32-bit words in key
For AES-128 with 128-bit key: Nb = 4, Nk = 4, Nr = 10
Matrix = 4 rows × Nb columns
Advanced Encryption Standard
Except for the last round, all other rounds are identical
Each round of processing includes one single-byte based substitution step,
a row-wise permutation step, a column-wise mixing step, and the addition
of the round key
The order in which these four steps are executed is different for encryption
and decryption
So, unlike DES, the decryption algorithm differs substantially from the
encryption algorithm
Advanced Encryption Standard
The input to the AES is a single 128-bit block, consisting of a 4×4 matrix of
bytes, arranged as follows:
This 4 × 4 matrix of bytes is referred to as the state array
Each column of the state array is a word, as is each row
A word consists of four bytes, that is 32 bits
Advanced Encryption Standard
128-bit key is also arranged in the form of matrix of 4 × 4 bytes
As with the input block, the first word from the key fills the first column of the matrix,
and so on
Four column words of the key matrix are expanded into a schedule of 44
words
Advanced Encryption Standard
AES Encryption Process
The input state array is XORed
with the first four words of the
key schedule
1) Substitute bytes
2) Shift rows
3) Mix columns
4) Add round key
The last round for encryption
does not involve the “Mix
columns” step
Advanced Encryption Standard
Substitute Bytes
Byte-by-byte substitution
Size of the lookup table is 16 × 16 (S-Box)
To find the substitute byte for a given input byte;
Divide the input byte into two 4-bit patterns, 0-15 (0 through F)
One of the hex values is used as a row index and the other as a column
index for reaching into the 16×16 lookup table
Substitution byte (for each input byte) is found by using the same lookup
table
Advanced Encryption Standard
Substitute Bytes
Advanced Encryption Standard
Substitute Bytes
Advanced Encryption Standard
Shift Rows
Rotation or transformation consists of;
not shifting the first row of the state array at all
circularly shifting the second row by one byte to the left
circularly shifting the third row by two bytes to the left
circularly shifting the last row by three bytes to the left
Advanced Encryption Standard
Mix Columns
This step replaces each byte of a column by a function of all the bytes in the
same column
Advanced Encryption Standard
Mix Columns
Lookup Table
Advanced Encryption Standard
Key Expansion
128 bits of the state array are bitwise XORed with the 128 bits of the round
key
AES Key Expansion algorithm is used to derive the 128-bit round key from
the original 128-bit encryption key
The algorithm first arranges the 16 bytes of the encryption key in the form
of a 4 × 4 array of bytes
Advanced Encryption Standard
Key Expansion
First four bytes of the encryption key constitute the word w0, the next four
bytes the word w1, and so on
The algorithm subsequently expands the words [w0, w1, w2, w3] into a 44
word key schedule that can be labeled w0, w1, w2, w3, ...., w43
Words [w0, w1, w2, w3] are bitwise XORed with the input block before the
round-based processing begins
The remaining 40 words are used four words at a time in each of the 10
rounds
Advanced Encryption Standard
Key Expansion
Now comes the interesting part;
How does the Key Expansion Algorithm expand four words w0, w1, w2, w3
into the 44 words w0, w1, w2, w3, w4, w5, ...., w43 ?
Advanced Encryption Standard
Key Expansion
Key expansion takes place on a four-word to four-word basis
Each grouping of four words decides what the next grouping of four words
will be
Advanced Encryption Standard
Key Expansion
Let’s say that we have the four words of the round key for the ith round;
wi wi+1 wi+2 wi+3
For these to serve as the round key for the ith round, i must be a multiple of 4
For example, [w4, w5, w6, w7] is the round key for round 1, [w8, w9, w10,
w11] round key for round 2, and so on
Advanced Encryption Standard
Key Expansion
Now (for example) we need to determine the words [w4 w5 w6 w7] from the
words [w0 w1 w2 w3]
We have
w5 = w4 ⊗ w1
w6 = w5 ⊗ w2
w7 = w6 ⊗ w3
Note that except for the first word in a new 4-word grouping, each word is
an XOR of the previous word and the corresponding word in the previous 4-
word grouping
Advanced Encryption Standard
Key Expansion
So now we need to figure out w4 (or the beginning word of each 4-word
grouping in the key expansion)
It is obtained by:
w4 = w0 ⊗ g(w3)
That is, XORing the first word of the last grouping with what is returned by
applying a function g() to the last word of the previous 4-word grouping
Advanced Encryption Standard
Key Expansion
The function g() consists of the following three steps:
1. Perform a one-byte circular rotation on the argument 4-byte word
2. Perform a byte substitution for each byte of the word returned by the
previous step by using the same 16 × 16 lookup table as used in the
SubBytes step of the encryption rounds
3. XOR the bytes obtained from the previous step with what is known as a
round constant
Advanced Encryption Standard
Key Expansion
The round constant is a word whose three rightmost bytes are always zero
Therefore, XORing with the round constant amounts to XORing with just its
leftmost byte
The round constant for the ith round is denoted Rcon[i]
Rcon[i] = (RC[i], 0, 0, 0)
The only non-zero byte in the round constants, RC[i], obeys the following
recursion;
RC[1] = 1
RC[ j] = 2 × RC[ j − 1]
* multiplication is defined over GF(2^8)
Advanced Encryption Standard
Key Expansion
Lets see an example;
The 4th column (w3) of the previous round key is rotated such that each
element is moved up one row
Then put this result through a Sub Box, which replaces each 8 bits of the
matrix with a corresponding 8-bit value from S-Box
Advanced Encryption Standard
Key Expansion
To generate the first column (w4) of the key, this result is XOR-ed with the
first column of the key (w0) as well as a constant (Rcon) which is dependent
on i
Values of Rcon based on i
Advanced Encryption Standard
Key Expansion
The second column (w5) is generated by XORing the 1st column (w4) of the
key with the second column (w1) of the previous round key
This continues for the other two columns in order to generate the entire
round key
Advanced Encryption Standard
What makes AES a strong cipher
Round constant is for the purpose of destroying any symmetries that may
have been introduced by other steps in the key expansion algorithm
Note that if you change one bit of the encryption key, it will affect the round
key for several rounds
AES was published with a probability that it will stay secure for at least 20
years
With 128 bit, (2128 = 3.4 x 1038) possible keys, a computer that tries 255 keys
per second needs 149 billion years to break AES
Advanced Encryption Standard
AES vs DES
AES Key expansion algorithm ensures that AES has no weak keys
A weak key reduces the security of a cipher in a predictable manner
For example, DES is known to have weak keys (alternating ones and zeros), that produce
identical round keys for each of the 16 rounds
A weak key causes all round keys to become identical, which, in turn, causes
the encryption to become self-inverting
That is, plain text encrypted and then encrypted again will lead back to the same plain
text
Since the small number of weak keys of DES are easily recognized, it is not
considered to be a problem with that cipher
References
AES official documentation
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Rijndael Cipher Animation
http://www.codeplanet.eu/files/flash/Rijndael_Animation_v4_eng.swf
Test AES encryption
https://www.openssl.org/
Simplified AES
http://edipermadi.files.wordpress.com/2008/09/s-aes-spec.pdf
“Cryptography and Network Security: Principles and Practice”, 6th edition, by William
Stallings
“Network Security: Private Communication in a Public World”, by Charlie Kaufman, Radia
Perlman, Mike Speciner (chapter 3)
References
Attacks on AES
State of AES attacks as of late 2010:
A. Kaminsky, M. Kurdziel, and S. Radziszowski. An overview of cryptanalysis research for the Advanced
Encryption Standard. IEEE Military Communications Conference 2010 (MILCOM 2010), pages 1853-1859,
San Jose, CA, USA, November 2010.
http://www.cs.rit.edu/~ark/20101102/milcom2010paper.pdf
http://www.cs.rit.edu/~ark/20101102/milcom2010v2.pdf
In August 2011, a key recovery attack (not a related key attack) on the full AES (not reduced-round AES)
better than brute force (but just a little) was published:
A. Bogdanov, D. Khovratovich, and C. Rechberger. Biclique cryptanalysis of the full AES. Cryptology ePrint
Archive, Report 2011/449, August 31, 2011.
http://eprint.iacr.org/2011/449
Breaks AES-128 with 2126.1 work
Breaks AES-192 with 2189.7 work
Breaks AES-256 with 2254.4 work
Also includes new breaks on reduced-round AES and on AES-based hash functions
AES is now (theoretically) broken!
THANKS
