Rijndael
Joan Daemen
Proton World
Belgium
Vincent Rijmen
COSIC
Belgium
Monday, October 23, 2000 NISSC 2000 2
Vincent meets Joan
l Where: K.U.Leuven, research group COSIC
l When: Summer `93
l Why: Evaluation of propriety cipher
l What: successful cryptanalysis (under NDA :-(
Monday, October 23, 2000 NISSC 2000 3
The Mother of Rijndael: Square
l Need for a 128-bit block cipher with 128-bit keys
l 56-bit DES key: exhaustive key search feasible
l 64-bit DES block (and Triple-DES): MAC weaknesses
l Summer-Fall `96: Design
l symmetrical parallel structure
l byte-oriented
l no arithmetic operations
l Spring `97: Publication
l Fast Software Encryption Workshop in Haifa, Israel
Monday, October 23, 2000 NISSC 2000 4
Our AES Proposal: Rijndael
l Spring `97: early draft of AES call for proposals:
l key and block lengths 128, 196 and 256 bits
l we started to work on a Square variant satisfying this
l Summer `97: Official AES call
l requirement of 192 and 256 bit block lengths removed
l "would be infeasible to realize"
l June `98: AES submission deadline
l We baptized our design Rijndael (Rijmen & Daemen)
and submitted it to NIST
Monday, October 23, 2000 NISSC 2000 5
AES Selection Process
l August 98': AES 1 in Ventura (CA)
l 15 proposals were presented
l Square had made school
l Rijndael: son of Square
l Crypton (Korea) has the Square structure
l Twofish (Counterpane) uses Square features
l August `99: Announcement of the five finalists
l October 2000: Rijndael announced as AES
Monday, October 23, 2000 NISSC 2000 6
What makes Rijndael stand out?
l The symmetric and parallel structure
l gives implementers a lot of flexibility
l has not allowed effective cryptanalytic attacks
l Well adapted to modern processors
l Pentium
l RISC and parallel processors
l Suited for Smart cards
l Flexible in dedicated hardware
 Let's have a look at what's inside!
Monday, October 23, 2000 NISSC 2000 7
Rijndael: what is inside?
l Key and State bytes arranged in rectangular arrays
k0,0
k1,0
k2,0
k3,0
k0,1
k1,1
k2,1
k3,1
k0,2
k1,2
k2,2
k3,2
k0,3
k1,3
k2,3
k3,3
k0,4
k1,4
k2,4
k3,4
k0,5
k1,5
k2,5
k3,5
k0,6
k1,6
k2,6
k3,6
k0,7
k1,7
k2,7
k3,7
a0,0
a1,0
a2,0
a3,0
a0,1
a1,1
a2,1
a3,1
a0,2
a1,2
a2,2
a3,2
a0,3
a1,3
a2,3
a3,3
a0,4
a1,4
a2,4
a3,4
a0,5
a1,5
a2,5
a3,5
a0,6
a1,6
a2,6
a3,6
a0,7
a1,7
a2,7
a3,7
Variable Key size:
16, 24 or 32 bytes
Variable Block size:
16, 24 or 32 bytes
Monday, October 23, 2000 NISSC 2000 8
Rijndael: Iterated Block Cipher
l 10/12/14 times applying the same round function
l Round function: uniform and parallel, composed of
4 steps
l Each step has its own particular function:
l ByteSub: nonlinearity
l ShiftRow: inter-column diffusion
l MixColumn: inter-byte diffusion within columns
l Round key addition
Monday, October 23, 2000 NISSC 2000 9
Round step 1: ByteSub
l Bytes are transformed by applying invertible S-box.
l One single S-box for the complete cipher
l High non-linearity
a0,0 a0,1 a0,2 a0,3
a1,0 a1,1 a1,2 a1,3
a2,0 a2,1 a2,2 a2,3
a3,0 a3,1 a3,2 a3,3
b0,0 b0,1 b0,2 b0,3
b1,0 b1,1 b1,2 b1,3
b2,0 b2,1 b2,2 b2,3
b3,0 b3,1 b3,2 b3,3
ai,j bi,j
S-boxS-box
Monday, October 23, 2000 NISSC 2000 10
Round step 2: MixColumn
l Bytes in columns are linearly combined
l High intra-column diffusion:
l based on theory of error-correcting codes
a0,0 a0,1 a0,2 a0,3
a1,0 a1,1 a1,2 a1,3
a2,0 a2,1 a2,2 a2,3
a3,0 a3,1 a3,2 a3,3
b0,0 b0,1 b0,2 b0,3
b1,0 b1,1 b1,2 b1,3
b2,0 b2,1 b2,2 b2,3
b3,0 b3,1 b3,2 b3,3
a1,j
a0,j
a2,j
a3,j
b1,j
b0,j
b2,j
b3,j













2 3 1 1
1 2 3 1
1 1 2 3
3 1 1 2
Monday, October 23, 2000 NISSC 2000 11
Round step 3: ShiftRow
l Rows are shifted over 4 different offsets
l High diffusion over multiple rounds:
l Interaction with MixColumn
m n o p
g h i j
w x y z
b c d e
m n o p
j g h i
y z w x
c d e b
Monday, October 23, 2000 NISSC 2000 12
Round step 4: Key addition
l Makes round function key-dependent
l Computation of round keys: "keep it simple"
l small number of operations
l small amount of memory
a0,0 a0,1 a0,2 a0,3
a1,0 a1,1 a1,2 a1,3
a2,0 a2,1 a2,2 a2,3
a3,0 a3,1 a3,2 a3,3
k0,0 k0,1 k0,2 k0,3
k1,0 k1,1 k1,2 k1,3
k2,0 k2,1 k2,2 k2,3
k3,0 k3,1 k3,2 k3,3
b0,0 b0,1 b0,2 b0,3
b1,0 b1,1 b1,2 b1,3
b2,0 b2,1 b2,2 b2,3
b3,0 b3,1 b3,2 b3,3
=+
Monday, October 23, 2000 NISSC 2000 13
Rijndael on Modern Processors
Round function: just 16 table-lookups and EXORS
a0,0 a0,1 a0,2 a0,3
a1,0 a1,1 a1,2 a1,3
a2,0 a2,1 a2,2 a2,3
a3,0 a3,1 a3,2 a3,3
b0 b1 b2 b3
T1T1
x3,2
T2T2
T3T3
T4T4
x2,2 x1,2 x0,2+ +++k2 = b2
Monday, October 23, 2000 NISSC 2000 14
Rijndael in Hardware
Monday, October 23, 2000 NISSC 2000 15
Future of AES/Rijndael
l AES
l US Government Administration
l IPSEC
l commercial file encryption products
l Banking (DIGIPASS, ...)
l ...
l Rijndael
l UMTS
l Windows
l ...
Monday, October 23, 2000 NISSC 2000 16
We like to thank
l NIST: for the open way in which the AES process
was conducted
l Rijndael Programmers: for showing that it can be
efficiently implemented
l Antoon Bosselaers, Paulo Barretto, Cryptix, Brian
Gladman, Geoffrey Keating, Helger Lipmaa, Kazumaro
Aoki, Mitsuru Matsui, a.m.o.
l Anyone who motivated us by expressing their
interest in our work