Transcript A simple algebraic representation of Rijndael

A simple algebraic representation
of Rijndael
Niels Ferguson
Richard Schroeppel
Doug Whiting
1
I am biased
• I’m one of the designers of Twofish, an AES
finalist that lost to Rijndael in the AES
competition.
• I spent several month attacking Rijndael.
2
The finite field
8
GF(2 )
• It is a field: you can add, subtract, multiply,
and divide.
• There are 28 = 256 elements.
• Field addition is the XOR operation.
• Multiplication is similar to modular
multiplication, without any carries.
3
Squaring in
8
GF(2 )
We all know that
(a + b)2 = a2 + ab + ab + b2
but as addition in GF(28) is a XOR we get
(a + b)2 = a2 + b2
This is known as the Freshman’s Dream.
Squaring is a bit-linear operation!
4
The MixColumn operation
Matrix multiplication: each output byte is a
linear combination of input bytes.
b0 = 2a0 + 3a1 + a2 + a3
b1 = a0 + 2a1 + 3a2 + a3
b2 = a0 + a1 + 2a2 + 3a3
b3 = 3a0 + a1 + a2 + 2a3
5
S-box has three layers
• Inversion in the field GF(28).
• Bit-linear function (each output bit is the
sum of some input bits).
• Addition of a constant.
6
Bit-linear functions in
8
GF(2 )
• Any bit-linear function in GF(28) can be
written as
ax128+bx64+cx32+dx16+ex8+fx4+gx2+hx
• Squaring is bit-linear, so all polynomials of
this form are bit-linear.
• There are 264 polynomials of this form, and
264 bit-linear functions.
7
Rewriting the S-box
• The constant can be moved into the key
schedule.
• We can rewrite the S-box as
1
S ( x)   wd  
 x
d 0
7
2
d
7

d 0
wd
x
2d
8
Combined S-box and MixColumn
3
• MixColumn:
bi   mi ,e  ae
e0
• Combined:
3
7
bi   mi ,e 
e 0

e,d
d 0
wd
ae
2d
wi ,e ,d
( ae )
2d
9
One round
Can be written as:
( 2)
i, j
a
k
(1)
i, j

e1 , d1
wi ,e1 ,d1
(k
(0)
e1 ,e1  j
 pe1 ,e1  j )
2 d1
or
( 2)
i, j
a
C
K *
*
e1 , d1 ( K  p* )
10
Four rounds
(5)
i, j
a
K

e4 , d 4
C
K*  
e3 , d 3
C*
K* 

C*
*
C
e2 , d 2
K*   *
*
K

p
e1 , d1
*
11
Conclusions
• Rijndael depends on a new complexity
assumption:
You cannot solve equations of this form
efficiently in GF(28).
• We have no idea how hard this problem is.
12
Which block cipher to choose
• Rijndael/AES: fast, available, and the safe
choice (for your career).
• Serpent: built like a tank, but slow
• Twofish: most of the security of Serpent,
with most of the speed of Rijndael.
13