IAIK Krypto Group
Rijndael: Een triomf van de wiskunde Vincent Rijmen KULAK, 23 februari 2006
Inhoud Vercijferen met een blokcijfer Data encryption & advanced data encryption Ontwerp van Rijndael 4 andere finalisten
Institute for Applied Information Processing and Communications (IAIK) - Krypto Group Faculty of Computer Science Graz University of Technology
.
Rijndael
2
1
IAIK Krypto Group
IAIK Krypto Group
De setting
Klassieke cryptografie
E
Rijndael
3
Rijndael
#!C&
#!C&
D
4
2
IAIK Krypto Group
IAIK Krypto Group
Principes
Eenvoudig substitutiecijfer
Kerckhoffs principe: Niets is geheim, behalve 1 parameter, de sleutel
Permutatie van 26 letters
Generatie, distributie en beheer van de sleutel: apart probleem
A
B
C
…
Z
Q
W
E
…
M
26! mogelijkheden (sleutels) Frequentie-analyse
© Wikipedia Rijndael
5
Rijndael
6
3
IAIK Krypto Group
IAIK Krypto Group
Geavanceerd substitutiecijfer
Blokcijfer
Permutatie van blok letters
Vermijd transport & stockage van enorme tabel
AAAA
AAAB
AAAC
…
ZZZZ
QAQZ
WIJT
ENTO
…
MIHB
Bereken de tabel: T[X] = f(X,sleutel)
“codeboek” Nog meer sleutels Blokken groot genoeg: frequentieanalyse onmogelijk (ondoenbaar)
Rijndael
Ontwerp `goede’ f: Veilig Snel
7
Rijndael
8
4
IAIK Krypto Group
IAIK Krypto Group
Data Encryption Standard (1977)
De DES rondetransformatie
1970: nood aan cryptografie voor commercieel gebruik 1973-1977: Ontwikkeling van een blokcijfer: DES Vercijfert blokken van 64 bit Sleutel van 56 bit Structuur: 16 iteraties van een rondetransformatie
Rijndael
9
Rijndael
10
5
IAIK Krypto Group
IAIK Krypto Group
Problemen met DES Geheime ontwerpcriteria NSA betrokkenheid Valluiken?
Korte sleutel Niet genoeg mogelijkheden
Toch een succes: de enige keuze Ook gebruikt voor authenticatie
Rijndael
11
Rijndael
12
6
IAIK Krypto Group
IAIK Krypto Group
Einde van DES
Advanced Encryption Standard
Ontworpen voor 1970 hardware Geen goed gebruik van moderne processors 1991, 1993: theoretische aanvallen + theoretisch ontwerp van een DES “cracker” 1998: bouw van een DES cracker (EFF)
1997: submissies Vereisten: Niet trager dan 3-DES Veiliger Geen royalties
Tijdelijke oplossing: 3-DES Augustus 1998: eerste AES conferentie
© EFF
Rijndael
13
Rijndael
14
7
IAIK Krypto Group
IAIK Krypto Group
Rijndael structuur
Uniforme rondetransformatie
10/12/14 iteraties van de rondetransformatie Uniforme rondetransformatie ≠ DES 4 stappen, elke stap heeft zijn eigen functie: SubBytes: niet-lineariteit ShiftRows: inter-kolom diffusie MixColumns: inter-byte diffusie binnen elke kolom AddRoundKey: inbrengen van sleutel
Rijndael
15
Rijndael
16
8
IAIK Krypto Group
IAIK Krypto Group
Stap 1: SubBytes
Stap 2: ShiftRows m g w b
S-box a0,0 a1,0 a2,0 a3,0
a0,1 a1,1 a2,1 a3,1
a0,2 a0,3 aa1,2 a1,3 i,j a2,2 a2,3 a3,2 a3,3
b0,0 b1,0 b2,0 b3,0
b0,1 b0,2 b1,1 b b1,2 i,j b2,1 b2,2 b3,1 b3,2
b0,3 b1,3 b2,3 b3,3
o i y d
p j z e
m h y e
n i z b
o j w c
p g x d
Rijen schuiven over 4 verschillende offsets Diffusie na meerdere ronden: Interaktie met MixColumns
Bytes gaan door een inverteerbare S-box. Altijd dezelfde S-box: Sterk niet-lineair: multiplicatieve inverse in GF(28) Kleine wijzigingen om algebraische beschrijving meer complex te maken Rijndael
n h x c
17
Rijndael
18
9
IAIK Krypto Group
IAIK Krypto Group
Stap 3: MixColumns a0,0 a1,0 a2,0 a3,0
a0,j
a0,1 a0,2 a1,1aa1,j 1,2 a2,1 a2,2 a a3,1 a2,j 3,2
a3,j
a0,3 a1,3 a2,3 a3,3
2 1 1 3
3 1 1 2 3 1 ⊗ 1 2 3 1 1 2
Stap 4: AddRoundKey a0,0 a0,1 a0,2 a0,3
b0,j b0,0 b1,0 b2,0 b3,0
b0,1 b1,1 b2,1 b3,1
a1,0 a1,1 a1,2 a1,3
b0,2 b0,3 b1,j b b 1,2 1,3 b b b2,2 2,j 2,3 b3,2 b3,3
a2,0 a2,1 a2,2 a2,3 a3,0 a3,1 a3,2 a3,3
b3,j
19
+
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
Introduceert sleutel “keep it simple”
Vermenigvuldig kolommen met matrix (in GF(28)) Sterke diffusie in elke kolom:
Rijndael
k0,0 k0,1 k0,2 k0,3
Rijndael
20
10
IAIK Krypto Group
IAIK Krypto Group
Ontwerp van een blokcijfer Waarschijnlijk veilig en traag: makkelijk Uitdaging: Snel op vele verschillende platformen Plausibele argumenten voor veiligheid
Rijndael
21
Rijndael
22
11
IAIK Krypto Group
IAIK Krypto Group
Waarom opsplitsen in componenten?
Belang van niet-lineariteit
Gewenst: output sterk niet-lineaire functie van alle input bits “Direct”: kost stijgt exponentieel ifv aantal inputs
Praktijk: deel van boodschap vaak a priori bekend Lineair cijfer: Lineaire vergelijkingen in sleutel
Neem:
“Sterk” niet-lineair
Zwak niet-lineaire functie, of Sterk niet-lineaire functies van minder bits + menging
Moeilijk te benaderen met lineaire functies
Itereer Uitgebreide literatuur beschikbaar over niet-lineaire functies
Rijndael
23
Rijndael
24
12
IAIK Krypto Group
IAIK Krypto Group
Belang van menging
SubBytes en AddRoundKey: geen menging
Blokcijfer Werken op de 16 bytes in parallel
Onvolledige menging: cijfer met kleinere blokken Slechte menging: goed benaderbaar door onvolledige menging Weinig literatuur beschikbaar over goede menging Rijndael
25
Rijndael
26
13
IAIK Krypto Group
IAIK Krypto Group
MixColumns versie 1
Op zoek naar een optimaal diffuziegetal output
input
0 1 1 1
1 1 1 0 1 1 1 0 1 1 1 0
a0,1 a1,1 a2,1
a0 , 2 a1, 2 a2 , 2
a3,1
a3, 2
a0 , 3 a1,3 a2 , 3 a3,3
gecombineerde vector
Lineaire code
1 0 ⊗ 0 0
0 0 0 a0 , 0
a0,1
a0 , 2
1 0 0 a1,0
a1,1
a1, 2
0 1 0 a2 , 0
a2,1
a2 , 2
0 0 1 a3, 0
a3,1
a3, 2
a0 , 3 a1,3 a2 , 3 a3,3
4 data symbolen 4 check symbolen
Diffuziegetal = 4 Rijndael
a0 , 0 a 1, 0 ⊗ a2 , 0 a3, 0
27
Rijndael
28
14
IAIK Krypto Group
IAIK Krypto Group
Eindige veld GF(28)
Optimaal diffuziegetal Diffuziegetal = minimale afstand van de lineaire code Optimale geval: afstand = #check symbolen + 1 =5
Lineaire code vereist eindig veld GF(28) past perfect by bytes Eigenlijk eenvoudiger dan werken met gehele getallen (in hardware)
Optimale MixColumns uit MDS-code
Optelling zonder overdracht Vermenigvuldiging vraagt minder poorten
Rijndael
29
Rijndael
30
15
IAIK Krypto Group
IAIK Krypto Group
Twofish
De 4 andere finalisten Twofish (Counterpane) MARS (IBM) RC6 (RSA security) Serpent (Cambridge – Technion - Bergen)
Rijndael
Rondetransformatie als DES Eclectisch: “combineert de beste elementen van vele andere ontwerpen”. Complex Op vele platformen snel
31
Rijndael
32
16
IAIK Krypto Group
IAIK Krypto Group
RC6 Rondetransformatie als DES Heel eenvoudig in alle programmeertalen Geen vaste tabellen Traag op chipkaarten en parallelle computers
Mee ontworpen door Rivest (RSA)
Rijndael
33
Rijndael
34
17
IAIK Krypto Group
IAIK Krypto Group
MARS
RC6 in minder dan 10 lijnen
Rondetransformatie tussen DES en uniform in 4 verschillende rondetransformaties Gebruikt 32-bit vermenigvuldiging
[A B C D] = boodschap B = B + S[0]; D = D + S[1] Voor i = 1 tot 20 doe
• Duur in hardware
Complex (fouten in specificatie)
T = Rot5(B*(2B+1)) U = Rot5(D*(2D+1)) A = RotU(A © T) + S[2i] B = RotT(C © U) + S[2i+1] [A B C D] = [B C D A]
Had IBM en mede-ontwerpers van DES achter zich
A = A + S[42]; C = C + S[43]
Rijndael
35
Rijndael
36
18
IAIK Krypto Group
IAIK Krypto Group
Rijndael tegen de rest
Serpent
Alle 5 de finalisten zijn veilig
Uniforme rondetransformatie Geen tabellen Super-traag
Rijndael heeft op veel platformen een hogere performantie Op ultramoderne parallelle processoren Op heel eenvoudige processoren
Ontwerpers: 3 befaamde cryptografen
Rijndael heeft wiskundige elegantie Eenvoudige beschrijving Link naar eindige velden, lineaire codes
Controverse: te mooi om waar te zijn? Rijndael
37
Rijndael
38
19
