AES Advanced Encryption Standard
Der Rijndael Algorithmus
Vortrag im Fach Kryptologie
Prof. Dr. Hoever
1
Vortragende: Fegler, Alexander & Hellmann, Jelle
Inhalt
-
1. Entstehung
-
-
2. Arbeitsweise
-
2
1.1 Auswahl des Nachfolgers
1.2 Anforderungen
1.3 Auswahlgründe
2.1 Mathematische Grundlagen
2.2 Überblick Algorithmus
2.3 State, Chipher Key number of rounds
2.4 Round transformation (was pro Runde gemacht wird)
2.4.1 Byte Sub
2.4.2 Shift Row
2.4.3 Mix Columm
2.4.4 Round Key Addition
2.4.5 Key Schedule (Key Expansion & Round Key Selection)
3. Anwendungsgebiete
4. Sicherheit
5. Fazit/Ausblick
1. Entstehung
Da DES immer unsicherer wurde, aufgrund seiner relativ kurzen
Schlüssellänge von 56 Bit und weil 3DES eine schlechte Performance
hatte, wurde 1997 in weiser Voraussicht vom NIST (National Institut for
Standardisation and Technology) eine Initiative bzw. Wettbewerb ins Leben
gerufen um den Nachfolger des DES zu suchen.
Kurz darauf wurden in einem Workshop werden die genauen Anforderungen
an den Algorithmus festgelegt.
Nach knapp 4 Jahren die der Auswahlprozess gebraucht hatte, stand das
Ergebnis fest, der Sieger des AES Wettbewerbes war der Rijndael Algorithmus.
Er wurde von den Belgiern Vicent Rijmen und Joan Daemen entwickelt.
3
1.1 Historie
März 2. AES Konferenz
Diskussion der bisherigen
Resultate
2. Januar ’97 Aufruf zur Initiative
15. April Ende der
Begutachtung der
Kandidaten
15. April AES-Workshops
genaue Anforderungen
1997
Februar Ende öffentliche
Diskussion zum Standard
1998
1999
November FIPS Standard
2000
2001
November FIPS- Standard als
Manusskript
2. Oktober Sieger ist Rinjdael
20. August 1. AES Konferenz
15 Algorithmen eingegangen
15. Mai Ende der
öffentlichen Diskussion
13./14. April 3. AESKonferenz Analyse der 5
Endkandidaten
4
1.2 Anforderungen
Anforderungen die vom NIST gestellt wurden waren:
Technische:
-
AES muss symmetrischer Algorithmus sein -> Blockalgorithmus
AES muss mindestens 128 Bit lange Blöcke verwenden und Schlüssel von 128, 192
und 256 Bit verwenden können
AES soll gleichermaßen leicht in Hard- und Software implementierbar sein
AES soll in Hard- und Software eine überdurchschnittliche Performance haben
AES soll allen bekannten Methoden der Kryptanalyse widerstehen können,
insbesondere POWER- und TIMING- Attacken
Speziell für den Einsatz in Smartcards sollen geringe Ressourcen erforderlich sein(
kurze Codelänge, niedriger Speicherbedarf)
Weitere:
-
5
Der Algorithmus muss frei von patentrechtlichen Ansprüchen sein und darf von
jedermann unentgeltlich genutzt werden
Umfangreiche Dokumentation
1.3 Auswahlgründe
NIST: „When considered togehter, Rijndael‘s combination of
security, performance, efficiency, implementability and
flexibility make it an appropriate selection for the AES“
Also aufgrund seiner Einfachheit und seiner exzellenten Performance
- Eingangstext jede runde deterministischen Transformationen
unterworfen
- Ergebnisse werden XOR mit den Rundenschlüssel verrechnet
Sicherheit kommt von der Konstruktion des Transformationen (S-Box)
und der Durchführung mehrerer Runden.
Aber gerade wegen seiner algebraischen Struktur wurden/werden
Schwächen vermutet
6
2.1 Mathematische Grundlagen
Ist a  a7 a6 a5 a4 a3 a2 a1a0 ein Byte, so wird die dazugehörige Polynomdarstellung
betrachtet
f ( x)  a7 x 7  a6 x 6  a5 x 5  a4 x 4  a3 x 3  a2 x 2  a1 x  a0
Für jedes Byte ist ein Polynom vom Grad ≤ 7, so dass man definiert
GF(256)  { f  Z 2 [ x] : grad( f )  7}
Der Addition zweier Polynome f und g in GF(256) entspricht die XOR Verknüpfung (
der dazu gehörigen Bytes.
Beispiel:
f ( x)  x 6  x 4  x 2  x  1
g ( x)  x 7  x  1
( x 6  x 4  x 2  x  1)  ( x 7  x  1)  x 7  x 6  x 4  x 2
01010111 10000011 11010100
57  83  D4
7
)
2.1 Mathematische Grundlagen
Um in GF(256) auch multiplizieren zu können, muss der Grad des Produktes
zweier Polynome wieder reduziert werden. Dies geschieht mit der Modulo
Rechung bzgl. eines Polynoms vom Grad 8 (=7+1).Daher wird für den AES
Algorithmus ein festes irrreduzibles Polynom gewählt und zwar
m( x)  x 8  x 4  x 3  x  1
Beispiel:
f ( x)  x 6  x 4  x 2  x  1
g ( x)  x 7  x  1
f ( x)  g ( x)  x13  x11  x 9  x 8  x 6  x 5  x 4  x 3  1
f ( x)  g ( x) mod(m( x))  x 7  x 6  1
8
2.1 Mathematische Grundlagen
Neutrale Element bzgl. ● ist das Byte 01
Das multiplikativ Inverse, kann mittels der erweiterten Euklid gefunden werden
a(x) und c(x) so berechen
b( x)a( x)  m( x)c( x)  1
a( x)  b( x) modm( x)  1
b 1 ( x)  a( x) modm( x)
Es gilt auch das Kommutativ- und das Distributivgesetz
a( x)  (b( x)  c( x))  a( x)  b( x)  a( x)  c( x)
Es folgt , das die 256 Bytes werte mit dem XOR ( ) als Addition und der obigen
Multiplikation ● den endlichen Körper GF(256) bilden.
In der Algebra ist ein endlicher Körper oder Galoisfeld (benannt nach dem
Mathematiker Evariste Galois) ein Körper mit nur endlich vielen Elementen.
9
2.2 Algorithmus Übersicht
Benutzerschlüssel
Klartext
Verschlüsselung
verschlüsselter
Text
10
Eingabe eines Klartextes und eines
Schlüssels durch den Benutzer
Rundenbasierte Hintereinanderausführung von verschiedenen
Transformationsschritten
Ausgabe des verschlüsselten Textes
2.3 Number of Rounds, State & Key
Rundenanzahl ist abhängig von verwendeter Schlüssellänge k
und verwendeter Blockgöße b
Zustand
b=128
b=192
b=256
k=128
10
12
14
k=192
12
12
14
k=256
14
14
14
Schlüssel
k0,0
k0,1
k0,2
K0,3
k0,4
k0,5
a1,3
k1,0
k1,1
k1,2
k1,3
k1,4
k1,5
a2,2
a2,3
k2,0
k2,1
k2,2
k2,3
k2,4
k2,5
a3,2
a3,3
k3,0
k3,1
k3,2
k3,3
k3,4
k3,5
a0,0
a0,1
a0,2
a0,3
a1,0
a1,1
a1,2
a2,0
a2,1
a3,0
a3,1
4 Byte=32 Bit
11
r
2.4 Verschlüsselungsprozess
Klartext
Schlüssel
Initialisierungsrunde
AddRoundKey
Runde 1 bis ( r – 1 )
ByteSub
Anzahl der Runden
ist abhängig von der
Block- und
Schlüssellänge
ShiftRow
MixColumn
AddRoundKey
Rundenschlüssel
Runde r
ByteSub
ShiftRow
AddRoundKey
12 verschlüsselter Text
2.4.1 Verschlüsselungsprozess
ByteSub
• monoalphabetische Verschlüsselung mit der
Substitutionsbox
• Bytes im Block durch Äquivalente in der S-Box ersetzen
• S-Box meist als Array implementiert
• Transformation ist deterministisch
• Lediglich zur Vermischung der Bytes und Schutz gegen
– differentielle und lineare Kryptanalyse
– Interpolationsattacken
13
ByteSub
2.4.1 Verschlüsselungsprozess
State vor
ByteSub:
19 a0 9a e9
d4 e0 b8 1e
3d f4
27 bf
c6 f8
S-Box
e3 e2 8d 48
11
be 2b 2a 08
S-Box:
14
Beispiel
State nach
ByteSub:
b4 41
98 5d 52
ae f1
e5 30
0
0
63
1
7c
2
77
3
7b
4
f2
5
6b
6
6f
7
c5
8
30
9
01
a
67
b
2b
c
fe
d
d7
e
ab
f
76
1
ca
82
c9
7d
fa
59
47
f0
ad
d4
a2
af
9c
a4
72
c0
2
b7
fd
93
26
36
3f
f7
cc
34
a5
e5
f1
71
d8
31
15
3
04
c7
23
c3
18
96
05
9a
07
12
80
e2
eb
27
b2
75
4
09
83
2c
1a
1b
6e
5a
a0
52
3b
d6
b3
29
e3
2f
84
5
53
d1
00
ed
20
fc
b1
5b
6a
cb
be
39
4a
4c
58
cf
6
d0
ef
aa
fb
43
4d
33
85
45
f9
02
7f
50
3c
9f
a8
7
51
a3
40
8f
92
9d
38
f5
bc
b6
da
21
10
ff
f3
d2
8
cd
0c
13
ec
5f
97
44
17
c4
a7
7e
3d
64
5d
19
73
9
60
81
4f
dc
22
2a
90
88
46
ee
b8
14
de
5e
0b
db
a
e0
32
3a
0a
49
06
24
5c
c2
d3
ac
62
91
95
e4
79
b
e7
c8
37
6d
8d
d5
4e
a9
6c
56
f4
ea
65
7a
ae
08
c
ba
78
25
2e
1c
a6
b4
c6
e8
dd
74
1f
4b
bd
8b
8a
d
70
3e
b5
66
48
03
f6
0e
61
35
57
b9
86
c1
1d
9e
e
e1
f8
98
11
69
d9
8e
94
9b
1e
87
e9
ce
55
28
df
f
8c
a1
89
0d
bf
e6
42
68
41
99
2d
0f
b0
54
bb
16
2.4.2 Verschlüsselungsprozess
ShiftRow
• Zeilen des State byteweise zyklisch nach links
rotieren
• Anzahl der Verschiebungen ist zeilen- und
blocklängenabhängig
b=128 b=192 b=256
b=Blocklänge
Zeile 0
0
0
0
Zeile 1
1
1
1
Zeile 2
2
2
2
Zeile 3
3
3
4
• Transformation ist deterministisch
15
ShiftRow
2.4.2 Verschlüsselungsprozess
16
Beispiel
d4 e0 b8 1e
d4 e0 b8 1e
27
bf
bf
b4 41
b4 41 27
11 98 5d 52
5d 52 11 98
ae
30 ae
f1
e5 30
f1
e5
2.4.3 Verschlüsselungsprozess
MixColumn
• Spalten vermischen
– Jede Zelle einer Spalte wird mit einer Konstanten multipliziert.
Konstantes Polynom:
c(x) = 03hx3 + 01hx2 + 01hx + 02h
– Die Ergebnisse werden XOR verknüpft
• Vorgehensweise beruht auf Transformation auf
Galoisfeldern
• Transformation ist deterministisch
17
2.4.3 Verschlüsselungsprozess
d4 e0 b8 1e
Beispiel
Beispielrechnung für das erste Byte:
bf b4 41 27
11010100 * 00000010 = 10110011
(d4 * 02 = b3)
5d 52 11 98
10111111 * 00000011 = 11011010
(bf * 03 = da)
30 ae f1 e5
04 e0 48 28
66 cb f8 06
81 19 d3 26
e5 9a 7a 4c
18
MixColumn
01101001
(b3 XOR da = 69)
01011101 * 00000001 = 01011101
(5d * 01 = 5d)
00110100
(69 XOR 5d = 34)
00110000 * 00000001 = 00110000
(30 * 01 = 30)
00000100
(34 XOR 30 = 04)
2.4.4 Verschlüsselungsprozess
AddRoundKey
• KeyAddition in der Vorrunde und am Ende
jeder weiteren Runde
• Rundenschlüssel bitweise XOR
verknüpfen mit dem State
• Einzige Funktion, die den Algorithmus vom
Schlüssel abhängig macht
19
2.4.4 Verschlüsselungsprozess
State
AddRoundKey
Round key
Beispiel
Neues State
04 e0 48 28
a0 88 23 2a
a4 68 6b 02
66 cb f8 06
fa 54 a3 6c
9c 9f 5b 6a
81 19 d3 26
fe 2c 39 76
7f 35 ea 50
e5 9a 7a 4c
17 b1 39 05
f2 2b 43 49
Beispielrechnung für die erste Spalte:
20
00000100 (04)
01100110 (66)
10000001 (81)
11100101 (e5)
10100000 (a0)
11111010 (fa)
11111110 (fe)
00010111 (17)
10100100 (a4)
10011100 (9c)
01111111 (7f)
11110010 (f2)
Schlüsselgenerierung 1
• Schlüssel aufteilen in r + 1 Rundenschlüssel
• Benutzerschlüssel expandieren auf die Länge
b*(r+1)
• Der erste Rundenschlüssel ist identisch mit dem
Benutzerschlüssel
• Berechnung weiterer Rundenschlüssel nach
festem Schema…
21
Schlüsselgenerierung 2
• Für das Schema benötigte Elemente:
• RotWord():
– verschiebt die 4 Bytes eines Wortes zyklisch um eine Position
nach links, d.h. RotWord([a0,a1,a2,a3]) = [ a1,a2,a3,a0]
• ByteSub():
– S-Box auf jedes Byte eines Wortes anwenden (s.o.)
• Rcon-Tabelle:
– Rcon[i] = [xi-1,0,0,0], wobei 0 das Nullbyte und xi-1 die (i-1)-te
Potenz von x=(02)hex bzgl. der Multiplikation ● in GF (28)
bezeichnet
22
Schlüsselgenerierung 3
W[0] W[1] W[2] W[3] W[4] W[5] W[6] W[7] W[8] …
RotWord
RotWord
ByteSub
ByteSub
Rcon[1]
Rcon:
23
Rcon[2]
01
02
04
08
10
20
40
80
1b
36
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
Entschlüsselung
• Zunächst AddRoundKey(State, Roundkey)
• Dann die einzelnen Runden
– InvByteSub(State)
– InvShiftRow(State)
– InvMixColumn(State)
– AddRoundKey(State, InvMixColumn(Roundkey))
• Letzte Runde ohne InvMixColumn und mit dem
gewöhnlichen AddRoundKey(State, Roundkey)
24
3. Anwendungsgebiete
Verschlüsselungsstandard 802.11i für Wireless LAN & seinem Wi-FiÄquivalent WPA2 außerdem noch SSH und IPsec.
Weiterhin wird der Algorithmus zur Verschlüsselung diverser
komprimierter Dateiarchive verwendet.
Tools die AES verwenden:
PGP (gnuPgp), Steganos Safe, Winzip 9.0
SSL 3.0 (RSA + AES), Skype
Linux:
loop-aes von Jari Ruusu, aespipe
25
4. Sicherheit
Bruteforce & theoretische Folgen
(AES mit 256 Bit Schlüssel)
Speicheraufwand : für alle 2 256 Schlüssel
Wenn es möglich wäre pro Atom 1 Schlüssel zu speichern
Hätte der Speicher eine Masse von 1046 g das entspricht 1014 Sternenmassen
24
Bei 128 Bit Schlüssel nur noch ca. 300 t Speichermasse ca.10
TByte
Wenn man jetzt 1 Mrd. Computer hat, wovon jeder pro Sekunde 1 Mrd. Keys
testet, so bräuchte man immer noch im Durchschnitt 5 Billionen Jahre um an
den Schlüssel zu gelangen.
26
4. Sicherheit Stärken
Einfluss der Schlüssel
Verknüpfung des Rundenschlüssel vor der ersten Runde und als letzter schritt
innerhalb einer Runde
-> Jedes Bit ist vom Schlüssel abhängig
Nichtlineare Schicht
Die S-Box ist eine stark nichtlineare Operation
Die Konstruktion der S-Box sorgt für nahezu idealen Schutz vor der linearen
und differentiellen Kryptanalyse
Lineare Schicht
Die ShiftRow and MixColumn sorgen für eine optimale Durchmischung der Bits
eines Blockes.
27
4. Sicherheit/Angriffe (akademische Erfolge) 1
• 2001 als geschlossene Formel mit 1 Billionen Summanden
(Niels Ferguson, Richard Schroeppel, Doug Whiting)
niemand weiß, ob daraus jemals ein sinnvoller Angriff auf AES
konstruiert werden kann
• 2002 algebraische Besonderheiten (große Systeme
quadratischen Gleichungen) (Eli Biham)
128-Bit AES: GLS 8000 Gleichungen mit 1600 Variablen
• 2002 aus XL Verfahren -> XSL Verfahren (Josef Pieprzyk,
Nicolas Courtouis) eXtended Sparse Linearization
• 2002 AES Spezialfall von BES (Big Encryption System) (Sean
Murphy, Matt Robshaw)
28
4. Sicherheit/Angriffe (akademische Erfolge) 2
Gleichungssysteme mit folgenden Eigenschaften:
- stark überbestimmt (mehr Gleichungen als Variable)
- Schwach besetzt( größte Teil der Koeffizienten=0)
- Besonders reguläre Struktur
Besonderheiten:
- Coutouis & Pieprzyk XSL Methode könnte AES in 2 230 Schritten knacken
-
Angriff nicht auf Statistik sondern Algebra
-
Sicherheit von Produktalgorithmen nicht mehr exponentiell mit Rundenzahl
steigend
Sean Murphy and Matt Robwerts , AES Spezialfall von BES besonders runde
Struktur -> Rechenaufwand könnte sich dann auf 2100 reduzieren.
29
4. Sicherheit
Theoretische Angriffe haben aus 2 Gründen keine praktische Bedeutung
100
1) Komplexität der Angriffe bei 2
Rechenschritten
2) Angriffe sind umstritten und noch nicht implementiert
“2^100 Rechenschritte sind eine utopisch große Zahl. Ein aus GHz-PentiumProzessoren aufgebauter Rechencluster, der die Arbeit binnen eines Jahres schaffen
Sollte hätte einen Stromverbrauch von vielen Millionen Gigawatt, was viele
Größenordnungen über der Weltenergieproduktion liegt.“ [ct02/21/038]
Außerdem tauchen in den harten mathematischen Arbeiten immer wieder
Formulierungen wie „könnte“ und „vermutlich“ auf .
Trotzdem ist durch diese Veröffentlichungen das makellose Image von AES
ein wenig angekratzt.
30
5. Fazit/Ausblick
•
•
•
•
•
Hardwarenahe( d.h. Einfach zu implementieren)
Optimiertes C-Programm besteht aus nur ~ 500 Zeilen Code
Einfaches Design
Ohne Patentansprüche
Bis heute kein praktikabler Angriff gefunden
• Aber wahrscheinlich nicht mehr für die nächsten 20 Jahre sicher
• Wenn sich der Rechenaufwand innerhalb eines Jahres um 2130
„reduziert“ warum dann nicht noch Faktor 2 20 oder 2 40 drauflegen,
dann wäre erster praktikabler Angriff denkbar
• Aber noch bestimmt 10 Jahre sicher, weil nicht ohne beträchtlichen
Aufwand knackbar
31
Literatur
•
•
•
•
•
•
•
•
•
•
•
32
iX10/2001, iX12/2002
ct 11/05 ,ct 7/05, ct 17/03
http://www.schneier.com/paper-rijndael.html
http://www.cryptosystem.net/aes/
http://www.chscene.ch/ccc/ds/66/008_aes.html
http://csrc.nist.gov/CryptoToolkit/aes/
http://www.wikipedia.de
http://www.itl.nist.gov/fipspubs/ FIPS 197 Paper
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael-ammended.pdf
http://www.realtec.de/privat/arbeiten.shtml

AES