Advanced Encryption Standard
Origins
• clear a replacement for DES was needed
• have theoretical attacks that can break it
• have demonstrated exhaustive key search attacks
• can use Triple-DES – but slow, has small blocks
• US NIST issued call for ciphers in 1997
• 15 candidates accepted in Jun 98
• 5 were shortlisted in Aug-99
• Rijndael was selected as the AES in Oct-2000
• issued as FIPS PUB 197 standard in Nov-2001
The AES Cipher - Rijndael
• designed by Rijmen-Daemen in Belgium
• has 128/192/256 bit keys, 128 bit data
• an iterative rather than feistel cipher
• processes data as block of 4 columns of 4 bytes
• operates on entire data block in every round
• designed to be:
• resistant against known attacks
• speed and code compactness on many CPUs
• design simplicity
AES Encryption
Process
AES Structure
data block of 4 columns of 4 bytes is state
key is expanded to array of words
has 9/11/13 rounds in which state undergoes:
byte substitution (1 S-box used on every byte)
shift rows (permute bytes between groups/columns)
mix columns (subs using matrix multiply of groups)
add round key (XOR state with key material)
view as alternating XOR key & scramble data bytes
initial XOR key material & incomplete last round
with fast XOR & table lookup implementation
AES Structure
Some Comments on AES
1. an iterative rather than feistel cipher
2. key expanded into array of 32-bit words
1. four words form round key in each round
3. 4 different stages are used as shown
4. has a simple structure
5. only AddRoundKey uses key
6. AddRoundKey a form of Vernam cipher
7. each stage is easily reversible
8. decryption uses keys in reverse order
9. decryption does recover plaintext
10. final round has only 3 stages
Substitute Bytes
• a simple substitution of each byte
• uses one table of 16x16 bytes containing a
permutation of all 256 8-bit values
• each byte of state is replaced by byte indexed by
row (left 4-bits) & column (right 4-bits)
• eg. byte {95} is replaced by byte in row 9 column 5
• which has value {2A}
• S-box constructed using defined transformation of
values in GF(28)
• designed to be resistant to all known attacks
Substitute Bytes
Substitute Bytes Example
Shift Rows
• a circular byte shift in each each
• 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
• decrypt inverts using shifts to right
• since state is processed by columns, this step
permutes bytes between the columns
Shift Rows
Mix Columns
• each column is processed separately
• each byte is replaced by a value dependent on all 4 bytes in the
column
• effectively a matrix multiplication in GF(28) using prime poly m(x)
=x8+x4+x3+x+1
Mix Columns
Mix Columns Example
Mix Columns
• can express each col as 4 equations
• to derive each new byte in col
• decryption requires use of inverse matrix
• with larger coefficients, hence a little harder
• have an alternate characterisation
• each column a 4-term polynomial
• with coefficients in GF(28)
• and polynomials multiplied modulo (x4+1)
• coefficients based on linear code with maximal distance between
codewords
Add Round Key
XOR state with 128-bits of the round key
again processed by column (though effectively a series of byte
operations)
inverse for decryption identical
since XOR own inverse, with reversed keys
designed to be as simple as possible
a form of Vernam cipher on expanded key
requires other stages for complexity / security
Add Round Key
AES Round
AES Key Expansion
takes 128-bit (16-byte) key and expands into array of 44/52/60 32-
bit words
start by copying key into first 4 words
then loop creating words that depend on values in previous & 4
places back
in 3 of 4 cases just XOR these together
1st word in 4 has rotate + S-box + XOR round constant on previous, before
XOR 4th back
AES Key Expansion
Key Expansion Rationale
• designed to resist known attacks
• design criteria included
• knowing part key insufficient to find many more
• invertible transformation
• fast on wide range of CPU’s
• use round constants to break symmetry
• diffuse key bits into round keys
• enough non-linearity to hinder analysis
• simplicity of description
Plain Text:
0123456789ab
cdeffedcba9876
543210
Key:
0f1571c947d9e
8590cb7add6af
7f6798
AES Example
Key Expansion
AES Example
Encryption
AES Example
Avalanche
AES Decryption
• AES decryption is not identical to encryption since steps done in
reverse
• but can define an equivalent inverse cipher with steps as for
encryption
• but using inverses of each step
• with a different key schedule
• works since result is unchanged when
• swap byte substitution & shift rows
• swap mix columns & add (tweaked) round key
AES Decryption
Implementation Aspects
• can efficiently implement on 8-bit CPU
• byte substitution works on bytes using a table of 256 entries
• shift rows is simple byte shift
• add round key works on byte XOR’s
• mix columns requires matrix multiply in GF(28) which works on byte values,
can be simplified to use table lookups & byte XOR’s
Implementation Aspects
can efficiently implement on 32-bit CPU
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
