Advance Encryption

Standard
Topics
 Origin of AES

 Basic AES

 Inside Algorithm

 Final Notes
DES cracking

Part 1  Cryptography
Origins
 A replacement for DES was needed
 Key size is too small

 Can use Triple-DES – but slow, small block

 US NIST issued call for ciphers in 1997

 15 candidates accepted in Jun 98

 5 were shortlisted in Aug 99

AES Competition Requirements
 Private key symmetric block cipher

 128-bit data, 128/192/256-bit keys

 Stronger & faster than Triple-DES

 Provide full specification & design details

 Both C & Java implementations

AES Evaluation Criteria
 initial criteria:
 security – effort for practical cryptanalysis
 cost – in terms of computational efficiency
 algorithm & implementation characteristics

 final criteria
 general security
 ease of software & hardware implementation
 implementation attacks
 flexibility (in en/decrypt, keying, other factors)
AES Shortlist
 After testing and evaluation, shortlist in Aug-99
 MARS (IBM) - complex, fast, high security margin
 RC6 (USA) - v. simple, v. fast, low security margin
 Rijndael (Belgium) - clean, fast, good security
margin[selected as AES
 Serpent (Euro) - slow, clean, v. high security margin
 Twofish (USA) - complex, v. fast, high security margin

 Found contrast between algorithms with

 few complex rounds versus many simple rounds
 Refined versions of existing ciphers versus new
proposals

Rijndae: pronounce “Rain-Dahl”

The AES Cipher - Rijndael
 Rijndael was selected as the AES in Oct-2000
 Designed by Vincent Rijmen and Joan Daemen in
Belgium
 Issued as FIPS PUB 197 standard in Nov-2001

 An iterative rather than Feistel cipher-chia 2

V. Rijmen
nửa
 processes data as block of 4 columns of 4 bytes (128
bits)
 operates on entire data block in every round

 Rijndael design:
 simplicity
 has 128/192/256 bit keys, 128 bits data J. Daemen
 resistant against known attacks
 speed and code compactness on many CPUs
Topics
 Origin of AES

 Basic AES

 Inside Algorithm

 Final Notes
AES Conceptual Scheme

Plaintext (128 bits)

AES Key (128-256 bits)

Ciphertext (128 bits)

10
Multiple rounds
 Rounds are (almost) identical
 First and last round are a little different

11
High Level Description

No MixColumns
Overall Structure
128-bit values

 Data block viewed as 4-by-4 table of bytes

 Represented as 4 by 4 matrix of 8-bit bytes.
 Key is expanded to array of 32 bits words

1 byte

14
Data Unit
Unit Transformation
Changing Plaintext to State
Topics
 Origin of AES

 Basic AES

 Inside Algorithm

 Final Notes
Details of Each Round
SubBytes: Byte Substitution
 A simple substitution of each byte
 provide a confusion – làm cho relationship between Ciphertext
and Key become more complex

 Uses one S-box 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

Galois Field- GF(28)
Galois : pronounce “Gal-Wa”
SubBytes and InvSubBytes
SubBytes Operation
 The SubBytes operation involves 16 independent
byte-to-byte transformations. • Interpret the byte as two
hexadecimal digits xy
S1,1 = xy16 • SW implementation, use
row (x) and column (y) as
lookup pointer
x’y’16
SubBytes Table
 Implement by Table Lookup
InvSubBytes Table
Sample SubByte Transformation

 The SubBytes and InvSubBytes

transformations are inverses of each other.
ShiftRows

 Shifting, which permutes the bytes.

 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
 In the encryption, the transformation
is called ShiftRows
 In the decryption, the transformation
is called InvShiftRows and the shifting
is to the right
ShiftRows Scheme
ShiftRows and InvShiftRows
MixColumns
 ShiftRows and MixColumns provide diffusion
to the cipher
 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
MixClumns Scheme

The MixColumns transformation operates at the column level; it

transforms each column of the state to a new column.
MixColumn and InvMixColumn
AddRoundKey
 XOR state with 128-bits of the round key

 AddRoundKey proceeds one column at a time.

 adds a round key word with each state column
matrix
 the operation is matrix addition

 Inverse for decryption identical

 since XOR own inverse, with reversed keys

 Designed to be as simple as possible

AddRoundKey Scheme
AES Round
AES Key Scheduling
 takes 128-bits (16-bytes) key and expands
into array of 44 32-bit words
Key Expansion Scheme
Key Expansion submodule
 RotWord performs a one byte circular left shift
on a word For example:

RotWord[b0,b1,b2,b3] = [b1,b2,b3,b0]

 SubWord performs a byte substitution on each

byte of input word using the S-box

 SubWord(RotWord(temp)) is XORed with

RCon[j] – the round constant
Round Constant (RCon)
 RCON is a word in which the three rightmost bytes are zero
 It is different for each round and defined as:
RCon[j] = (RCon[j],0,0,0)
where RCon[1] =1 , RCon[j] = 2 * RCon[j-1]
 Multiplication is defined over GF(2^8) but can be implement
in Table Lookup
Key Expansion Example (1st Round)
• Example of expansion of a 128-bit cipher key
Cipher key = 2b7e151628aed2a6abf7158809cf4f3c
w0=2b7e1516 w1=28aed2a6 w2=abf71588 w3=09cf4f3c
Topics
 Origin of AES

 Basic AES

 Inside Algorithm

 Final Notes
AES Security
 AES was designed after DES.
 Most of the known attacks on DES were already
tested on AES.
 Brute-Force Attack
 AES is definitely more secure than DES due to the
larger-size key.
 Statistical Attacks
 Numerous tests have failed to do statistical analysis of
the ciphertext
 Differential and Linear Attacks
 There are no differential and linear attacks on AES as
yet.
Implementation Aspects
 The algorithms used in AES are so simple
that they can be easily implemented using
cheap processors and a minimum amount
of memory.

 Very efficient

 Implementation was a key factor in its

selection as the AES cipher

 AES animation:
 http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/
rijndael_ingles2004.swf
A Few Other Block Ciphers-
READING
Symmetric Key Cryptography
A Few Other Block Ciphers
 Briefly…
 IDEA
 Blowfish
 RC6
 More detailed…
 TEA

Part 1  Cryptography
IDEA
 Invented by James Massey
 One of the giants of modern crypto
 IDEA has 64-bit block, 128-bit key
 IDEA uses mixed-mode arithmetic
 Combine different math operations
 IDEA the first to use this approach
 Frequently used today

Part 1  Cryptography
Blowfish
 Blowfish encrypts 64-bit blocks
 Key is variable length, up to 448 bits
 Invented by Bruce Schneier
 Almost a Feistel cipher

Ri = Li1  Ki
Li = Ri1  F(Li1  Ki)
 The round function F uses 4 S-boxes
 Each S-box maps 8 bits to 32 bits
 Key-dependent S-boxes
 S-boxes determined by the key
Part 1  Cryptography
RC6
 Invented by Ron Rivest
 Variables
 Block size
 Key size
 Number of rounds
 An AES finalist
 Uses data dependent rotations
 Unusual for algorithm to depend on plaintext

Part 1  Cryptography
Time for TEA…

 Tiny Encryption Algorithm (TEA)

 64 bit block, 128 bit key
 Assumes 32-bit arithmetic
 Number of rounds is variable (32 is
considered secure)
 Uses “weak” round function, so large
number of rounds required

Part 1  Cryptography
TEA Encryption
Assuming 32 rounds:
(K[0], K[1], K[2], K[3]) = 128 bit key
(L,R) = plaintext (64-bit block)
delta = 0x9e3779b9
sum = 0
for i = 1 to 32
sum += delta
L += ((R<<4)+K[0])^(R+sum)^((R>>5)+K[1])
R += ((L<<4)+K[2])^(L+sum)^((L>>5)+K[3])
next i
ciphertext = (L,R)

Part 1  Cryptography
TEA Decryption
Assuming 32 rounds:
(K[0], K[1], K[2], K[3]) = 128 bit key
(L,R) = ciphertext (64-bit block)
delta = 0x9e3779b9
sum = delta << 5
for i = 1 to 32
R = ((L<<4)+K[2])^(L+sum)^((L>>5)+K[3])
L = ((R<<4)+K[0])^(R+sum)^((R>>5)+K[1])
sum = delta
next i
plaintext = (L,R)

Part 1  Cryptography
TEA Comments

 “Almost” a Feistel cipher

 Uses + and - instead of  (XOR)
 Simple, easy to implement, fast, low
memory requirement, etc.
 Possibly a “related key” attack
 eXtended TEA (XTEA) eliminates related
key attack (slightly more complex)
 Simplified TEA (STEA)  insecure version
used as an example for cryptanalysis

Part 1  Cryptography