Biclique Cryptanalysis of the Full AES
Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger
Microsoft Research - KU Leuven - ENS

16 August 2011

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AESOr:
Why you might want to rename
AES-128 into AES-126
in a few minutes

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

Biclique?

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AESWhere?

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

BicliqueIn a cipher
plaintextciphertext

MITMkey

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

What for?

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

AES-128
4Best meet-in-the-middle
attack on AES-128

7Best key-recovery
attack on AES-128?

02

Bogdanov-Khovratovich-Rechberger468

10 rounds

Biclique Cryptanalysis of the Full AES

AES-128
4
Best meet-in-the-middle
attack on AES-128

7
Best key-recovery
attack on AES-128

8Bicliques for
8-round AES-128

2124.9biclique?
02

Bogdanov-Khovratovich-Rechberger

46810 rounds

Biclique Cryptanalysis of the Full AES

AES-128
4Best meet-in-the-middle
attack on AES-128

7Best key-recovery
attack on AES-128

8Bicliques for8-round AES-128

2124.9biclique2126.2

Bicliques
for the full AES-128

02

Bogdanov-Khovratovich-Rechberger

46810 rounds

Biclique Cryptanalysis of the Full AES

192?

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

Sure

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

AES-192

5Best meet-in-the-middle
attack on AES-192

8Best key-recovery
attack on AES-192

2189.7

Bicliques
for the full AES-192

02

Bogdanov-Khovratovich-Rechberger

4681012 rounds

Biclique Cryptanalysis of the Full AES

Methods?

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

AES-128
3-Round Biclique of Higher Dimension

SubBytes
ShiftRows
MixColumns

SubBytes
ShiftRows
MixColumns

SubBytes
ShiftRows
MixColumns

SubBytes
ShiftRows
MixColumns

key schedule

key schedule

SubBytes
ShiftRows
MixColumns

SubBytes
ShiftRows

key schedule

SubBytes
ShiftRows

SubBytesShiftRows
MixColumns

key schedule

key schedule

SubBytes
ShiftRows
MixColumns

SubBytes
ShiftRows
MixColumns

key schedule

key schedule

SubBytes
ShiftRows
MixColumns

key schedule

aSubBytes
ShiftRowsb0
Bogdanov-Khovratovich-Rechberger

0
Biclique Cryptanalysis of the Full AES

AES-128
Idea of the Speed-Up

Split the 2128 key space into groups of 216 keys
To test all 216 keys in a group:
Perform a base computation
Precompute 28 forward key modifications
Precompute 28 backward key modifications
For each key in 216 , combine one forward and one backward
computation for freeALL 216 keys in the group covered with only 29 computations!

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

Biclique Key Recovery for AES

roundscomputations data memory success prob.
AES-128 secret key recovery

10 (full)

2126.18

288

28

1

AES-192 secret key recovery
12 (full)

2189.74

280

28

1

AES-256 secret key recovery
14 (full)

2254.42

240

28

1

No related keys!

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES

Check the full paper at the project website
http://research.microsoft.com/en-us/projects/cryptanalysis/aes.aspx

Bogdanov-Khovratovich-Rechberger

Biclique Cryptanalysis of the Full AES