Skript - Arbeitsgruppe Kryptographie und Sicherheit

Transcrição

Symmetrische Verschlüsselungsverfahren
Karlsruher Institut für Technologie, SS 2014
Daniel Kraschewski und Willi Geiselmann
Skript-Ausarbeitung: Jonas Böhler
Grundlage: Datensicherheitstechnik/SCC2-Skript
16. April 2014
Inhaltsverzeichnis
1 Einführung
1.1 Analytische Angriffe gegen Kryptosysteme . . . . . . . . . . . . . . . . . .
2 Historische Kryptoverfahren
2.1 Substitution . . . . . . . . . . . . .
2.1.1 Caesar-Chiffre . . . . . . .
2.1.2 Vigenère-Chiffre . . . . . .
2.2 Permutation . . . . . . . . . . . . .
2.3 Rotorenchiffren . . . . . . . . . . .
2.3.1 Die Hagelin-Maschine C-34
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
6
6
6
7
9
10
10
3 Einführung zu Blockchiffren & Konstruktionen
12
3.1 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 DES (Data Encryption Standard) . . . . . . . . . . . . . . . . . . . . . . . 13
4 Meet-in-the-Middle, Slide-Attack & Related-Key-Attack
4.1 Meet-in-the-Middle gegen 2DES . . . . . . . . . . . . .
4.2 Advanced Meet-in-the-Middle gegen 2Key-3DES . . .
4.2.1 Eine Variante per Known-Plaintext-Attack . .
4.3 Slide-Attack . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Advanced Slide-Attack gegen DES-X . . . . . . . . . .
4.5 Related-Key-Attack am Beispiel LOKI89 . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19
19
20
22
23
25
26
5 Lineare Kryptoanalyse
30
5.1 FEAL-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 DES: Lineare Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6 Differentielle Kryptoanalyse
37
6.1 DES: Differentielle Kryptoanalyse . . . . . . . . . . . . . . . . . . . . . . . 37
6.1.1 Angriff gegen einen 2n-Runden-DES . . . . . . . . . . . . . . . . . 40
6.2 Skipjack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7 AES (Advanced Encryption Standard)
46
7.1 Aufbau und Funktionsweise . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.2 Schwächen und beste bekannte Angriffe . . . . . . . . . . . . . . . . . . . 49
2
8 Betriebsmodi für Blockchiffren
8.1 ECB: Electronic Codebook Mode .
8.2 CBC: Cipher Block Chaining Mode
8.3 CFB: Cipher Feedback Mode . . .
8.4 OFB: Output Feedback Mode . . .
8.5 CTR: Counter Mode . . . . . . . .
8.6 Probleme bei schwachen Verfahren
8.7 Vergleich . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
50
50
51
52
54
55
56
56
9 Formale Sicherheitsbegriffe
58
9.1 Beziehungen zwischen den Begriffen . . . . . . . . . . . . . . . . . . . . . 60
10 Hashfunktionen
10.1 Definition und Eigenschaften . . . . . . .
10.2 Merkle-Damgard- & Feistel-Konstruktion
10.3 Äquivalenz von Krypto-Primitiven . . . .
10.4 Aufbau von SHA-1 . . . . . . . . . . . . .
10.5 Angriffsansätze gegen Hashfunktionen . .
10.5.1 Praktische Angriffe aus sinnlosen“
”
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Kollisionen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
62
62
63
64
67
69
70
11 Nachrichten-Authentifikation
72
11.1 Message Authentication Codes . . . . . . . . . . . . . . . . . . . . . . . . 72
11.2 Abstreitbare Authentifikation . . . . . . . . . . . . . . . . . . . . . . . . . 73
3
1 Einführung
Die Grundlage für dieses Skript bildet das Vorlesungsskript [Gei09]. Sofern nicht weiter
angegeben, werden Verschlüsselungsfunktionen in Abbildungen bzw. im Text mit E für
Encryption und Entschlüsselungsfunktionen mit D für Decryption bezeichnet. Darüber
hinaus werden Klartexte als m für Message, Geheimtexte mit c für Code und Schlüssel
mit k für Key bezeichnet.
1.1 Analytische Angriffe gegen Kryptosysteme
Bei der Kryptoanalyse wird davon ausgegangen, dass der Gegner ungehinderten Zugang zum ungesicherten Übertragungssystem hat (also beliebig viel Chiffretexte empfangen kann). Ferner nimmt man an, dass das Kryptoverfahren bekannt, der Schlüssel
aber geheim ist. Die Sicherheit des Verfahrens beruht allein auf der Geheimhaltung des
Schlüssels und nicht den Details des Kryptoverfahrens; dies ist als Kerckhoffs’ Prinzip
bekannt.
Die nachfolgende Auflistung der Angriffsarten ist aufsteigend nach der Stärke des Angriffs geordnet:
Ciphertext-Only Attack Es stehen nur die abgefangenen Chiffretexte zur Verfügung.
Der Angreifer hat also Zugriff auf den unsicheren Kommunikationskanal, was stets
vorausgesetzt wird.
Known-Plaintext-Attack Es stehen bekannte Klartext-Chiffretext-Paare zur Verfügung.
Hilfreich zur Schlüsselermittlung sind unter anderem verschlüsselte Anfangs- und
Endphrasen, z. B. Mit freundlichem Gruß“. So war es für das Brechen der Enigma”
Verschlüsselung, um ein konkreteres Beispiel zu nennen, sehr nützlich zu wissen,
dass viele codierte Nachrichten, die abgefangen wurden, unter anderem ein Textfragment der Form (An das) Oberkommando der Wehrmacht“ enthielten. Da auch
”
genaue Wettervorhersagen für militärische Aktionen von Bedeutung sind, wurden
diese von Wetterstationen ebenso verschlüsselt und man konnte, sofern die Vorhersagen einigermaßen akkurat waren, ziemlich sicher sein, was der Inhalt dieser
abgefangenen Nachrichten wohl sein könnte.
Chosen-Plaintext-Attack Es stehen beliebige Klartext-Chiffretext-Paare zur Verfügung.
Man kann also selbstgewählte Klartexte verschlüsseln bzw. indirekt verschlüsseln
lassen. Dies erscheint zuerst unrealistisch, aber man kann es sich als eine Art
Black-Box-Szenario vorstellen, bei welchem der Angreifer zwar Zugriff auf ein Verschlüsselungssystem, aber nicht den Schlüssel selbst hat. Direkt kann dieser Zugriff
4
sein, falls z. B. ein Server, der bestimmte Anfragen automatisch verschlüsselt im
Spiel ist. Und indirekt könnte man z. B. das Wort Vandalismus“ verschlüsseln
”
lassen, indem man vor den Augen eines Streifenpolizisten ein öffentliches Gebäude
mit Graffiti besprüht und darauf wartet, dass er einen verschlüsselten Funkspruch
absetzt. Sollte der Polizeifunk allerdings unverschlüsselt erfolgen, hat man sich
wohl umsonst verhaften lassen.
Zu den in der Kryptoanalyse verwendeten Methoden zählen die folgenden Strategien:
• Vollständige Suche: Man durchsucht den ganzen Schlüsselraum nach dem passenden Schlüssel.
• Trial-and-Error-Methode: Man testet gewisse Möglichkeiten und überprüft diese
auf Fehlerfreiheit.
• Statistische Methoden: Häufigkeitsanalysen (z. B. Buchstaben- oder Worthäufigkeit
des Klartextes und des Chiffrats).
• Strukturanalyse von Kryptosystemem: Beispielsweise das Lösen von Gleichungssystemen.
5
2 Historische Kryptoverfahren
In der klassischen Kryptographie gibt es im Wesentlichen zwei Werkzeuge zur Transformation von Klar- in Chiffretext:
Code Ein System zur Substitution ganzer Nachrichten oder Teilen davon, Wörtern oder
Silben einer Sprache durch Wörter/Zahlenfolgen einer anderen, häufig künstlichen,
Sprache. Sie arbeiten also auf semantischen Einheiten und entsprechen gewissermaßen einem festgelegten Wörterbuch. Zu den Nachteilen zählt, dass die Transformation gleicher Klartexte zu immer gleichen Chiffren führt, man ein großes
Wörterbuch benötigt und man sich auf vorher vereinbarte Sachverhalte, für die
man Codewörter erstellt, einschränken muss.
Chiffre Ein universelles Verfahren, das eine Anzahl an Kryptooperationen (Substitution
oder Permutation) benutzt, um einen beliebigen Klartext in einen Chiffretext umzuwandeln. Einheiten fester Länge des Klartextextes werden Einheiten fester Länge
des Chiffretextalphabets zugeordnet. Man operiert auf syntaktischen Einheiten.
Die oben erwähnten Kryptooperationen zur Transformation von Klartexten in Chiffretexten werden in zwei Typen unterteilt:
1. Substitution und
2. Permutation,
welche in den nächsten zwei Abschnitten näher erläutert werden.
2.1 Substitution
2.1.1 Caesar-Chiffre
Bei der Caesar-Chiffre wird jedes Zeichen des Klartextes um den Schlüssel-Wert k im
Alphabet verschoben. Man wählte bei dieser Chiffre k = 3 fest und dadurch ergibt sich
folgende Chiffrierabbildung:


A 7→ D


..
Ek :
.
.



Z 7→ C
Dies verstößt allerdings gegen das Kerckhoffs’sche Prinzip, denn aufgrund des fest gewählten, immer gleichen Schlüssels ist der gesamte Algorithmus geheim zu halten, nicht
6
nur der Schlüssel selbst. Dennoch war diese Verschlüsselung gar nicht so schlecht, schließlich konnte damals ohnehin kaum jemand lesen.
Angriff
Um eine solche simple Substitution anzugreifen, betrachtet man die Zeichenhäufigkeit.
In der deutschen Sprache ist z. B. das E der häufigste Buchstabe, ist im Chiffrat nun
F der häufigste, so wurde mit hoher Wahrscheinlichkeit der Schlüssel k = 1 verwendet.
Und kennt man den Klartext bzw. Teile davon, kann man den Schlüssel leicht ermitteln.
2.1.2 Vigenère-Chiffre
Bei der Vigenère-Chiffre wird eine möglichst lange Schlüsselfolge (im Beispiel COVER)
anstatt eines konstanten Schlüssels wie bei der Caesar-Chiffre verwendet.
Klartext:
Schlüsselfolge:
THEMATHEMATICAL
COVERCOVERCOVER
Chiffretext:
WWARSWWARSWXYFD
(Das sich wiederholende Muster WWARS lässt hier schon ohne jegliche Information über
den Klartext auf die richtige Periode 5 schließen.)
Angriffe
Man kann verschiedene Angriffe gegen Vigenère anwenden, von denen wir einige aufzählen wollen:
• Man kann die Schlüssellänge raten/durchprobieren (es sind wahrscheinlich nur
wenige 100) und es anschließend wie Caesar brechen (siehe dazu den nächsten
Teilabschnitt).
• Die Autokorrelationsfunktion, welche die relative Häufigkeit von übereinstimmenden Stellen eines Textes mit sich selbst um einige Stellen verschoben angibt, hat
einen Peak bei der Schlüsselperiode, was hilfreich ist.
• Die Methode von Kasiski & Friedman: Der Koinzidenzindex des Chiffrats, d. h. die
Wahrscheinlichkeit, dass an zwei zufälligen Stellen eines Textes dasselbe Zeichen
steht, sinkt bei steigender Schlüssellänge. (Siehe dazu den übernächsten Teilabschnitt).
Diese Chiffre galt lange Zeit als unbrechbar ( Le Chiffre indéchiffrable“) und ist tatsächlich
”
perfekt, wenn die Schlüssellänge gleich der Länge des Klartexts ist (und man somit den
One-Time-Pad erreicht hat).
Angriff: Caesar
Hat man die Periodizität l der Schlüsselfolge erkannt, kann man Vigenère wie Caesar
brechen: Man schreibt den Chiffretext in Spalten der Länge l nebeneinander, wie es in
Abbildung 2.1 zu sehen ist, und hat in jeder Zeile eine Caesar-Verschlüsselung.
7
1 l+1
2 l+2
..
..
.
.
l
2l
· · · ← Caesar
···
..
.
···
Abbildung 2.1: Anordnung des Chiffretexts zum Brechen der Vigènere-Chiffre
Man hat allerdings nicht immer das Glück, dass gleiche Teilfolgen im Klartext mit der
gleichen Schlüssellänge verschlüsselt wurden (sind sie aber entstanden, dann ist ihr Abstand ein Vielfaches der Schlüsselperiodizität). Im allgemeinen Fall wendet man die
Methode von Kasiski und Friedman an.
Angriff: Kasiski und Friedman
Definition 2.1.1: (Koinzidenzindex): Der Koinzidenzindex Ic eines Chiffretextes c gibt
die Wahrscheinlichkeit dafür an, dass zwei unabhängig voneinander gewählte Zeichen
des Chiffretextes c gleich sind. (Sinkt bei steigender Schlüssellänge.)
Für einen Chiffretext c, der aus einer Caesar-Chiffrierung hervorgegangen ist, hängt
der Koinzidenzindex Ic nicht vom Schlüssel k, sondern lediglich von den statistischen
Eigenschaften der Klartextquelle ab. Für englische Texte gilt z. B. Ic ≈ 0, 065. Diese
Unabhängigkeit von Ic bei der Caesar-Chiffre wird für die Ermittlung der Periodenlänge,
wie unten beschrieben, ausgenutzt.
Es sei ni die absolute Häufigkeit
des Zeichens ai aus dem Alphabet A in dem Chiffretext
ni der Länge n. Dann gibt es 2 = ni (n2i −1) Möglichkeiten das Paar ai ai auszuwählen:
Ic =
≈
ni 2
n
ai ∈A 2
X
P
=
X ni 2
ai ∈A
n
− 1)
Anzahl günstiger Fälle
=
n(n − 1)
Anzahl möglicher Fälle
ai ∈A ni (ni
(für großes n)
(2.1)
(2.2)
Ordnet man den Chiffretext der Länge n wie im vorherigen Bild in l Zeilen an, dann
gilt:
1. Es gibt n( nl − 1) Möglichkeiten, Zeichenpaare in derselben Zeile auszuwählen.
(Für jedes der n Zeichen, welches man als Erstauswahl betrachtet, hat man nl − 1
verbleibende Zeichen in der gleichen Zeile, die man als Zweites auswählen kann.)
2. Es gibt n(n − nl ) Möglichkeiten, Zeichenpaare in verschiedenen Zeile auszuwählen.
Sei p die Wahrscheinlichkeit dafür, in derselben Zeile gleiche Zeichenpaare auszuwählen.
Falls die Zeilenanzahl l gleich der Periode der Schlüsselfolge ist, dann kann p durch den
P
Koinzidenzindex ai ∈A p2i approximiert werden (für genügend großes n), da hier eine
Caesar-Chiffrierung vorliegt (dabei bezeichnet pi die Wahrscheinlichkeit dafür, dass die
8
Klartextquelle das Zeichen ai aussendet). Ansonsten betrachtet man die Wahrscheinlichkeit, in verschiedenen Zeilen gleiche Zeichenpaare auszuwählen, wobei hier von einer
Gleichverteilung der Zeichen auszugehen ist (Schlüssel mit unendlicher Periode), also
P
≈ ai ∈A (1/|A|)2 = 1/|A|.
Man erhält somit als Approximation für den Koinzidenzindex:

Ic =
n
n
1
· n
−1 ·
p2i + n n −
n(n − 1)
l
l
a ∈A
X

·
i
1 
|A|
(2.3)
Also gerade die Anzahl passender Zeichenpaare (in großen Klammern) durch die Anzahl
aller möglichen Zeichenpaare.
Die Periodenlänge einer Vigenère-Chiffre bestimmt man wie folgt:
1. Berechne den Koinzidenzindex gemäß (2.1) oder (2.2).
2. Vergleiche diesen mit den ermittelten theoretischen Werten für verschiedene Werte
von l nach (2.3).
Man erhält so zwar nicht immer das korrekte l, aber der Vergleich des gemessenen“
”
Koinzidenzindex mit dem theoretisch zu erwartenden Wert gibt Aufschluss über die
verwendete Chiffre; ob es eine Permutations- oder Caesar-Chiffre oder eine VigenèreChiffre mit kleinerer oder größerer Periode ist (für kleinere steigt Ic , man nähert sich
Caesar, für größere sinkt Ic , man nähert sich dem One-Time-Pad).
Varianten
Es folgen Varianten von Vigenère, die die periodische Wiederholung des Schlüssels meiden (und somit nicht mit Kasiski und Friedman zu brechen sind):
• Man wählt einen Schlüsselanfang der Länge l und verschlüsselt die ersten l Klartextzeichen mit diesem Schlüssel. Dann wird der Klartext als Schlüssel verwendet.
• Man wählt einen sich nicht wiederholenden Text als Schlüssel. Wählt man aber
einen Text einer natürlichen Sprache, dann kann man über die relative Häufigkeit
der Zeichen dieser Sprache hochwahrscheinliche Paare von Klartext- und Schlüsselbuchstaben angeben und durch Ausprobieren Teilfolgen des Schlüssels und Klartextes bestimmen. Fehlende bzw. unsichere Buchstaben kann man durch Kontextbetrachtung gewinnen, hierbei sind Häufigkeitsverteilungen von Bigrammen,
Trigrammen, etc. sowie Einzelwortwahrscheinlichkeiten nützlich.
• One-Time-Pad: Man verwendet eine echte Zufallsfolge, die genauso lang wie der
Klartext ist als Schlüssel und verwendet diesen nur ein einziges Mal. (Die einzige
Chiffre, die perfekt sicher ist.)
2.2 Permutation
Bei der Permutation werden Texte in Blöcke fester Länge eingeteilt und die Blockinhalte
über Schlüssel permutiert.
9
Angriff
Ein Angriff kann über die Aufstellung einer Bigramm-Statistik erfolgen:
1. Rate die Blocklänge L durch vollständiges Durchprobieren, L muss dabei die Chiffratlänge teilen.
2. Schreibe das Chiffrat Zeilenweise in eine Matrix der Breite L.
3. Berechne für je zwei Spalten i, j die Wahrscheinlichkeit, dass im Klartext i direkt
vor j stand.
4. Die erste Klartextspalte hat keinen wahrscheinlichen Vorgänger“, es folgt also
”
jeweils der wahrscheinlichste Nachfolger“.
”
2.3 Rotorenchiffren
Man begann am Anfang des 20. Jahrhunderts, eine große Anzahl verschiedener Substitutionen zum Verschlüsseln zu verwenden. Und zwar wechselte man diese Substitutionen
regelmäßig nach dem Verschlüsseln eines einzelnen Zeichens. Diese große Anzahl von
Wechseln ließ sich manuell kaum noch bewerkstelligen, sodass man (elektro-)mechanische
Maschinen entwickelte, die diese Substitutionen und ihre Wechsel durchführten.
2.3.1 Die Hagelin-Maschine C-34
Die Hagelin C-34 ist eine Rotormaschine, deren Rotoren binäre Werte zurückgeben,
die durch zyklisch rückgekoppelte binäre Schieberegister beschrieben werden können.
Mit diesen Rotoren wird eine Pseudozufallsfolge generiert, mit deren Hilfe eine Vigenère-Verschlüsselung durchgeführt wird. Wie die meisten historischen Rotormaschinen arbeitet sie über den Zahlen von 0 bis 25, also über Z26 . Die Rotoren sind zyklisch
rückgekoppelte Schieberegister der Längen 17, 19, 20, 21 und 23. Da die Längen der Rotoren paarweise teilerfremd sind, ergibt sich eine Periodenlänge von 17 · 19 · 20 · 21 · 23 =
3120180. Ihre Ausgaben werden als die Binärdarstellung eines Index in eine Schlüsselliste
aufgefasst. (Der Index in die Schlüsselliste ist 5 Bit lang, welche somit 32 Werte aus Z26
enthält.) Von diesem so indizierten Wert wird der Klartext subtrahiert (Modulo 26).
Die hier verwendete Subtraktion hat den Vorteil, dass das System selbstinvers ist. Der
Schlüssel dieses Verfahrens, welches in Abbildung 2.2 zu sehen ist, wird von der Initialbelegung der Schieberegister und dem Inhalt der Schlüsselliste gebildet.
Angriff
Die Idee des Angriffs ist es nicht die exakten Einstellungen und somit den Schlüssel
dieser Maschine zu ermitteln, sondern nur äquivalente Einstellungen zu finden, die es
einem ermöglichen, Texte zu dechiffrieren.
1. Mithilfe von Klartext-Chiffrat-Paaren kann man den Schlüsselstrom erhalten, aber
der Index bleibt unbekannt.
10
2. Schreibt man ein häufig vorkommendes Zeichen am Anfang der Schlüsselliste (s[0]),
kann man z. B. die Nullerfolge als Index annehmen. Somit sind die Rotoren-Werte
gleich 0.
3. Man sucht nun nach Rotorenstellungen, in der 4 von 5 Ausgabebits bekannt sind,
vervollständigt das 5. Ausgabebit (sodass man einen neuen Index erhält) und ebenso die Schlüsselliste (indem man den Schlüssel-Buchstaben an der mometane Rotorenposition einfügt)
4. Schließlich wiederholt man den dritten Schritt bis alles vollständig ermittelt wurde.
Rotor 1
Rotor 2
Rotor 3
Rotor 4
Rotor 5
Schlüsselliste
Klartext
−
s[0]
s[1]
..
.
s[30]
s[31]
Index in die Schlüsselliste
Chiffretext
Abbildung 2.2: Struktur der Hagelin-Maschine
11
3 Einführung zu Blockchiffren &
Konstruktionen
3.1 Definitionen
Definition 3.1.1: (Blockchiffre): Gegeben seien zwei endliche Alphabete A, B und n, m ∈
N sowie ein Schlüsselraum K. Eine Blockchiffre ist gegeben durch eine Familie von injektiven Abbildungen fk : An → B m mit k ∈ K. In der Regel gilt A = B = {0, 1} und
n = m (die fk sind dann zwangsläufig bijektiv).
Blockchiffren sind meist Produktchiffren, d. h. mehrere Substitutionen (S-Boxen, von
Shannon bezeichnet als confusion“) und Permutationen (P -Boxen, diffusion“) hinter”
”
einander, da wir wissen, dass einfache Substitutions- und Permutations-Chiffren nicht
sicher sind. Bei einer Blockchiffre teilt man einen Klartext in Blöcke fester Länge ein
und chiffriert diese einzeln mit einer für alle Blöcke gleichen Verschlüsselungsfunktion.
Als sequentielle Chiffren oder Stromchiffren bezeichnet man Verschlüsselungsverfahren,
bei denen die Folge von Klartextzeichen nacheinander mit einer in jedem Schritt variierenden Funktion verschlüsselt wird. Es wird also ein Klartext mit unabhängig davon
erzeugten Schlüsselstrom (Zufall) verknüpft.
Anforderungen
Damit man auch effizient nutzbare und sichere Blockchiffren hat, müssen folgende Anforderungen gelten:
• Gegeben den Schlüssel k, muss sowohl fk als auch fk−1 effizient berechenbar sein.
• Ein Angreifer kann nicht unterscheiden zwischen einem Orakel Oi (ideal), welches
eine zufällige Injektion An → B m implementiert, und dem Orakel Or (real), welches
die gegebene Blockchiffre mit zufälligem Schlüssel implementiert. Formal lässt sich
dies über Wahrscheinlichkeiten definieren, wobei AO bedeutet, dass der Angreifer
A Zugriff auf das Orakel O hat:
|P [AOi → 0] − P [AOr → 0]| = negligible(|k|).
Hierbei gilt zu beachten, dass A polynomial beschränkt ist und wenn man eine
Funktion µ als negligible ( vernachlässigbar“) bezeichnet, bedeutet dies, dass die
”
Funktion asymptotisch schneller verschwindet als jedes Polynom. Formaler ausgedrückt sagt man, dass eine Funktion µ negligible ist, sofern gilt:
∀d ∈ N ∃x0 ∈ N ∀x > x0 : |µ(x)| < x−d .
12
Achtung: Diese asymptotische Aussage betrifft keine konkrete Schlüssellänge. Man will
das Problem eines Angriffs nämlich so allgemein wie möglich beschreiben, darum gibt
es keine exakte Angabe eines Sicherheitsparameters (z. B. einer Schlüssellänge). Es muss
nur gezeigt werden, dass der Aufwand für einen Angreifer im Vergleich zu dem Aufwand
eines Nutzers in Abhängigkeit dieses Parameters viel schneller wächst. Sollte dann ein
Sicherheitssystem gebrochen werden (z. B. aufgrund des technischen Fortschritts bei der
Rechnerentwicklung, die ein schnelleres Durchsuchen des Schlüsselraums erlaubt), kann
man einfach diesen Parameter vergrößern, um das System erneut abzusichern.
Ideal Cipher
Eine Ideal Cipher (IC) ist eine (Über-)Idealisierung einer Blockchiffre. Jedem Schlüssel
k ∈ {0, 1}λ ist eine vollkommen zufällige Permutation Pk : {0, 1}n → {0, 1}n zugeordnet
(hierbei sind λ und n Sicherheitsparameter) und per Orakelzugriff kann jede Maschine
im Modell die Funktionen Pk und Pk−1 auswerten. Die Existenz einer solchen IC wird
zur Vereinfachung von Beweisen angenommen, man spricht dann von dem Ideal-CipherModell.
Achtung: Es gibt (pathologische) Protokolle, die zwar im idealisierten IC-Modell beweisbar sicher sind, jedoch alle Sicherheit verlieren, wenn man die IC durch einen öffentlich
bekannten, volldeterministischen Algorithmus ersetzt. Der Unterschied zu Definition
3.1.1 liegt darin, dass der Angreifer den Schlüssel kennt (bzw. ihn sogar wählt).
3.2 DES (Data Encryption Standard)
Der Data Encryption Standard (DES) wurde von IBM mit Unterstützung der National Security Agency in den 70ern entworfen. Aufgrund seiner geringen Schlüssellänge
von effektiv nur 56 Bit wird er als nicht mehr sicher angesehen. Im Jahre 1998 wurde
DES durch einen 250.000$-Parallelrechner der Electronic Frontier Foundation (EFF) gebrochen, dieser durchsuchte einfach den gesamten Schlüsselraum in etwa neun Tagen.
Allerdings gibt es trotz intensiver Forschungsarbeiten keinen wirklichen Angriff, der in
der Praxis besser ist als das bloße Durchprobieren aller möglichen Schlüssel. Darum
entwickelte man verbesserte Varianten von DES, die wir am Ende dieses Abschnitts
vorstellen werden.
Die Abbildung 3.1 zeigt den groben Aufbau von DES. Am Anfang findet eine Permutation satt und am Ende wird deren inverse Permutation ausgeführt, da diese Permutationen
aber fest und bekannt sind, können sie für unsere weitere Betrachtung des DES entfallen.
Es gilt auch, dass die Ver- und Entschlüsselung aufgrund der Konstruktionseigenschaft
bis auf die (genau umgekehrte) Reihenfolge der verwendeten Teilschlüssel identisch sind.
Um genauer auf den Aufbau des DES einzugehen, müssen wir erst erklären, was man
unter einem Feistel-Netzwerk versteht. In [KL07] wird es beschrieben als eine alternative
zur Verwendung einfacher Substitutionen und Permutationen zur Erstellung von Blockchiffren. Zwar werden diese meistens auch innerhalb eines Feistel-Netzwerkes genutzt,
13
Input
64 Bit
Initiale Permutation
32 Bit
k1
L0
32 Bit
R0
F
L1
..
R1
k16
L15
R15
F
Inverse Initiale Permutation
Output
Abbildung 3.1: DES Verschlüsselungsalgorithmus
aber auf geschickte Weise miteinander verbunden, sodass für die Substitutionen nicht
mehr gelten muss, dass sie invertierbar sind. Dies ist vorteilhaft, da die Invertierbarkeit
zwangsläufig größere Struktur in das System bringt, wobei man aber von einer guten
Blockchiffre eher ein unstrukturiertes (also zufällig aussehendes) Verhalten erwartet. Ein
Feistel-Netzwerk besteht aus mehreren Runden, die gleich aufgebaut sind. In der i-ten
Runde wird die Eingabe als aus zwei Hälften Li−1 (linke Hälfte) und Ri−1 (rechte) bestehend betrachtet. Die linke Eingabehälfte für die nächste Runde, also Li , ist die rechte
Hälfte der momentanen Runde, also Ri−1 . Auf Li−1 wird noch eine Funktion F (deren
Eingabe ein Rundenschlüssel und Ri−1 sind), aufaddiert, sodass man die neue rechte
Hälfte Ri erhält. Auf die genaue Zusammensetzung dieser F -Funktion werden wir nun
eingehen.
14
F -Funktion
Die F -Funktion F (Ri−1 , ki ) erhält als Eingabe Ri−1 , die rechte Hälfte des internen Zustands nach der i − 1-ten Runde, und mit ki den Rundenschlüssel für die i-te Runde.
Der Ablauf wird nun erläutert und ist ebenso in Abbildung 3.2 zu sehen.
Ri−1
(32 Bit)
ki
Erw.
(48 Bit)
(48 Bit)
(6 Bit)
(6 Bit)
S1
...
(4 Bit)
S8
(4 Bit)
P
F (Ri−1 , ki )
Abbildung 3.2: F -Funktion
1. Zuerst sorgt die Expansion Erw.(Ri−1 ) dafür,
erweitert wird. Mit Ri−1 = (r1 , . . . , r32 ) lässt
durch
(r32 , r1 ,
r4 , r5 ,
r8 , r9 ,
r12 , r13 ,
Erw.(Ri−1 ) =
r16 , r17 ,
r20 , r21 ,
r24 , r25 ,
r28 , r29 ,
dass die Eingabe von 32 auf 48 Bit
sich diese Erweiterung beschreiben
r2 , . . .
r6 , . . .
r10 , . . .
r14 , . . .
r18 , . . .
r22 , . . .
r26 , . . .
. . . r32 ,
r5 ,
r9 ,
r13 ,
r17 ,
r21 ,
r25 ,
r29 ,
r1 ).
Eine grafische Repräsentation davon findet man in Abbildung 3.3.
2. Diese erweiterten 48 Bits werden mit dem i-ten Rundenschlüssel ki addiert, also
erhält man Erw.(Ri−1 ) ⊕ ki .
3. Je 6 Bit davon werden zu einer der acht S-Boxen geführt (diese sind Tabellen
und die Eingangsbits dienen der Indizierung), deren Ausgänge je 4 Bit liefern. Die
15
S-Boxen werden durch eine 4 × 16-Matrix beschrieben und jede Zeile stellt eine
Substitution dar. Die Substitutionen sind nichtlinear und der kryptologisch wichtigste Teil. (Die 8 Boxen mit je 4 Substitutionen liefern insgesamt 32 verschiedene
Substitutionen.)
4. Die Ausgabe der S-Boxen werden abschließend noch einer Permutation P unterworfen.
r1 r2 r3 r4
r5 r6 r7 r8
r9
...
r32 r1 r2 r3 r4 r5
r4 r5 r6 r7 r8 r9
r8 r9
Abbildung 3.3: Erweiterungsfunktion Erw.(Ri−1 ) mit Ri−1 = (r1 , . . . , r32 )
Technische Daten und Ablauf
Nach diesen Eingangsbemerkungen wollen wir nun die technischen Daten des DES genauer betrachten:
• Es wird eine Feistel-Struktur mit 16 Runden verwendet (dies ermöglicht z. B. die
Ver- & Entschlüsselung mit der gleichen Hardware).
• Die Blocklänge des DES beträgt 64 Bit, d. h. dass man mit einer Eingabe von 64
Bit arbeitet, wobei diese intern als zwei 32-Bit-Blöcke verarbeitet werden.
• Der Schlüsselraum hat eine Größe von 56 Bit (zusätzlich ergänzen 8 Paritätsbits
die acht 7-Bit-Zeichen eines Nachrichtenblocks auf ungerade Parität). Dies wurde
bereits vor Inkrafttreten des Standards als zu kurz kritisiert.
• Die Rundenschlüssel ki sind je 48 Bit groß. Es wird eine Auswahlfunktion auf
den 56-Bit-Hauptschlüssel angewendet, welche Permutationen, zirkuläre Linksshifts und Bit-Auswahlen (Selects) beinhaltet und gut umkehrbar ist.
Der Ablauf, auf den zuvor schon lose eingegangen wurde, soll hier zusammenhängend
und kompakt dargestellt werden:
1. Es erfolgt zuerst eine initiale Permutation auf der in Blöcken eingeteilten Eingabe.
2. Anschließend gibt es 16 Runden mit verschiedenen Rundenschlüsseln, wobei die
Runden funktional identisch sind:
Li = Ri−1 , Ri = Li−1 ⊕ F (Ri−1 , ki ).
Mit Li und Ri bezeichnet man wie bereits erwähnt die linken bzw. rechten Texthälften während den Verschlüsselungschritten und dies wird in Abbildung 3.1 auch
genauer erkennbar.
16
3. Abschließend findet die inverse Permutation zur initial ausgeführten statt.
Entwurfskriterien
Die Entwurfskriterien wurden erst nachträglich veröffentlicht, sodass es Befürchtungen
gab, die NSA hätte Hintertüren in die Verschlüsselung eingebaut. Heute kann man allerdings sagen, dass diese Befürchtungen (in diesem Fall) unbegründet waren. Die Kriterien
lauten:
• Keine S-Box ist eine lineare oder eine affine Funktion ihrer Eingabe.
• Die Änderung eines Eingabebits einer S-Box bewirkt eine Änderung von wenigstens
zwei Ergebnisbits.
• Die S-Boxen sind so gewählt, dass das Hamming-Gewicht des S-Box-Ergebnisses
möglichst konstant bleibt, wenn irgendein Eingabebit konstant gehalten wird.
Variationen
Der DES ist bis heute strukturell ungebrochen, aber brute force ist, wie eingangs erwähnt,
aufgrund des zu kleinen Schlüsselraums möglich. Um diesem Problem des zu kleinen
Schlüsselraums zu begegnen, wäre die naive Idee einfach einen größeren Schlüssel zu
nehmen, allerdings würde dies gegen den Standard verstoßen und DES ist bereits in vielen Hardware-Implementationen mit fester Schlüssellänge vorzufinden. Man kann aber,
wenn man den Schlüssel schon nicht vergrößern kann, einfach mehrere Schlüssel nehmen, indem man den DES z. B. verschachtelt ausführt. Diese nachfolgenden Varianten,
die alle mehr Schlüssel bieten als der ursprüngliche DES und damit den Schlüsselraum
signifikant vergrößern, sind alle praxistauglich und gelten als sicher:
Triple DES Beim Triple DES verschlüsselt man den Klartext m zuerst normal mit DES
mit einem Schlüssel k1 , anschließend entschlüsselt man dieses so erzeugte Chiffrat
mit einem Schlüssel k2 und verschlüsselt das Ergebnis davon mit einem Schlüssel
k3 , um das Triple-DES-Chiffrat c zu erhalten. Etwas formaler ausgedrückt:
C = DESk1 (DES−1
k2 (DESk3 (m)))
Die Entschlüsselung in der Mitte scheint ein wenig seltsam und hat nichts mit
Sicherheit zu tun, es ist eine praktische Überlegung. Sind nämlich alle drei Schlüssel
gleich, erhält man die normale DES-Verschlüsselung.
2-Key-3DES Der 2-Key-3DES ist im Grunde der Triple-DES, allerdings gilt k1 = k3 .
Außerdem ist der 2-Key-3DES in der Theorie nicht so sicher wie der Triple-DES.
Einen Angriff auf den 2-Key-3DES werden wir im Abschnitt 4.2 betrachten.
DES-X Beim DES-X wird nicht nur ein Schlüssel k zum Betrieb des DES verwendet,
sondern auch zwei Schlüssel kx , ky direkt auf den Klartext bzw. das DES-Chiffrat
addiert, um somit das DES-X-Chiffrat c zu erzeugen. Diese zusätzliche Addition
mit Schlüsseln wird auch als key whitening bezeichnet und soll die Struktur des
Klartextes zusätzlich verschleiern. Das Chiffrat lässt sich also beschreiben per:
c = DESk (m ⊕ kx ) ⊕ ky .
17
Einen theoretischen Angriff auf DES-X werden wir im Abschnitt 4.4 betrachten.
Frugal DES-X Der Frugal DES-X ist eine Vereinfachung von DES-X, es gilt nämlich für
die verwendeten Schlüssel kx = ky .
18
4 Meet-in-the-Middle, Slide-Attack &
Related-Key-Attack
Bei der generellen Angriffsstrategie gegen rundenweise Blockchiffren versucht man, Zwischenergebnisse zu berechnen bzw. zu approximieren, um damit einzelne Rundenschlüssel
anzugreifen. Dies kann auf verschiedene Weisen erfolgen, so versucht man z. B. in gewisser
Form beim Meet-in-the-Middle-Ansatz ein großes Problem (ein zu großer Schlüsselraum)
in mehrere kleinere zu zerlegen. Man kann aber auch die Selbstgleichheit von Verschlüsselungsrunden ausnutzen, wie dies bei den Slide-Attacks geschieht oder einen einfachen, sich wiederholenden Aufbau einer Runden- bzw. Teilschlüsselgenerierung als Ansatzpunkt wählen, wie dies bei den Related-Key-Attacks der Fall ist.
4.1 Meet-in-the-Middle gegen 2DES
Bei einem Meet-in-the-Middle-Angriff versucht man Zwischenergebnisse beim Verschlüsseln (Vorwärtsschritt) und Entschlüsseln (Rückwärtsschritt) zu finden, die gleich sind.
Für die einzelnen Schritte probiert man einfach alle möglichen Schlüssel durch (brute
force). Findet man ein passendes Zwischenergebnis, hat man sich also in der Mitte getroffen, ist es sehr wahrscheinlich, dass die per Ausprobieren gefundenen Schlüssel für
die einzelnen Schritte zusammen den gesuchten Schlüssel ergeben. Dies wollen wir nun
ausführlicher am 2DES demonstrieren. Das Chiffrat bei 2DES ergibt sich zu
c = DESk2 (DESk1 (m))
und die Struktur der Verschlüsselung ist in Abbildung 4.1 zu sehen. Es wird einfach die
DES-Verschlüsselung zwei Mal mit unterschiedlichen Schlüsseln auf den Klartext bzw.
das Zwischenergebnis ausgeführt.
m
k1
k2
E1
E2
c
Abbildung 4.1: 2DES
Würden wir nun die Zwischenergebnisse (nach E1 ) kennen, könnten wir die Schlüssel einzeln per brute force herausfinden. Auf diese Weise wollen wir nun, wie zuvor beschrieben,
die Verschlüsselung brechen.
19
Vorgehen (Known-Plaintext-Attack)
Mit den bekannten Klartext-Chiffrat-Paaren m1 , c1 und m2 , c2 kann man nun einen
Angriff ausführen. Zuerst berechnet man mit einem beliebig gewählten Schlüssel ausgehend von den bekannten Klartexten m1 , m2 mögliche Zwischenchhiffrate, führt also
nur eine einfache DES-Verschlüsselung aus. Anschließend führt man mit einem anderen Schlüssel eine Entschlüsselung der bekannten Chiffrate c1 , c2 durch. Sollten die bei
Ver- und Entschlüsselung erhaltenen Zwischenwerte identisch sein, hat man sich in der
Mitte getroffen, also die korrekten Schlüssel verwendet. Dabei benötigte man jedes Mal
nur einen Aufwand in der Größe eines einzelnen Schlüssels und nicht der Summe ihrer
Größe; man hat den Aufwand also halbiert. Man kann den Angriff algorithmisch in drei
Schritten beschreiben:
1. Vorwärtsschritt: Für alle k = 0, . . . , 256 − 1 tabelliere
[DESk (m1 ), DESk (m2 ), k]
2. Sortierschritt: Sortiere die Tabelle lexikographisch.
3. Rückwärtsschritt: Für alle k = 0, . . . , 256 − 1 berechne
−1
DES−1
k (c1 ), DESk (c2 )
und suche nach Treffern in der sortierten Tabelle per binärer Suche.
Aufwand
Es werden nur zwei Klartext-Chiffrat-Paare benötigt aber als Speicher benötigt man
ungefähr 260 Byte, also Exabyte, schnellen Speicher. Das Sortieren über FestplattenZugriffszeiten wäre viel zu langsam. Der Aufwand für die einzelnen Schritte lautet:
• Vorwärtsschritt: ≈ 2 · 256 DES-Operationen.
• Sortierschritt: ≈ 56 · 256 Vergleiche.
• Rückwärtsschritt: ≈ 2 · 255 DES-Operationen (nur 255 , da man nach der Hälfte
ungefähr fertig ist), plus ≈ 56 · 256 (Tabellen-)Vergleiche.
Eine Variante des Angriffs kommt mit weniger Speicher aus, aber das Produkt aus Laufzeit und Speicher ist im Wesentlichen konstant. Lässt man z. B. das letzte Byte in der
Tabelle weg, wird diese kleiner, man hat aber mehr falsche Treffer (false positive), die
man genau nachprüfen muss.
4.2 Advanced Meet-in-the-Middle gegen 2Key-3DES
Der DES, welcher ja schon früh für seine geringe Schlüssellänge kritisiert wurde, sollte
durch die Verwendung von zwei- bzw. sogar dreifacher Verschlüsselung sicherer gemacht
werden. Allerdings wurde in [MH81] bemerkt, dass dieser Zuwachs an Sicherheit nicht
unbedingt so groß wie erhofft ist und es wurde auch gleich ein Angriff auf den 2Key-3DES
vorgestellt. Mit einer dreifachen Ausführung des DES kann man nun keine Zwischenwerte
20
mehr direkt berechnen und vergleichen. Zur Erinnerung: Bei 2Key-3DES lässt sich die
Verschlüsselung eines Klartextes m darstellen als
c = DESk1 (DES−1
k2 (DESk1 (m)))
oder über Zwischenwerte Z1 , Z2 als
Z1 = DESk1 (m), Z2 = DES−1
k2 (Z1 ), c = DESk1 (Z2 ).
Wäre der erste Zwischenwert Z1 bekannt, könnte man den 2Key-3DES wie den 2DES
angreifen. Wie kommt man aber zu diesem Zwischenwert? Man wählt ihn einfach selbst.
Setzt man z. B. Z1 = 0 und berechnet für alle möglichen Schlüssel k nun DES−1
k (0),
erhält man alle möglichen Klartexte m k , deren erster Zwischenwert eben null wäre.
Wählt man als Angriffsart eine Chosen-Plaintext-Attack, kann man sich diese selbst
erstellten Klartexte zu den passenden Chiffraten c k verschlüsseln lassen. Die Menge aller
Klartexte m k kann man auch als die Menge aller zweiten Zwischenwerte Z2 auffassen,
da für diese die gleiche Berechnung, die DES-Entschlüsselung, durchgeführt wird. Man
rechnet die Chiffrate ci nun zu den zweiten Zwischenwerten Z2 zurück per DES−1
i (ci ).
Findet man einen Wert, der mit einem Klartext mj übereinstimmt, lauten die Schlüssel
k1 = i, k2 = j. Mit k1 = i hat man nämlich sowohl den Klartext aus dem selbst gewählten
ersten Zwischenwert Z1 als auch den zweiten Zwischenwert Z2 aus dem erfragten Chiffrat
errechnet und da die Menge der Klartexte auch die Menge der zweiten Zwischenwerte
darstellt, liefert ein übereinstimmendes mj den zweiten Schlüssel k2 = j. Diesen Angriff
wollen wir nun etwas formaler festhalten.
Vorgehen (Chosen-Plaintext-Attack)
Als erster Zwischenwert wird 0 . . . 0 gewählt. Der Angriffsablauf, mitsamt einigen im
Folgenden verwendeten Bezeichnungen, ist in Abbildung 4.2 visualisiert.
m
DES
k1
0...0
DES−1
Pj = Bi
k2
DES
ck
c
k1
Abbildung 4.2: Advanced Meet-in-the-Middle bei 2Key-3DES
1. Für alle möglichen Schlüssel k: Tabelliere Pk := DES−1
k (0 . . . 0) samt verwendetem
Schlüssel und einer Markierung Mitte“, also
”
(Pk , k, Mitte).
(Dies liefert sowohl alle zweiten Zwischenwert als auch alle Klartexte, die zu dem
ersten Zwischenwert 0 . . . 0 führen.)
21
2. Für alle k: Erfrage Chiffrate c k zu Pk .
3. Für alle k: Tabelliere
(Bk , k, Ende)
mit Bk := DES−1
k (c k ).
4. Verbinde die beiden Tabellen und sortiere diese gemeinsame Liste nach dem ersten
Feld. Nun suche zwei aufeinanderfolgende identische Einträge im ersten Feld, also
Bi = Pj aus (Bi , i, Ende) und (Pj , j, Mitte). Damit hat man einen Schlüsselkandidat der Form k1 = i, k2 = j gefunden. (Die Markierungen Mitte“ bzw. Ende“
”
”
lassen einen hierbei wissen, welcher der gefundenen Werte i, j der erste bzw. zweite
Schlüssel ist, was man natürlich ohne Markierungen einfach testen könnte).
5. Teste den Schlüsselkandidat an einigen Klartext-Chiffrat-Paaren.
Aufwand
Dieser Angriff benötigt ungefähr 256 Verschlüsselungsanfragen und hat ansonsten folgenden Ressourcenaufwand:
• Rechenaufwand: ≈ 2 · 256 DES-Operationen + ≈ 57 · 257 Sortier-Aufwand
• Speicherbedarf: ≈ 260 Byte
4.2.1 Eine Variante per Known-Plaintext-Attack
Bei einer anderen Form dieses Angriffs werden in [OW06] zufällige Werte für den Zwischenwert Z1 durchprobiert (anstatt nur Z1 = 0 . . . 0 wie zuvor zu betrachten), bis man
eine passende Wahl für Z1 getroffen hat:
1. Die als gegeben angenommenen n Klartext-Chiffrat-Paare (mi , ci ) werden in einer
Tabelle gespeichert, sortiert bzw. gehasht nach dem Klartext.
2. Wähle ein zufälliges Z1 . Für alle möglichen Schlüssel k1 :
a) Berechne m = DES−1
k1 (Z1 ).
b) Suche ein zu m passendes mi in der Tabelle, falls dies vorhanden sein sollte,
berechne Bi = DES−1
k1 (ci ) und tabelliere den Zwischenwert Bi und Schlüsselkandidat k1 in einer zweiten Tabelle.
3. Für alle k2 :
a) Berechne Pj = DES−1
k2 (Z1 )
b) Suche nach einem zu Pj passenden Bi in der zweiten Tabelle. Falls dies vorhanden sein sollte, sind die in den Tabellen gespeicherten k1 , k2 Schlüsselkandidaten.
4. Teste die Schlüsselkandidaten mithilfe der Klartext-Chiffrate-Paare auf Korrektheit. Sollte keiner gefunden werden, gehe zu Schritt 2.
22
Der Aufwand lautet dann bei n Klartext-Chiffrat-Paaren:
• Rechenaufwand: ≈ (256 ) · (264 /n) = 2120 /n [= 2120−log n ], also die Anzahl aller Schlüsselkombinationen mal der wahrscheinlichen Anzahl an zu probierenden
Werten für Z1 bis man einen Treffer erhalten sollte.
• Speicherbedarf: ≈ n
4.3 Slide-Attack
Bruce Schneier bemerkte: Except in a few degenerate cases, an algorithm can be made
”
arbitrarily secure by adding more rounds.“ Und einen solchen simplen, etwas dege”
nerierten“ Algorithmus wollen wir nun einführend analog zu [BW00] betrachten und
daran die Idee des Slide-Angriffs erklären. Ist nämlich ein solcher Angriff möglich, kann
man die Chiffre interessanterweise nicht wieder durch das bloße Hinzufügen von mehr
Runden sicher machen. Man nutzt nämlich die Selbstähnlichkeit einer Chiffre aus und
vergleicht diese mit sich selbst bei vorangeschrittener Bearbeitung (also z. B. um eine
Runde versetzt).
Gegeben sei eine Chiffre wie sie in Abbildung 4.3 zu sehen ist, bei der die gleiche Funktion mehrfach hintereinander mit gleichem Schlüssel auf dem Klartext ausgeführt wird.
Hierbei wird angenommen, dass eine Key-Recovery gegen f praktikabel ist (d. h. um den
Schlüssel k zu berechnen gilt, dass der Aufwand dafür um einiges kleiner als 2|k| ist).
m
k
k
f
f
k
...
f
c
Abbildung 4.3: Verschlüsselung mit gleichbleibender Funktion f und Schlüssel k
Idee/Ziel
Man sucht ein slid pair “, welches so heißt, da man im Bearbeitungspfad eine Stelle
”
nach rechts gerutscht“ ist. Dieses slid pair lautet:
”
(m, c), (m 0 , c 0 ) mit m 0 = fk (m), c 0 = fk (c).
Die Verschlüsselung von m zu c unterscheidet sich also von der Verschlüsselung von m 0
zu c 0 nur dadurch, dass letzteres ein Mal mehr unter dem gleichen Schlüssel bearbeitet
wird, also schon eine Runde weiter ist.
Vorgehen
1. Für je zwei Klartext-Chiffrat-Paare (m, c), (m 0 , c 0 ) berechne einen Schlüssel k, sodass m 0 = fk (m) gilt und teste, ob c 0 = fk (c) gilt.
23
2. Falls ja, wurde ein guter Kandidat gefunden (es könnte ja sein, dass ein Schlüssel
nur gerade für dieses Paar geklappt hat). Man testet nun, ob es ein false positive
ist, indem man den Schlüssel an anderen Paaren testet.
Aufwand
Bevor wir den Aufwand genauer besprechen, ist es hilfreich das Geburtstags-Paradoxon
zu erklären. Dieses besagt, dass die Wahrscheinlichkeit p, in einer Gruppe von n Personen mindestens zwei zu finden, die den gleichen Geburtstag haben, überraschend hoch
ist. Es gibt ja auch immerhin n(n − 1)/2 mögliche Paare zu betrachten. Um das Paradoxon besser zu verstehen, betrachten wir erstmal die Gegenwahrscheinlichkeit dazu.
365−(n−1)
364
Diese lautet 1−p = 365
, da die Wahrscheinlichkeit, dass die erste unter365 · 365 · · ·
365
suchte Person mit den bisherigen untersuchten keinen Geburtstag teilt 1 = 365
365 ist und
die Wahrscheinlichkeit, dass die zweite untersuchte Person keinen Geburtstag mit den
bisher untersuchten teilt, dementsprechend um einen Tag verringert ist, etc. Für n = 23
Personen gilt schließlich p ≈ 1/2. In [KL07] Appendix A.4 wird diese Wahrscheinlichkeit
p verallgemeinert, indem man q Elemente aus einer Menge von N betrachtet:
Lemma (Untere Grenze für p): Wählt man q Elemente yi , . . . , yq aus einer Menge der
Größe N (mit N fest gewählt) uniform, unabhängig und zufällig aus, dann gilt für die
Wahrscheinlichkeit p, dass es von einander verschiedene i, j mit yi = yj gibt, folgendes:
p≤
q2
.
2N
√
Lemma (Obere Grenze für p): Wählt man q ≤ 2N Elemente yi , . . . , yq aus einer
Menge der Größe N (mit N fest gewählt) uniform, unabhängig und zufällig aus, dann
gilt für die Wahrscheinlichkeit p, dass es von einander verschiedene i, j mit yi = yj gibt,
folgendes:
q(q − 1)
p≥
.
4N
Betrachtet und analysiert√man diese beiden oberen und unteren Grenzen zusammen,
zeigen diese, dass für q ≤ N , die Wahrscheinlichkeit
für eine Kollision Θ(q 2 /N ) lautet.
√
Alternativ kann man sagen, dass für q = Θ( N ) die Wahrscheinlichkeit für eine Kollision
konstant ist. Mit diesem Vorwissen, können wir nun den Aufwand besprechen:
• Es sind nach dem Geburtstags-Paradoxen bei einer Blocklänge von n Bit höchstens
ungefähr 2n/2 Klartext-Chiffrat-Paare nötig.
• Oft reichen aber auch schon weniger Paare, da man z. B. bei einer Feistel-Chiffre
mit immer demselben Rundenschlüssel zu einer Nachricht m = (L, R) ein passendes
m 0 = (R, fk (R) ⊕ L) suchen kann und der Aufwand nun nur noch ungefähr 2n/4
beträgt, da die halbe Nachricht fest ist (so kann man z. B. entweder L oder R auf
null setzen).
24
4.4 Advanced Slide-Attack gegen DES-X
In [BW00] wird ein fortgeschrittener Angriff mit der Slide-Methode vorgestellt, welcher
im Folgenden genauer erklärt wird. Beim DES-X wird nicht mehrfach verchlüsselt, so
dass zunächst eine Slide-Attack nicht einsetzbar scheint. Hängt man aber eine Ver- und
eine Entschlüsselung leicht überlappend aneinander, so ist die Technik trotzdem anwendbar. Dieses Vorgehen wird in [BW00] als twist“ bezeichnet. Das Chiffrat bei DES-X
”
lässt sich wie zuvor beschrieben darstellen als c = DESk (m ⊕ kx ) ⊕ ky und der Klartext
somit als m = DES−1
k (c ⊕ ky ) ⊕ kx .
Idee/Ziel
Man versucht slid pairs“ (m, c), (m0 , c0 ) zu finden, die die Eigenschaft c ⊕ c0 = ky
”
erfüllen. Dadurch erhalten wir eine Gegenüberstellung der Ver- und der Entschlüsselung
beim DES-X, wie sie in Abbildung 4.4 veranschaulicht wird. Für jedes slid pair gilt:
−1 0
m = kx ⊕ DES−1
k (c ⊕ ky ) = kx ⊕ DESk (c )
−1
0
m0 = kx ⊕ DES−1
k (c ⊕ ky ) = kx ⊕ DESk (c).
Daraus ergibt sich folgendes Suchkriterium für slid pairs:
−1 0
0
m ⊕ DES−1
k (c) = m ⊕ DESk (c ).
m
kx
k
E
c0
c0
ky
c
c
k
D
kx
m0
Abbildung 4.4: DES-X: Sliding with a twist“
”
Vorgehen (Known-Plaintext-Attack)
Mithilfe dieses Suchkriteriums und einer Menge von Klartext-Chiffrat-Paare (m, c), muss
man folgendes für alle Schlüssel k durchführen:
25
−1 0
0
1. Suche (m, c), (m0 , c0 ), sodass m ⊕ DES−1
k (c) = m ⊕ DESk (c ):
Sortiere die gegebenen Paare (m, c) nach dem Wert H(m ⊕ DES−1
k (c)), wobei H
eine Hashfunktion ist. (Man kann diesen Hashwert als einen Index in ein Array
ansehen, der einem angibt, wohin man das zugehörige Nachrichten-Chiffrat-Paar
speichern muss.) Passende Paare ergeben nun eine Kollision.
2. Falls eine Kollision und somit ein slid pair gefunden wurde, setze ky = c ⊕ c0
und kx = m ⊕ DES−1
k (c ⊕ ky ). Anschließend teste den Schlüssel (k, kx , ky ) auf
verschiedenen Paaren auf Korrektheit.
Aufwand
Es werden ungefähr 264/2 Klartext-Chiffrat-Paare benötigt (hierbei entsprechen die 64
Bit natürlich der DES-Blocklänge). Dies sind etwa 64 GByte, also eine mit einem üblichen
Rechner durchaus handhabbare Datenmenge. Der im Folgenden erläuterte Aufwand beträgt insgesamt viel weniger als ein Angriff per brute force und das zuvor beschriebene
Vorgehen ist darüber hinaus auch noch parallelisierbar.
• Je Schlüsselkandidat benötigt man ≈ 232 DES-Operationen (also für alle Paare)
plus ≈ 232 Sortieraufwand (normalerweise n log(n), aber für uns sind ja nur die
Kollisionen wichtig).
• Gesamt ergibt dies ≈ 288 (= 256 · 232 , wobei die 256 für brute force gegen den
Schlüssel und die 232 für die Sortierung aufgewendet werden).
4.5 Related-Key-Attack am Beispiel LOKI89
Ein Related-Key-Attack ist eine Angriffstechnik gegen Chiffren mit einer Rundenschlüsselfunktion, d. h. einer Funktion, die aus dem eigentlichen (Haupt-)Schlüssel für jede
Runde einen Teilschlüssel erstellt, die als schwach bezeichnet werden kann. Die Praxisrelevanz dieser Angriffsform zeigt sich daran, dass damit Wired Equivalent Privacy (WEP),
welches zur Verschlüsselung von WLANs verwendet wurde, gebrochen werden konnte.
In [Bih94] wird ein Angriff auf das Verschlüsselungsverfahren LOKI89 vorgestellt. Die
Idee ist die Nutzung von Selbstähnlichkeiten im Schaltbild. Aus dem Rundenschlüssel der
vorherigen Runde wird auf immer gleiche Weise (per Shift und Hälften-Vertauschung)
ein neuer erstellt. Gegeben einen Schlüssel, kann man alle Rundenschlüssel eine Runde
zurückdrehen und erhält neue, gültige Rundenschlüssel, die aus einem anderen Schlüssel
abgeleitet werden können (related keys). Dies wird in Abbildung 4.5 veranschaulicht;
hierbei vertauscht die Funktion swap“ die linke mit der rechten Hälfte der Eingabe und
”
ROL12“ führt eine Bitrotation um 12 Positionen nach links durch.
”
26
m = (ml , mr )
k = (kl , kr )
kl
k1
ml ⊕ kl
kr
m0
ROL12
F
k0
k2
u
v
u
ROL12
F
..
.
k16
0 =k
k15
16
ROL12
F
F
y
x
k10 = k2
F
..
.
..
.
v
y
x
0
k16
swap(k)
c
F
swap(k 0 )
c0
Abbildung 4.5: LOKI89 mit Rundenschlüsseln (links) und eine Runde versetzt (rechts)
LOKI89 verwendet eine Schlüssellänge von 64 Bit und eine Blocklänge von 64 Bit. Die
ersten beiden Rundenschlüssel ergeben sich aus dem Hauptschlüssel k = (kl , kr ) per
(k1 , k2 ) = (kl , kr ).
Die restlichen Rundenschlüssel der Runden 3 bis 16 erhält man für die i-te Runde folgendermaßen:
ki = ROL12 (ki−2 ).
Alle gerade Runden haben Rundenschlüssel, die sich Bits teilen (bzw. eine gemeinsame
Vergangenheit haben), ebenso alle ungeraden.
27
Für ein slid pair bei LOKI89 gelten folgende Gleichungen (wobei die farbigen Kreise
u, v, x, y Verweise auf die Abbildung 4.5 sind). Der Schlüssel k wird, wenn man ihn nach
einer Runde der Rundenfunktion betrachtet, zu folgendem Wert:
k 0 = (kr , ROL12 (kl ))
(4.1)
Die linke und rechte Hälften des Klartextes sind nach einer Runden mit Schlüssel k
identisch zu denen nach der initialen Schlüsseladdition mit Schlüssel k 0 (also vor der
ersten Runde), nämlich:
m0 ⊕ k 0 = (mr ⊕ kr , ml ⊕ kl ⊕ F (mr ⊕ kr ⊕ kl )
| {z } |
{z
u
(4.2)
}
v
Analog gilt diese Beziehung bezüglich der Chiffrate:
c0 ⊕ swap(k 0 ) = (cr ⊕ kl ⊕F (cl ⊕ kr ⊕ kl ), cl ⊕ kr ))
| {z }
(4.3)
| {z }
y
x
Vorgehen ( Chosen Key Chosen Plaintext“-Attack)
”
Die simple, selbstähnliche Rundenschlüsselfunktion ermöglicht einen Angriff über die
Beziehung von Rundenschlüsseln mithilfe der zuvor vorgestellen Gleichungen. Es gilt
zu bemerken, dass bei einer Chosen-Key-Attack die Relationen zwischen unbekannten
Schlüsseln und nicht die Schlüssel selbst gewählt werden; letzteres wäre natürlich trivial.
1. Wähle k 0 = (kr , ROL12 (kl )). k 0 entspricht also k um eine Runde weitergeschaltet.
2. Wähle 216 zufällige Klartexte m mit gleicher rechter Hälfte (m = (∗, m)).
Wähle 216 zufällige Klartexte m0 mit derselben linken Hälfte (m0 = (m, ∗)).
(Es reichen 216 , da man die Hälfte des Klartextblocks gleich lässt (64/2 = 32) und
noch das Geburtstagsparadoxon verwendet (32/2 = 16).)
3. Erfrage 216 Chiffrate c = Enck (m) und analog c0 = Enck0 (m0 ).
4. Suche m, m0 , sodass cl = c0r gilt. Dies ist eine notwendige Voraussetzung für ein
slid pair nach (4.3).
5. Suche kr ⊕ kl , sodass
m0r ⊕ c0l = ml ⊕ F (mr ⊕ kr ⊕ kl ) ⊕ cr ⊕ F (cl ⊕ kr ⊕ kl ).
Mit den Gleichungen (4.1), (4.2) und (4.3) erhält man eine Verbindung von den
zwei Klartexten und Chiffraten des slid pairs. Addiert man diese wie oben, ist die
einzige Unbekannte kr ⊕ kl .
6. Berechne k = (kl , kr ) mittels eines LGS durch (4.1), (4.2)
28
Aufwand
Das Geburtstagsparadoxon besagt, dass mit einer signifikante Wahrscheinlichkeit ein slid
pair existiert und die Wahrscheinlichkeit für ein false positive in Schritt 4 beträgt jeweils
ungefähr 1/232 . Weitere Aufwände sind:
• 217 Verschlüsselungsanfragen (Schritt 3)
• ≈ 216 für Suche nach slid pair (Schritt 4)
• ≈ 232 für Bestimmung von kr ⊕ kl . (Dies wäre schneller mittels einer DifferenzTabelle für F durchführbar, wie wir sie im Abschnitt 6 kennen lernen werden.)
29
5 Lineare Kryptoanalyse
Bei der linearen Kryptoanalyse wird versucht, lineare Abhängigkeiten innerhalb des Verschlüsselungssystems zu finden bzw. Annäherungen daran, die vielleicht sogar nur mit
einer gewissen Wahrscheinlichkeit gelten. Diese Abhängigkeiten bzw. Approximationen
werden wir im Folgenden als lineare Approximation bezeichnen. Zuerst werden dazu
statistische lineare Beziehungen zwischen den Eingabe- und Ausgabebits der inneren
Funktionen aufgestellt, z. B. jeder S-Box. Diese Beziehungen werden kombiniert und auf
den gesamten Algorithmus ausgeweitet, um eine lineare Approximation des gesamten
Algorithmus ohne Zwischenwerte zu erhalten.
5.1 FEAL-4
Aufgrund der Bedenken bezüglich der Sicherheit von DES kam es zur Entwicklung verschiedener alternativer Kryptosysteme, welche den DES in Sicherheit und Geschwindigkeit übertreffen sollten. Eine dieser Entwicklungen ist der Fast Encryption Algorithmus (FEAL), welcher von den Japanern A. Shimizu und S. Miyaguchi bei dem japanischen Unternehmen NTT entwickelt wurde und in seiner ersten Fassung vier Verschlüsselungsrunden verwendet, warum man ihn auch FEAL-4 nennt. Zwar ist FEAL-4
wirklich schneller als der DES, allerdings wurde schon im gleichen Jahr, in dem der
Algorithmus bei der EUROCRYPT’87 öffentlich vorgestellt wurde, ein starker Angriff
veröffentlicht. Wir wollen uns nun der Beschreibung des Aufbaus von FEAL-4 widmen.
Abbildung 5.1 zeigt den Aufbau von FEAL-4, welcher wie DES eine Feistel-Struktur
aufweist und Abbildung 5.2 zeigt die F -Funktion, welche in jeder der vier Runden aufgerufen wird. Dabei verschieben die darin befindlichen S-Boxen S0 , S1 die modulo 256
addierten Eingaben zyklisch um zwei Bits nach links, genauer:
Si (A, B) = ROL2 (A + B + i mod 256).
Der 64-Bit-Schlüssel wird zu 4 Rundenschlüsseln mit jeweils 16 Bit umgewandelt, mithilfe von XOR- und Vertauschungsoperationen. Bezüglich der F -Funktion konnte man
sehr starke Abhängigkeiten zwischen den Ein- und Ausgabebits herstellen: Eine lineare
Charakteristik gibt dabei an, dass die Parität einer bestimmten Menge von Eingabebits
und Ausgabebits mit einer bestimmten Wahrscheinlichkeit gerade ist. Bei S0 (A, B) ist
die Parität der Eingabebits A[0], B[0] (hierbei gibt A[0] das erste Byte von A an) und
des Ausgabebits S[2] immer gerade, bei S1 dementsprechend ungerade. Hiermit kann
30
ml
mr
32 Bit
k1
L0
F0
F
16 Bit
B0
R0
B1
R1
B2
R2
B3
R3
k2
L1
F1
F
k3
L2
F2
F
k4
L3
F3
F
cl
cr
Abbildung 5.1: Struktur von FEAL-4
eine lineare Approximation der gesamten F -Funktion realisiert werden (die Auflistung
erfolgt von der obersten S-Box mit Eingang B[0..7] zur untersten):
F [2] = B[0] ⊕ F [8]
(5.1)
F [10] = 1 ⊕ B[0] ⊕ B[8] ⊕ k[0] ⊕ B[16] ⊕ B[24] ⊕ k[8]
(5.2)
F [18] = F [8] ⊕ B[16] ⊕ B[24] ⊕ k[8]
(5.3)
F [26] = 1 ⊕ F [16] ⊕ B[24]
(5.4)
In den Gleichungen (5.2) und (5.3) geht der Schlüssel ein, dieser ist zwar unbekannt
aber fest. Also versucht man alle Schlüssel per brute force, schaut ob die Parität konstant bleibt (somit wäre ein Schlüsselkandidat gefunden) oder nicht. Diese Charakteristik
für F können zu Charakteristiken für die ersten drei Runden erweitert werden. In Abbildung 5.3 (b) ist eine mögliche erweiterte Charakteristik samt Herleitung angegeben. Die
31
F [0..7]
8 Bit
B[0..7]
S0
k[0..7]
S1
F [8..15]
B[8..15]
S0
F [16..23]
B[16..23]
k[8..15]
F [24..31]
S1
B[24..31]
Abbildung 5.2: F -Funktion von FEAL-4
Struktur von FEAL-4 ist zum leichteren Nachvollziehen der Herleitung direkt gegenüber
gestellt.
Diese Analyse der F -Funktion kann man zu einer Analyse von mehreren Runden erweitern: Sei für gegebene Indexmengen X, Y, Z die Parität B[X] ⊕ F [Y ] ⊕ K[Z] = c, also
konstant. Verwendet man diese Gleichung in der ersten und dritten Runde und berechnet damit R1 [Y ] einmal aus den Eingängen (ml , mr ) und einmal aus den Ausgängen der
dritten Runde (L3 , R3 ), so ergibt sich:
ml [X, Y ] ⊕ mr [X] ⊕ k1 [Z] ⊕ c = ml [Y ] ⊕ R0 [X] ⊕ k1 [Z] ⊕ c
1)
= L0 [Y ] ⊕ F0 [Y ]
= R1 [Y ]
= R3 [Y ] ⊕ F2 [Y ]
2)
= R3 [Y ] ⊕ R2 [X] ⊕ k3 [Z] ⊕ c
= R3 [Y ] ⊕ L3 [X] ⊕ k3 [Z] ⊕ c.
(Hierbei stellte man bei 1) einfach R0 [X] ⊕ F0 [Y ] ⊕ k1 [Z] = c nach F0 [Y ] um und bei 2)
R2 [X] ⊕ F2 [Y ] ⊕ k3 [Z] = c nach F2 [Y ].)
Dies liefert die Gleichung für drei Runden:
ml [X, Y ] ⊕ mr [X] ⊕ R3 [Y ] ⊕ L3 [X] = k1 [Z] ⊕ k3 [Z] .
|
{z
}
Schlüssel konstant
Attacke (Known-Plaintext-Attack)
Wie zuvor besprochen kann man aufbauend von einer einfachen Analyse der Ein- und
Ausgabebits des Inneren von FEAL-4, also der F -Funktion, eine Analyse über drei Runden erstellen. Wobei man dies aufgrund der symmetrischen Struktur jeweils ausgehend
32
ml
L0
mr
F0
F
F0 [2] = B0 [0] ⊕ F0 [8]
R0
B0
ml [0] ⊕ mr [0]
L1
F1
L2
F2
L3
F3
F
F
F
R1
B1
ml [2] ⊕ R1 [2]
B2
R2
B3
R3
R3 [2] ⊕ F2 [2]
ml [8] ⊕ R1 [8]
R3 [8] ⊕ F2 [8]
B2 [0] ⊕ F2 [8]
R2 [0]
cl
cr
(a) FEAL-4-Struktur
⇒ ml [0, 2, 8] ⊕ mr [0] ⊕ R3 [2, 8] ⊕ R2 [0] = 0.
(b) Herleitung einer erweiterte Charakteristik
Abbildung 5.3: FEAL-4: Struktur und Charakteristik
vom Klartext (Verschlüsselung) oder vom Chiffretext (Entschlüsselung) betrachten kann.
Mit diesem Vorwissen ist nun eine Known-Plaintext-Attack auf den vierten (bzw. den
ersten) Rundenschlüssel möglich:
1. Verschlässle einige Klartexte mit FEAL-4.
2. Für jeden Schlüssel k4 :
a) Rechne alle entsprechenden Chiffrate zurück zum Zwischenergebnis nach der
3. Runde.
b) Falls die drei Runden Gleichung nicht bei allen Klartext- / Zwischenergebnissen gleich sein sollte, verwerfe den Schlüsselkandidat.
3. Wiederhole den Vorgang mit verschiedenen Charakteristiken, bis nur noch wenige
Kandidaten für k4 übrig sind.
4. Führe einen analogen Angriff gegen k1 durch.
5. Finde k2 und k3 mittels brute force. (Wenn k1 und k4 komplett bekannt sind, sind
diese Schlüssel auch direkt berechenbar durch die Struktur der S-Boxen.)
Aufwand
Nach dieser etwas längeren Erläuterung des FEAL-Aufbaus und des Angriffs, kommen
wir zu einer recht kurzen Aufwandsanalyse:
33
• Man benötigt ≈ 16 Klartext-Chiffrat-Paare (besser sind aber ≈ 20, damit k1 , k4
komplett durch lineare Analyse rekonstruierbar wird).
• Der Rechenaufwand beträgt ≈ 216 (dominiert durch vollständige Suche von k1 , k4 ).
5.2 DES: Lineare Analyse
Die S-Boxen bei DES sind keine linearen Funktionen. Es gibt aber Charakteristiken,
welche mit hoher Wahrscheinlichkeit gelten. Die stärkste Abweichung gibt es bei S5 mit
einer Wahrscheinlichkeit p = 12/64 = 0.1875. Damit lässt sich analog zur linearen Analyse von FEAL-4 eine Known-Plaintext-Attack auf den 4-Runden-DES durchführen; bei
Schritt 2 wird dann jeweils geprüft, ob die Statistik stimmt (d. h. ob die Gleichung im
richtigen Verhältnis ”k1 [Z] ⊕ k3 [Z] = 1ünd ”k1 [Z] ⊕ k3 [Z] = 0”liefert – die Wahrscheinlichkeit für einen der Ausgänge ist: p2 + (1 − p)2 ).
Ist eine Charakteristik für 2n + 1 Runden und dazu eine passende lineare Approximation
der F -Funktion bekannt, so lässt sich damit eine Charakteristik für 2n + 3 Runden
konstruieren (es seien X, Y, Z Indexmengen): Mit der gegebenen lineare Approximation
der Ein- und Ausgänge der F -Boxen
F [Y ] ≈ R[X]
(5.5)
L1 [Z] ⊕ R1 [Y ] ≈ L2n [Y ] ⊕ R2n [Z]
(5.6)
und der gegebenen Charakteristik
erhält man die neue Charakteristik
L0 [Y ] ⊕ R0 [X, Z] ≈ L2n+1 [X, Z] ⊕ R2n+1 [Y ].
(5.7)
(1-Runden-Charakteristiken sind trivial, da immer gilt Ri = Li+1 .)
Die Herleitung der neuen Charakteristik soll hier genauer betrachtet werden. Ausgehend
von der gegebenen Charakteristik (5.6) kommt man (mithilfe der linearen Approximation
(5.5)) zur linken Seite der neuen Charakteristik (5.7):
L1 [Z] ⊕ R1 [Y ] = R0 [Z] ⊕ R1 [Y ] = R0 [Z] ⊕ L0 [Y ] ⊕ F0 [Y ]
(5.5)
≈ R0 [Z] ⊕ L0 [Y ] ⊕ R0 [X] = R0 [X, Z] ⊕ L0 [Y ].
Dies kann man sich auch mithilfe der Abbildung 5.4 verdeutlichen. Analog kann man
zur rechten Seite von (5.7) kommen:
L2n+1 [X, Z] ⊕ R2n+1 [Y ] ≈ L2n [Y ] ⊕ R2n [Z].
Nun muss man beide Seiten nur noch mithilfe der gegebenen Charakteristik (5.6) verbinden, um zur neuen Charakteristik (5.7) zu gelangen.
34
L0
F0
L1
L2n+1
R0
F
..
F2n+1
R1
R2n+1
F
Abbildung 5.4: DES-Aufbau
Erfolgswahrscheinlichkeit
Gilt die lineare Approximation (5.5) mit Wahrscheinlichkeit p und die Charakteristik
(5.6) mit Wahrscheinlichkeit q, dann gilt die neue Charakteristik (5.7) mit Wahrscheinlichkeit
p2 q + (1 − p)2 q + 2p(1 − p)(1 − q).
Die einzelnen Summanden dieses Ausdruck wollen wir kurz erläutern:
• p2 q: Das Quadrat ergibt sich, da man die lineare Approximation (5.5) zwei Malverwendet hat, einmal für die linke und einmal für die rechte Seite, und q taucht
auf, da man die Charakteristik (5.6) zum Verbinden verwendete.
• (1 − p)2 q: Wenn beides gleich“ falsch ist, gilt natürlich die umgekehrte Parität,
”
was aber genauso nützlich ist.
• 2p(1 − p)(1 − q): Man hat hier den Faktor 2 stehen, da entweder die erste oder
zweite Approximation falsch gewesen sein können. War eine der Approximationen
falsch, ändert sich das Bit, ist aber auch die Charakteristik falsch, wird die (falsche)
Charakteristik erfüllt, gilt also.
Lemma (Piling-up Lemma): Es seien Xi mit i ∈ {1, . . . , n} unabhängige Zufallsvariablen, die den Wert 0 mit der Wahrscheinlichkeit pi und den Wert 1 mit Wahrscheinlichkeit
1 − pi annehmen. Dann gilt:
n
Y
1
1
P [X1 ⊕ · · · ⊕ Xn = 0] = + 2n−1
pi −
.
2
2
i=1
Man kann nun zu dieser Folgerung aus dem Piling-up Lemma kommen: Eine (2n + 1)Runden-Charakteristik, basierend auf n linearen Approximationen, welche jeweils mit
35
Wahrscheinlichkeit pi gelten, hat etwa folgende Wahrscheinlichkeit:
n
Y
1
1
+ 22n−1
pi −
2
2
i=1
2
.
Achtung: Diese Approximationen sind natürlich aufgrund des Aufbaus von DES und den
Zusammenhängen zwischen den einzelnen Runden und Zwischenwerten nicht wirklich
statistisch unabhängig!
Und gilt für alle linearen Approximationen die Abschätzung min(pi , 1 − pi ) > , so ist
der Vorteil einer linearen Analyse sogar vernachlässigbar in der Rundenzahl, denn es
gilt:
2n
1
1
1 1
q < + 22n−1
−
= + (1 − 2)2n .
2
2
2 |2
{z
}
vernachl. in n
Aufwand
Für die lineare Analyse eines 16-Runden-DES werden ca. 247 Klartext-Chiffrat-Paare
benötigt. Damit können 14 der 56 Schlüsselbits gefunden werden. Die verbleibenden
42 Bit des Schlüsels könen dannn durch vollständige Suche ermittelt werden. Dieser
Angriff ist somit natürlich deutlich schneller als ein bloßer Angritt per brute force gegen
den vollen Schlüssel.
36
6 Differentielle Kryptoanalyse
Bei der differentiellen Kryptoanalyse betrachtet man nicht die verschiedenen Klar- und
Chiffretexte, sondern betrachtet und tabelliert bestimmte Differenzen, meistens per XOR
ermittelt, der Klartexte, welche mit einer Wahrscheinlichkeit p zu bestimmten Differenzen der Chiffretexte führen. Für diese Wahrscheinlichkeit p muss gelten, dass sie größer
ist, als man es von einer zufälligen Permutation erwarten würde, sodass man aus den
Differenzen wichtige Informationen bezüglich des Schlüssels gewinnen kann. Diesen etwas abstrakteren Ansatz wollen wir anhand eines Beispiels für den DES im nächsten
Abschnitt veranschaulichen.
6.1 DES: Differentielle Kryptoanalyse
Die Grundidee bei der differentiellen Kryptoanalyse des DES ist, dass der Schlüssel hier
in den einzelnen Runden auschließlich per XOR eingeht und sich dadurch die Differenzen von Zwischenergebnissen nicht ändern, man diese also unabhängig vom Schlüssel
betrachten kann. Man tabelliert nun die möglichen Eingangspaare bei gegebenen Einund Ausgangsdifferenzen bezüglich der S-Boxen in einer Differenztabelle. Erhält man
bestimmte Ausgabedifferenzen der S-Boxen (also mehrere Ausgaben, die man paarweise
addieren kann), kann man in der Tabelle nachsehen, welche Differenzen wohl welche Eingabepaare benötigt und daraus, wie im Folgenden erläutert, den Schlüssel gewinnen. Die
Abbildung 6.1 verdeutlicht die Differenzbildung anhand des Signalflusses der S-Boxen
(die Differenztabelle wird mit Diff.“ abgekürzt). Hierbei erweitert die Funktion Erw. die
”
4 Eingangsbits von m1 bzw. m2 auf bekannte Weise zu 6 Bits e1 bzw. e2 und jede S-Box
korrespondiert zu 6 Schlüsselbits k. Dadurch erhalten wir als Eingang zu den S-Boxen
sin,1 = e1 ⊕ k
bzw. sin,2 = e2 ⊕ k
und die Ausgänge nennen wir dementsprechend sout,1 und sout,2 . Addiert man diese
Gleichungen zusammen, erhält man die Differenz der S-Box-Eingaben per
s0in = e0 = e1 ⊕ e2 = E(m1 ) ⊕ E(m2 ) = E(m0 ) = E(m1 ⊕ m2 )
und die Differenzen der Ausgänge der S-Boxen lauten
s0out = sout,1 ⊕ sout,2 .
Die S-Boxen lassen sich dann als Differenz-Tabellen darstellen, deren Aufbau beim Angriff auf den 1-Runden-DES etwas formaler erklärt wird. So erhält man einen vom
37
m1
m0 = m1 ⊕ m2
m2
Erw.
Erw.
⊕
e1
e2
k
sin,1 = e1 ⊕ k
Erw.
=
k
sin,2 = e2 ⊕ k
S
S
sout,1
e0 = e1 ⊕ e2
= E(m1 ) ⊕ E(m2 ) = E(m0 )
s0in = e0
Diff.
s0out = sout,1 ⊕ sout,2
sout,2
Abbildung 6.1: Differenz von Zwischenergebnissen bei DES-S-Boxen
Schlüssel k unabhängigen Signalfluss (e0 = s0in ). Da wir von einer Known-PlaintextAttack ausgehen werden, sind alle Texte bis auf sin,1 und sin,2 bekannt.
Attacke: 1-Runden-DES
Um bei gegebenen Differenzen m0 und s0out die Werte für die Eingänge der S-Boxen
sin,1 , sin,2 zu ermitteln, erstellt man zu jeder S-Box eine Differenz-Tabelle, die die möglichen Kombinationen dafür enthält. Jede Zeile i dieser 64 × 16-Tabelle entspricht einer
Eingangsdifferenz m0 = i. In der Spalte j sind alle Paare sin,1 , sin,2 eingetragen, die zu
einer Ausgangsdifferenz s0out = j führen. Ist ein Paar gefunden, das den vorgegebenen
Differenzen entspricht, so kann man k berechnen:
sin,1 = e1 ⊕ k
⇒
k = sin,1 ⊕ e1 .
So erhält man meist nur eine Menge von Schlüsseln, benutzt man aber mehrere Textpaare und nimmt die Schnittmenge der Schlüssel-Mengen, kann man diese Menge immer
stärker einengen.
Man kann den 1-Runden-Angriff leicht auf einen 2-Runden-Angriff erweitern, da die
einzelnen Runden separat angegriffen werden können. Die Ein- und Ausgangspaare (sin ,
sout ) berechnen sich zu (mr , ml ⊕ cl ) bzw. (cl , mr ⊕ cr ) für die erste und zweite Runde
wie die Abbildung 6.2 es veranschaulicht.
Das Problem bei einer Erweiterung auf 3 Runden ist, dass man in keiner Runde Einund Ausgangspaare der F -Funktion direkt berechnen kann. Die Lösung lautet nun, dass
(1)
(1)
man für die dritte Runde eine Chosen-Plaintext-Attack mit Klartexten m1 = (L0 , R0 )
38
k1
ml
mr
F
k2
F
cl
cr
Abbildung 6.2: 2-Runden-DES
L0
L1
L2
F0
F1
F2
k1
R0
k2
R1
k3
R2
F
F
F
L3
R3
Abbildung 6.3: 3-Runden-DES
(2)
(2)
und m2 = (L0 , R0 ) mit gleichbleibender rechter Hälfte benutzt. Die Abbildung 6.3
erleichtert die Zuordnung der im Folgenden verwendeten Bezeichnungen.
Die Eingänge der letzten F -Boxen als Differenzen lauten mit den gegebenen Klartexten
(1)
(2)
(1)
(2)
(1)
(1)
(2)
(2)
(2)
(2)
(2)
R20 = R2 ⊕ R2 = L3 ⊕ L3
und die Ausgänge sind
(1)
F20 = F2
(2)
⊕ F2
= R3 ⊕ L2 ⊕ R3 ⊕ L2
(1)
(1)
(1)
(1)
(1)
(2)
= R3 ⊕ L0 ⊕ F0
⊕ R3 ⊕ L0 ⊕ F0
(2)
= R3 ⊕ L0 ⊕ R3 ⊕ L0 .
Die letzte Umformung gilt, da wir gleiche rechte Hälfte beim Klartexte gewählt haben
(1)
(2)
und somit F0 ⊕ F0 = 0 erfüllt ist. Die ersten zwei Runden kann man wie zuvor
39
angreifen und die dritte durch die oben angegebenen Ein-/Ausgangs-Differenzen wie die
erste Runde.
6.1.1 Angriff gegen einen 2n-Runden-DES
Bei der Übertragung der differentiellen Kryptoanalyse auf größere Rundenzahlen, gelangt man zu einem probabilistischen Schema. Es gibt bestimmte Eingangsdifferenzen,
die sich mit hoher Wahrscheinlichkeit nach einer 2-Runden-DES-Verschlüsselung wiederfinden, Charakteristiken genannt. Man benötigt Charakteristiken, die über 2 Runden
mit großer“ Wahrscheinlichkeit stabil bleiben. Ein Beispiel hierfür enthält die Abbildung
”
6.4.
Wkt. = 1
19600000
0...0
0..0
F
0..0
00000000
1960..0
1960 . . . 0
1/234
0..0
F
1960 . . . 0
0...0
Abbildung 6.4: 2n-Runden-DES
Vorgehen (Chosen-Plaintext-Attack)
Mithilfe der Charakteristiken und der Annahme, dass diese bei passender Ein- und Ausgangsdifferenz auch wirklich erfüllt sind, kann man einen Angriff vornehmen:
1. Erfrage Chiffrate zu Klartext-Paaren mit Differenz entsprechend der Charakteristik.
2. Verwerfe Tupel mit unpassender Ausgangsdifferenz.
3. Führe 1-Runden-Angriff (wie zuvor) gegen die letzte Runde aus, mit der Annahme,
dass dort die Charakteristik erfüllt war (dies führt zu 18 Bits des letzten Rundenschlüssels). Achtung: Möglicherweise wird kein Schlüsselkandidat für alle Tupel
passen, also erfolgt ein Mehrheitsentscheid.
4. Man verwendet brute force gegen die restliche 38 Schlüsselbits.
Wahrscheinlichkeit
Die fünf rechten S-Boxen liefern bei der stabilen Charakteristik 19600000 die Differenz
0 (20 Bit), die linken drei S-Boxen liefern beliebige Werte (12 Bit). Die Wahrscheinlichkeit, dass alle 12 Bit gleich 0 sind lautet bei Gleichverteilung 2−12 . Aber mit unserer
40
Charakteristik 1/234, also ungefähr 16 Mal häufiger als bei beliebiger Charakteristik
XXX00000.
Aufwand
Die benötigte Ausgangsdifferenz tritt bei einer Rundenzahl von 2n etwa einmal pro
234n Klartext-Paaren auf. Die Wahrscheinlichkeit, dass die Charakteristik zwei Runden
überlebt lautet 234−1 , somit beträgt sie für 16 Runden natürlich 234−8 . Aufgrund von
2348 ≈ 263 ist die differentielle Kryptoanalyse damit nicht praxisrelevant für DES, da
brute force schon mit 256 möglich ist. Für Verfahren mit weniger Runden, z. B. FEAL-8,
ist sie aber absolut relevant.
6.2 Skipjack
Skipjack wurde gegen Ende der 80er bzw. Anfang der 90er von der NSA unter Geheimhaltung entwickelt, scheiterte allerdings politisch und wurde schließlich 1998 veröffentlicht.
Der Einsatzzweck war der CLIPPER-Chip zur Sprachverschlüsselung. Es wurde auch
Key Escrow betrieben, d. h. der Schlüssel wurde hinterlegt und unter Umständen Dritten zugänglich gemacht, sodass z. B. die Regierung die Kommunikation abhören konnte.
Gegen eine in der Rundenzahl reduzierte Version dieser Blockchiffre werden wir nach der
Beschreibung des Aufbaus einen Angriff erläutern. Allerdings werden wir hier nicht wie
bei der üblichen differentiellen Analyse die überdurchschnittlich auftretenden Differenzen ausnutzen, sondern die selten bzw. gar nicht möglichen Paare. Schlüssel, bei denen
solche unmöglichen Differenzen entstehen, können wir somit ausschließen und dadurch
die Menge an zu betrachtenden Schlüssel immer weiter einschränken.
Aufbau
Der Aufbau von Skipjack lässt sich grob wie folgt charakterisieren:
• Vier 16-Bit-Worte w1 , . . . , w4 (also 64 Bit) werden mit einem 80-Bit-Schlüssel in
32 Runden mit jeweils einem 32-Bit-Teilschlüssel verschlüsselt.
• Die 32 Runden haben folgenden Aufbau: 8 Mal wird Regel A angewendet (siehe
Abb. 6.5), anschließend 8 Mal Regel B (siehe Abb. 6.6) und erneut 8 Mal Regel A
und 8 Mal Regel B.
• Durch das Addieren des Rundenzählers bei den Regeln wird verhindert, dass man
z. B. 2-Runden-Charakteristiken wie bei DES verwenden kann (da sich auch bei
gleicher Eingabe die Runden unterschiedlich verhalten).
41
w1
w2
G
w3
w4
Zähler
Abbildung 6.5: Regel A
w1
G
w2
w3
w4
Zähler
Abbildung 6.6: Regel B
Der Ablauf von Skipjack kann auch in einer anderen Form dargestellt werden, wie es in
Abbildung 6.7 zu sehen ist: Hier ist das Schieberegister durch einen Signalfluss ersetzt
worden, sodass die jeweiligen Ergebnisse der Runden nur alle vier Takte direkt mit
dem Registerinhalt der ursprünglichen Darstellung übereinstimmen. Ansonsten sind die
Zwischenergebnisse gegenüber den Inhalten der Register verschoben“.
”
Die Rundenfunktion G, die bei den Regeln A und B verwendet wird, besteht aus einer Feistelchiffre mit vier Runden, bei der die jeweiligen Teilschlüssel zum Signalfluss
per XOR addiert werden. Die Rundenfunktion F von G realisiert eine bijektive 8-BitSubstitution. Das Problem ist der Übergang von Regal A zu Regel B. Normalerweise
überlebt“ ein 16-Bit-Wort nur drei Runden, hier bleibt w4 aber sieben Runden nahe”
zu unverändert. Tabelle 6.1 zeigt diesen problematischen Regelübergang anhand eines
Beispiels.
Runde (Regel)
7 (A)
8 (A)
w1
G(w1 ) ⊕ w4 ⊕ 7
9 (B)
w3
16-Bit-Worte
w2
G(w1 )
G(G(w4 ) ⊕ w4 ⊕ 7)
w3
w2
G(w
)
⊕
w4 ⊕ 8 ⊕
1
G(w1 ) ⊕ 7
Tabelle 6.1: Skipjack-Regelübergang
42
w4
w3
w2
?
G
?
- j
1
?
?
j
?
Regel A
?
j
?
?
j
?
G
2
G
3
G
4
G
?
- j
5
?
?
j
?
Regel A
?
j
?
G
6
G
7
G
PP
P
P
?
j
?
?
j
G
?
j
8
1
10
?
G
Regel B
?
- j
11
?
G
?
- j
12
?
G
?
- j
13
?
G
?
j
14
?
G
?
- j
15
Regel B
?
G
?
- j
16
?
G
?
?
?
?
Abbildung 6.7: Alternative Darstellung von Skipjack (hier nur Runde 1–16, die nächsten
16 Runden sind bis auf die Zähler identisch).
43
Differentielle Analyse
Zwei differentielle 12-Runden-Charakteristiken, die man sich anhand des Signalverlaufs
aus Abbildung 6.7 klar machen kann, lauten:
• Differenz 0X00 vor Runde 5 ⇒ Differenz XXX0 nach Runde 16
• Differenz X000 nach Runde 28 ⇒ Differenz XX0X vor Runde 17
Es kann also, wenn man beide Charakteristiken kombiniert, nie vorkommen, dass gilt:
• Eingangsdifferenz 0X00 vor Runde 5 ⇒ Ausgangsdifferenz nach Runde 28 mit
X000.
Alle solchen Rundenschlüssel wären falsch. Insgesamt gilt also: Gegeben die Zwischenergebnisse (x1 , x2 , x3 , x4 ) und (x1 ⊕y, x2 , x3 , x4 ) vor Runde 29, so ist die Ausgangsdifferenz
nach Runde 29
(G(x1 ) ⊕ G(x1 ⊕ z), y, 0, 0).
|
{z
}
:=x (siehe Angriff, 3.)
Tupel mit anderer Ausgangsdifferenz als XX00 sind für uns also irrelevant. Somit haben
wir eine differentielle Analyse der Runden 5–29 von Skipjack durchgeführt.
Angriff (Chosen-Plaintext-Attack)
Mithilfe des Wissens über bestimmte Differenzen, die nicht auftauchen können, kann
man nun den möglichen Schlüsselraum stark einengen bzw. sogar auf den korrekten
Schlüssel kommen, wenn man eine in der Rundenzahl reduzierte Version von Skipjack
betrachtet. Mit den gegebenen Differenzen für 25 Runden werden wir nun einen Angriff
auf die Runden 5–29 vorstellen:
1. Lasse 222 Mengen mit je 216 Klartexten mit paarweiser Differenz 0X00 verschlüsseln. Zum Beispiel (a, b, c, d), (a, b + z, c, d) mit z ∈ 1, . . . , 216 . (216 Klartexte
ergeben per Kombination ungefähr 231 mögliche Paare.)
2. Behalte nur Tupel mit Ausgangsdifferenz XX00 (etwa jede zweite Menge liefert
ein Paar).
3. Teste für alle Rundenschlüssel und Chiffrat-Paare (a, b, c, d), (a ⊕ x, b ⊕ y, c, d), ob
G−1 (a) ⊕ G−1 (a ⊕ x) = y
und verwerfe entsprechende Schlüssel (was möglich ist, da der Schlüssel ja in G
eingeht).
4. Die restliche 48 Bit werden per brute force ermittelt.
Aufwand
Ein Rundenschlüssel erfüllt obige Gleichung (Schritt 3) jeweils mit der (erwarteten)
21
Wahrscheinlichkeit von ungefähr 2−16 . Daraus folgt, es bleiben etwa 232 (1 − 2−16 )2
44
21
falsche Kandidaten übrig (≈ 0, 000054). Der Ausdruck 232 (1 − 2−16 )2 lässt sich erklären, als die Wahrscheinlichkeit dafür, dass für alle 232 möglichen Rundenschlüsseln
die Gleichung nicht erfüllt ist (also die Gegenwahrscheinlichkeit 1 − 2−16 gilt) und zwar
für alle 221 Paare mit Differenz XX00.
Die Aufwände für jeden einzelnen Schritt lauten:
1. 222 · 216 = 238 (Anzahl Klartexte, die erstellt werden müssen)
2. 222 · 216 = 238 (Anzahl Klartexte, die überprüft werden müssen)
3. 221 · 232 = 253 (Man nimmt 221 = 222 /2, da nur jede zweite Menge ein Paar
liefert und 232 , da alle möglichen 32-Bit-Schlüssel durchgegangen werden. Durch
trickreiches Ausnutzen der Struktur von G ist dies aber auch in ≈ 221 ·217 möglich.)
4. 248 (per brute force, aber auch hier sind intelligentere Verfahren bekannt.)
Es gilt zu bemerken, dass der vollständige 32-Runden-Skipjack in der Praxis noch ungebrochen ist.
45
7 AES (Advanced Encryption Standard)
Im Jahr 1997 gab es eine internationale Ausschreibung für einen DES-Nachfolger durch
das National Institute of Standards and Technology (NIST). Die Anforderungen an den
Nachfolger lauteten:
• Eine Blocklänge von 128 Bit
• Eine variable Schlüssellänge von 128, 192 oder 256 Bit
• Leicht implementierbar und leistungsstark, sowohl in Hardware als auch in Software
• Robust gegen alle bekannten Methoden der Kryptoanalyse, einschließlich Seitenkanälen (also Angriffe gegen eine physische Implementierung)
• Patent- und lizenzfrei
Die 15 eingereichte Kandidaten wurden einem öffentlichen Auswahlprozess (den AESKonferenzen) unterzogen und es blieben fünf Finalisten, die in Tabelle 7.1 verglichen
werden. Von den Finalisten konnte sich am Ende Rijndael durchsetzen und wurde zum
neuen Standard AES.
7.1 Aufbau und Funktionsweise
Die Blocklänge von AES beträgt wie gefordert 128 Bit (Rijndael in der Originalfassung
unterstützt auch 192 und 256 Bit) und die Schlüssellänge kann 128, 192 oder 256 Bit
betragen. Die Schlüssellänge beeinflusst die Rundenzahl und die Bestimmung der Rundenschlüssel (Key Schedule bzw. Schlüsselexpansion genannt). Die Anzahl der Runden
steigt mit der Länge des Schlüssels und es werden dementsprechend 10, 12 oder 14 Runden verwendet. Die internen Zwischenwerte, der sogennante Zustand, welcher zu Beginn
der Klartext selbst ist, und die Rundenschlüssel werden als 4-zeilige Byte-Matrix und
je nach Schlüsselgröße mit 4, 6 oder 8 Spalten repräsentiert. Im Gegensatz zur FeistelStruktur des DES findet man hier eine Art Substitutions-Permutations-Netzwerk, wobei
die Substitution“ mithilfe von linearen Funktionen erfolgt.
”
Ablauf
Jede Runde läuft in vier Schritten ab (alle Aktionen sind dabei invertierbar!) und die genannten Operationen werden auf den Zustand angewendet. Am Anfang und zum Schluss
gibt es noch eine spezielle Vor- bzw. Schlussrunde.
46
g
erk
un
erh
eit
Bem
Sic
h
Str
ukt
ur
En
twi
ckle
r
Don
Coppersmith
Feistel
(32 Runden)
hoch-sicher
komplexe
Struktur
(erschwert
Sicherheitsanalyse)
Ronald Rivest
Feistel
(32 Runden)
hinreichend
sicher
sehr einfacher
Aufbau (wenige
PseudoCodezeilen)
Rijndael
Joan Daemon,
Vincent Rijmen
SubstitutionsPermutationsNetzwerk
(10, 12 oder 14)
hinreichend
sicher
einfache
Struktur;
bestes in HW
& SW (nur 500
Zeilen C-Code)
Serpent
Ross Anderson,
Eli Biham,
Lars Knudsen
SubstitutionsPermutationsNetzwerk
(32 Runden)
hoch-sicher
(vermutlich
sicherstes)
schnellste HW,
lahmste SW
Twofish
Bruce Schneier,
Niels Ferguson,
David Wagner
hoch-sicher
komplexe
Struktur
(erschwert
Sicherheitsanalyse)
MARS
RC6
Feistel
(16 Runden)
Tabelle 7.1: NIST-Ausschreibungsfinalisten zur DES-Nachfolge
• Vorrunde: Eine Key Addition wird ausgeführt, d. h. ein bitweises XOR der Zustandsmatrix mit dem 0-tem Rundenschlüssel
Diese vier Schritte werden für jede Runde ausgeführt:
1. Byte Substitution: Dies wird auch die Rijndael-S-Box“ genannt und dieser Teil
”
sorgt für Nicht-Linearität des Algorithmus. Hierbei wird jedes Byte des Zustandes
durch ein anderes ersetzt.
a) Fasse die Bytes als Elemente von F28 auf und invertiere sie (bezüglich der
Multiplikation), falls der Wert ungleich null ist.
b) Führe eine affine Transformation y = Ax+b mit den Konstanten A ∈ {0, 1}8×8
47
und b ∈ {0, 1}8 durch, welche wie folgt definiert sind:

1
1


1

1
A=
1


0

0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1

1
1


1

1
,
0

0


0
1
 
1
1
 
 
0
 
0

b=
0 .
 
 
1
 
1
0
2. Shift Row: Man führt in diesem Schritt eine zyklische Rotation der Zeilen gegeneinander aus. Diese wird beispielhaft für 128-Bit-Datenblöcke in Abbildung 7.1
visualisiert. (Für andere Blockgrößen von Rijndael werden die Zeilen teilweise anders verschoben.)
a
b
c
d
a
b
=⇒
c
d
Abbildung 7.1: Shift-Row-Operation für 128-Bit-Datenblöcke
b wird hier vorgenommen, dabei
3. Mix Column: Eine lineare Transformation y = Ax
werden die Spalten als Vektoren in F428 aufgefasst. Jedes der 4 Bytes einer Spalte
ist also als ein Vektorelement zu sehen. Beim Entschlüsseln verwendet man die
Matrix Ab−1 .
4. Key Addition: Dieser Schritt ist wie in der Vorrunde das bitweises XOR eines
Bit-Rundenschlüssels mit der Zustandsmatrix.
• Schlussrunde: Die letzte Runde läuft wie die Runden zuvor ab, allerdings wird der
Mix-Column-Schritt ausgelassen.
Schlüsselexpansion
Die Rundenschlüssel werden vom Hauptschlüssel per Schlüsselexpansion erstellt. Der
folgenden Algorithmus beschreibt diesen Vorgang für den AES mit einer Schlüssellänge
von 128 Bit für die i-te Runde:
1. Teile Schlüssel in 32-Bit-Worte W [0], . . . , W [3] auf, also genau die Spalten der
Byte-Matrix
2. Berechne W [i] rekursiv:
i f i = 0 mod 4
then W [i] := W [i − 4] ⊕ f (W [i − 1]) ⊕ const(i)
else
W [i] := W [i − 4] ⊕ W [i − 1]
48
Wobei f eine Funktion ist (die zirkuläre Linkshifts, Substitutionen und eine XORAddition beinhaltet), und const(i) eine von i abhängige Konstante bezeichnet. Für AES
mit einer Schlüssellänge von 192 bzw. 256 Bit ersetzt man die 4“ nun natürlich durch
”
eine 6“ bzw. 8“ und bei AES-256 verwendet man folgendes für den if-then-Abchnitt:
”
”
W [8j + 4] = W [i] := W [i − 8] ⊕ ByteSub(W [i − 1]).
7.2 Schwächen und beste bekannte Angriffe
Einige bekannten Schwächen und die besten bekannten Angriffe gegen AES wollen wir
nun kurz besprechen.
Mathematische Struktur Die Verschlüsselung ist als eine geschlossene algebraische Formel über F28 darstellbar, der Algorithmus hat also eine zu starke mathematische
Struktur und ist damit theoretisch durch Lösen nicht-linearer Gleichungssysteme
angreifbar.
Seitenkanalangriffe Für eine Cache-Timing-Attack, bei welcher man mithilfe der Zeitdauer für bestimmte Berechnungen Rückschlüsse über die Beschaffenheit des Schlüssels ziehen kann, benötigt man über 200 Millionen gewählte Klartexte und eben
exakte Timing-Information. Oder es ist einem Angreifer möglich, beliebigen Code
auf den Verschlüsselungsservern ausführen.
Related-Key-Attack Eine Related-Key-Attack ist gegen AES-192 und AES-256 mit einem Aufwand von ungefähr 2100 möglich. Für rundenreduzierte AES-Varianten
mit 256 Bit Schlüssellänge sind folgende Aufwände bekannt: Gegen 9, 10 bzw. 11
Runden lauten die Aufwände 239 , 245 bzw. 270 .
Meet-in-the-Middle-/Biclique-Attack In [BKR11] wurde der erste Key-Recovery-Angriff
auf den vollen AES vorgestellt. Die effektive Schlüssellänge wurde per Meet-in-theMiddle- und Biclique-Attack um 2 Bit verkürzt. Es wird hierfür nur ein einziges
Klartext-Chiffrat-Paar benötigt.
49
8 Betriebsmodi für Blockchiffren
Die in diesem Kapitel vorgestellten Betriebsmodi erlauben die wiederholte und sichere Nutzung von Blockchiffren mit einem einzigen Schlüssel. Eine Blockchiffre erlaubt
nämlich nur die Verschlüsselung eines einzelnen Blocks mit der passender Länge. Durch
Randomisation, z. B. durch die zusätzliche Eingabe eines sogenannten Initialisierungsvektors, wird es ermöglicht, mehrere Blöcke zu verschlüsseln. Längere Nachrichten müssen
darüberhinaus aufgeteilt und (bei zu kleinen Endstücken) gepaddet werden.
8.1 ECB: Electronic Codebook Mode
Der Klartext m wird in Blöcke ‡ n bit aufgeteilt und jeder Block separat mit demselben
Schlüssel verschlüsselt, wie es in Abbildung 8.1 zu sehen ist. Dies ist der einfachste Modus
und zugleich der unsicherste.
k
k
Übertragung
m
Ek
c0
c
Ek−1
m0
Abbildung 8.1: ECB
Vorteile:
+ Keine Fehlerfortpflanzung, d. h. Übertragungsfehler (Bitflips) sind
auf die betroffenen Blöcke begrenzt
+ Verschlüsselte Datenspeicher können hier blockweise ausgelesen
bzw. beschrieben werden; einfache Suchfunktionen sind auf verschlüsselten Daten ausführbar
+ Ver- und Entschlüsselung parallelisierbar
Nachteile: − Gleiche Klartext-Blöcke führen zu gleichen Chiffrat-Blöcken (darum wird es auch Codebook“ genannt)
”
− Ein Angreifer kann Blöcke löschen, verändern, duplizieren
(Replay-Attack) und die Reihenfolge ändern (somit ungeeignet für
lange Nachrichten)
Um diesen Nachteilen abzuhelfen, sollte der Chiffreblock vom Klartextblock und von
vorherigen Klartext- bzw. Chiffreblöcken abhängen, damit sich wiederholende, identische Klartextblöcke unterschiedliche Chiffreblöcke liefern. Man kann damit dann auch
50
Einfüge-, Lösch- und Änderungs-Versuche erkennen. Ohne eine solche Abhängigkeit von
vorherigen Blöcken bleiben gleiche Blöcke gut erkennbar, was die Abbildung 8.21 verdeutlicht. Man kann darin links ein Bild von Tux, dem Linux-Maskottchen sehen, welches
trotz ECB-Verschlüsselung rechts immer noch grob als solches zu erkennen ist.
(a) TuX, der Pinguin
(b) ECB-verschlüsselter TuX
Abbildung 8.2: ECB-Verschlüsselung an einem Bild-Beispiel
8.2 CBC: Cipher Block Chaining Mode
Bei CBC wird ein n-Bit-Register verwendet, welches den vorherigen Chiffreblock zwischenspeichert. Dieses benötigt eine Anfangsbelegung, einen sogenannten Initialisierungsvektor (IV). Die Chiffreblöcke ci erhält man nun durch
c0 := Initialisierungsvektor,
ci := Ek (mi ⊕ ci−1 ).
Es hängt also jeder Chiffreblock ci von allen vorausgegangenen Blöcken und dem IV ab.
Für die Entschlüsselung gilt
c0 := Initialisierungsvektor,
mi := Ek−1 (ci ) ⊕ ci−1 .
Dieser Ver- und Entschlüsselungsvorgang ist in Abbildung 8.3 veranschaulicht.
CBC ermöglicht Selbstsynchronisation: Da man zur Entschlüsselung nur den momentanen und den vorherigen Block braucht, müssen Sender und Empfänger nicht den IV
austauschen. Der Empfänger kann irgendwas nehmen und der Sender schickt als ersten
Block Zufall. Für den nächsten Block steht nun das passende im Empfänger-Register.
1
8.2 (a) von Larry Ewingi ([email protected]) erstellt mit GIMP; 8.2 (b) von Wikimedia Commens
51
k
k
Übertragung
m
Ek
c0
c
Register
Ek−1
m0
Register
Abbildung 8.3: CBC
Vorteile:
+ Nachteile von ECB beseitigt
+ Entschlüsselung selbstsynchronisierend (da für die Berechnung eines Klartextes nur die beiden letzten Chiffrate benötigt werden)
Nachteile: − Initialisierungsvektor muss übertragen werden oder alternativ
Selbstsynchronisation nutzen ⇒ kleiner Bandbreitenverlust
− nur lesender wählerfreier Zugriff (auf z. B. Datenspeicher) über
Selbstsynchronisation, kein Schreibzugriff
− Übertragungsfehler erzeugen Bitfehler bei der Entschlüsselung des
nachfolgenden Blocks
− Verschlüsselung nicht parallelisierbar (Entschlüsselung schon)
Behandlung des letzten Blocks
Hat der letzte Block nur eine Länge von l < n und Padding ist nicht möglich (z. B. aufgrund Bandbreiten- oder Anwendungsbeschränkungen), kann man (als Sender) wie folgt
vorgehen: Verschlüssle den vorletzten Chiffreblock cr−1 , addiere diesen verschlüsselten
Wert mit dem letztem Block mr und nehme von dem Ergebnis die linken l Bits. Allerdings ist der letzte Block anfällig gegen (sinnvolle) Veränderungen, was mit Malleability
bezeichnet wird, da sich eine Veränderung im Chiffretext nicht mehr auf folgende Blöcke
auswirken kann.
Eine bessere Methode ist Ciphertext Stealing, welche in Abbildung 8.4 zu sehen ist. Hierbei wird der letzte Klartextblock mit den höherwertigen Bits des vorletzten Chiffreblocks
gepaddet und verschlüsselt. Die höherwertigen Bits des vorletzten Chiffreblocks werden
entfernt und der letzte und vorletzte Chiffreblock werden vertauscht. (Man nimmt also nur eine Reihenfolgenänderung vor, aber es werden keine zusätzlichen Padding-Bits
benötigt.)
8.3 CFB: Cipher Feedback Mode
Man verwendet bei CFB ein n-Bit-Schieberegister, dessen Inhalt um l Bit nach links
verschoben wird und welches dann mit den l Bit von c, dem letzten Chiffrat, befüllt
wird. Anschließend werden diese n Bit aus dem Schieberegister verschlüsselt, l Bit davon
52
mp−1
mp
Ek
c0p−1
mp
Ek
cp−1
cp
Abbildung 8.4: Ciphertext Stealing bei letztem Klartextblock mp
ausgewählt und auf den neuen Klartextblock addiert, der somit verschlüsselt wurde. Man
kann sich dies mithilfe der Abbildung 8.5 leicht verständlich machen.
Schiebereg.
Schiebereg.
n Bit
Ek
k
Ek
k
n Bit
l-Bit Ausw.
l-Bit Ausw.
Übertragung
l Bit
m
c0
c
m0
Abbildung 8.5: CFB
Ein Initialisierungsvektor wird benötigt (analog zu CBC), dieser kann im Klartext (z. B.
als Präambel zur eigentlichen Nachricht) übertragen werden; äquivalent ist Selbstsynchronisation nutzbar. Die Chiffretextfolge ist vom IV und allen zuvor übertragenen
Chiffraten abhängig. Die Invertierbarkeit der Blockchiffrefunktion, in vorherigen Abbildungen durch Ek−1 beim Empfänger gekennzeichnet, wird nicht benötigt, da die nBit-Schieberegister den gleichen Inhalt haben.
53
Vorteile:
+ Blocklänge l aus 1, . . . , n frei wählbar (ohne Overhead bei Kommunikation)
+ Selbstsynchronisierend (analog zu CBC); für l = 1 sogar robust
gegen Bitslips (für l > 1 nur falls Vielfaches von l verschluckt
wurde)
+ Chiffre muss nicht (effizient) invertierbar sein
Nachteile: − Mehraufwand für Ver-/Entschlüsselung von Faktor n/l, da schließlich n Bits verschlüsselt, aber nur l Bits verwendet werden. (Einzelne Runden können aber vorberechnet werden, da der Klartext
nur mit XOR eingeht.)
− Resynchronisation bei Bitflips erst nach n/l Blöcken
− Ein Angreifer kann gezielt Klartextblock-Bits ändern, erzeugt aber
in nachfolgenden Blöcken zufällige Änderungen. Der letzte Block
ist zwar wieder gefährdet, wird aber bei 8-Bit-CFB (l = 8) meist
für die Prüfsumme verwendet, ist also nicht sinnvoll änderbar.
Ist es einem Angreifer möglich ein Chiffretext zu einem anderen umzuformen, sodass
deren Klartexte in Relation zueinander stehen, spricht man von Malleability (siehe auch
Abschnitt 9).
Bei Übertragungsfehlern wird solange falsch dechiffriert, bis der Fehler aus dem Schieberegister hinausgeschoben wird. Bei l übertragenen Zeichen und einer Schieberegisterlänge
von n lautet die Anzahl falsch dechiffrierter Zeichen 1 + n/l.
8.4 OFB: Output Feedback Mode
Bei OFB wird ähnlich wie bei CFB vorgegangen, allerdings nimmt man nicht l Bit
des Chiffrats, die man dann dem Schieberegister zuführt, sondern die l-Bit-Auswahl der
Verschlüsselung des Schieberegisterinhalts, wie dies in Abbildung 8.6 zu sehen ist. Ein
Initialisierungsvektor wird benötigt, dieser kann im Klartext übertragen werden.
Vorteile:
+ Schlüsselstrom unabhängig von Nachrichtenstrom vorberechenbar
+ Keine Fehlerfortpflanzung bei Bitflips
+ Chiffre muss nicht (effizient) invertierbar sein
Nachteile: − Lineare Verschlüsselung (XOR) verwendet, d. h. ein Angreifer
kann gezielt Klartext-Bits kippen. (Es gibt keine NachrichtenVerkettung wie beim CBC, CFB, also ist die Erkennung einer
Manipulation genauso problematisch wie bei ECB.)
− Wiederverwendung“ des Initialvektors ist besonders kritisch, es
”
gilt dann c ⊕ c0 = m ⊕ m0 , man kann nun den Klartext erkennen
wie bei Vigènere.
− Keinerlei Resynchronisation, wenn etwas verloren geht (ECB, CBC
und CFB resynchronisieren, wenn ganze Blöcke verloren gehen).
54
Schiebereg.
Schiebereg.
n Bit
Ek
Ek
l-Bit Ausw.
l-Bit Ausw.
k
k
n Bit
Übertragung
l Bit
c0
c
m
m0
Abbildung 8.6: OFB
8.5 CTR: Counter Mode
Ein Initialisierungsvektor wird benötigt, welcher im Klartext übertragen werden kann.
Dieser IV, mit addiertem bzw. angehängtem Counter, wird verschlüsselt und auf den
Klartext addiert. Anschließend wird der Counter erhöht und wieder mit dem IV verschlüsselt und auf den nächsten Klartextblock addiert usw., wie es Abbildung 8.7 zeigt.
IV
IV
Counter
Counter
k
Ek
Ek
k
Übertragung
m
c0
c
m
Abbildung 8.7: CTR
Vorteile:
+
+
+
+
+
Schlüsselstrom unabhängig von Nachrichtenstrom vorberechenbar
Ver- & Entschlüsselung parallelisierbar
Keine Fehlerfortpflanzung bei Bitflips
Chiffre muss nicht (effizient) invertierbar sein
Verschlüsselte Datenspeicher können blockweise bearbeitet werden
Im Wesentlichen hat man also die Vorteile von ECB und OFB. Außerdem hat man auch
die gleichen Nachteile wie bei OFB.
55
8.6 Probleme bei schwachen Verfahren
Bei dem OFB-Verfahren ist die Schlüsselwahl zu beachten. Denn mit einem schwachem Schlüssel k kann die Blockchiffre Ek eine Involution bilden (d. h. eine selbstinverse Permutation) und erzeugt dann einen Schlüsselstrom mit einer Periode von 2n.
Dies ermöglicht einen einfachen Known-Plaintext-Angriff, wenn 2n Bit vom Klartext
bekannt sind bzw. es entspricht sogar einer Vigenère-Verschlüsselung.
Bei dem CBC-Modus ist eine Birthday-Attack aufgrund gleicher Chiffrat-Blöcke möglich.
Bei gleichen Chiffrate-Blöcken ci = cj gilt nämlich:
Ek (mi ⊕ ci−1 ) = Ek (mj ⊕ cj−1 ).
Und daraus folgt:
mi ⊕ mj = ci−1 ⊕ cj−1 .
Somit erhält man aufeinander addierte Klartextblöcke mi ⊕ mj . Dies tritt bei einer
Blocklänge von n ab einer Klartextlänge von ungefähr 2n/2 mit signifikanter Wahrscheinlichkeit auf. Darum sollte man Schlüssel bei großen Datenmengen häufig wechseln.
8.7 Vergleich
Ein Vergleich über einige Betriebsmodi findet sich in Tabelle 8.1.
56
–
CBC
m>n
IV bzw.
autom.
nach einem
Block
CFB
Zeichenstrom
(jedes
Zeichen
einzeln
bearbeitet)
IV bzw.
autom.
nach einem
Block
OFB
m > n,
Fehlererweiterung
unerwünscht
CTR
m > n,
Fehlererweiterung
unerwünscht
IV
IV
Acc
ess
om
Ra
nd
Bit
-Sli
p
r
hle
Bit
-Fe
eite
run
g
Feh
le
rer
w
io n
Syn
chr
oni
sat
g
ndu
n
Ver
we
Nachricht m
¡ Block n
ECB
Nein
1 Block
zerstört
Keine Synchronisation
mehr
rw
Ja
1 Block
zerstört, 1 Bit
im nächsten
Block invertiert
mehr
r
Ja
Nächsten
1 + n/l Zeichen
gestört
Nur für l = 1
nach n Bit
Resynchronisation
r
Nein
1 Bit invertiert
mehr
–
Nein
1 Block
zerstört
mehr
rw
Tabelle 8.1: Betriebsmodi im Vergleich
57
9 Formale Sicherheitsbegriffe
Bei den verwendeten formalen Sicherheitsbegriffen wird ein Paar aus zwei Spielen definiert, mit einem Angreifer A und einem Herausforderer Eb , deren Ergebnis jeweils eine
binäre Zufallsvariable ist. Die Chiffre ist sicher im Sinne der Definition, wenn kein Angreifer bewirken kann, dass die beiden Spielergebnisse statistisch signifikant voneinander
abweichen. Die Mächtigkeit des Angreifers wird dabei durch zwei Orakel O und O0 modelliert, auf welche der Angreifer vor bzw. während des Spiels zugreifen kann. So kann
ein Angreifer ein Verschlüsselungsorakel nutzen, um Klartexte zu verschlüsseln, ohne
dass der Angreifer dabei Zugriff auf den geheimen Schlüssel hat.
Angriffe
• Chosen-Plaintext Attacks (CPA): Bei diesem Angriff sind O und O0 reine Verschlüsselungsorakel.
• Chosen-Ciphertext Attacks (CCA1): Hier ist O ein Ver- & Entschlüsselungsorakel
und O0 ist nur ein Verschlüsselungsorakel.
• Adaptive Chosen-Ciphertext Attacks (CCA2): Hier sind O und O0 jeweils Ver- und
Entschlüsselungsorakel. (O0 weigert sich hierbei allerdings trivialerweise, ChallengeChiffrate zu entschlüsseln.)
Schutzziele
Die folgenden Veranschaulichungen sind abgeleitet aus [BDPR98].
• Indistinguishability (IND): Ein Angreifer A kann keine zwei Klartexte m0 , m1 finden, deren Chiffrate er dem jeweils zugehörigen Klartext zuordnen könnte. In dem
Spiel, welches in Abbildung 9.1 zu sehen ist, gibt der Angreifer A die zwei Klartexte an den Herausforderer Eb , welcher mit einem zufällig ausgewähltem b ∈ {0, 1}
entscheidet, welcher der beiden Texte verschlüsselt und zurückgegeben wird. Der
Angreifer gibt bb ∈ {0, 1} aus, mit welchem er angibt, ob seiner Meinung nach m0
oder m1 verschlüsselt wurde. Sind bb und b identisch, so war der Angriff erfolgreich.
• Real or Random (ROR): Ein Angreifer A kann keinen Klartext m finden, dessen
Chiffrat er von verschlüsseltem Zufall unterscheiden könnte. In Abbildung 9.2 wird
R
dies veranschaulicht, hierbei wird mit x ←
− Klartextraum ausgedrückt, dass man
aus dem Klartextraum per Zufall ein Element auswählt.
• Non-Malleability (NM): Ein Angreifer A kann Chiffrate nicht so umformen, dass
die Fälschung“ eine sinnvolle Relation R zum Original“ erfüllt. (Malleability
”
”
58
lässt sich übersetzen zu Formbarkeit“, Geschmeidigkeit“.) Der Spielablauf ist
”
”
in Abbildung 9.3 zu sehen. Es geht bei diesem Angriff nicht darum, etwas über
den Klartext x zu erfahren, sondern einen Chiffrat-Vektor ~y auszugeben, dessen
Entschlüsselung ~x eine (bedeutende) Relation R zum Klartext x hat, geschrieben
als R(x, ~x). Zuerst gibt der Angreifer hierbei eine Klartextverteilung M aus. Daraus werden zwei Nachrichten x0 , x1 zufällig ausgewählt und x0 wird für ihn zu y
verschlüsselt und zurückgegeben. Der Angreifer gibt nun die Beschreibung einer
Relation R und einen Vektor ~y aus. Wobei y ∈
/ ~y gegeben und R effizient prüfbar
ist. Der Vektor ~y wird nun entschlüsselt zu ~x. Der Angreifer ist erfolgreich, sofern
die Relation R(x, ~x) erfüllt ist und die Wahrscheinlichkeit dafür signifikant größer
ist als diejenige, für die R(x1 , ~x) mit einem zufällig gewähltem x1 aus M gilt.
Warum so eine auf den ersten Blick seltsame Definition sinnvoll ist, kann man sich
verständlich machen, wenn man als Beispiel eine Auktion mit zwei Teilnehmern
betrachtet: Der ehrliche Teilnehmer gibt ein Gebot g verschlüsselte als Ek (g) ab
und der unehrliche zweite Teilnehmer liest dies. Könnte er nun, ohne es zu entschlüsseln, daraus Ek (g + 1) machen, würde er zwar nicht wissen, was er bietet,
aber immer gewinnen.
m0 ,
A
Eb
m1
y = EncK (mb )
y
h
b
b
i
Ergebnis: bb
Abbildung 9.1: Indistinguishability (IND)
A
m
Eb
R
x←
− Klartextraum
(
y
h
b
b
y=
EncK (m)
EncK (x)
falls b = 0
falls b = 1
i
Ergebnis: bb
Abbildung 9.2: Real or Random (ROR)
59
A
(Klarte
Eb
M
xtverte
il
ung)
y
R
x0 , x1 ←
−M
y = Enck (x0 )
R, ~y
~x = Deck (~y )
[Ergebnis: y ∈
/ ~y ∧ ⊥ ∈
/ ~x ∧ R(xb , ~x)]
Abbildung 9.3: Non-Malleability (NM)
9.1 Beziehungen zwischen den Begriffen
Die Beziehungen zwischen den verschiedenen Sicherheitsbegriffen nach [BDPR98] sind in
Abbildung 9.4 zu finden. Hierbei bedeuten die gestrichelten und durchgestrichene Pfeile
natürlich, dass die jeweiligen Begriffe nicht auseinander folgen, während die normalen
Pfeile die folgt aus“-Beziehung darstellen sollen.
”
NM-cpa
NM-cca1
NM-cca2
IND-cpa
IND-cca1
IND-cca2
RoR-cpa
RoR-cca1
RoR-cca2
Abbildung 9.4: Beziehung zwischen den Sicherheitsbegriffen
Im Folgenden sollen einige Beziehungen erläutert werden und es stehe atk“ kurz für
”
CPA“, CCA1“ und CCA2“.
”
”
”
• IND-atk ⇒ RoR-atk: Kann man zwei selbstgewählte Klartexte nicht unterscheiden,
dann auch nicht ein gewählter und ein zufälliger Text.
• RoR-atk ⇒ IND-atk: RoR-Sicherheit bedeutet, dass kein Angreifer einen Klartext
m oder m0 findet, sodass er Ek (m) oder Ek (m0 ) von verschlüsseltem Zufall unterscheiden kann. Aus der Transitivität der Ununterscheidbarkeits-Relation folgt die
Ununterscheidbarkeit von Ek (m) und Ek (m0 ).
60
• IND-CCA1 ; NM-CPA: Ein IND-CCA1-sicheres Schema bleibt IND-CCA1-sicher,
wenn man an jedes Chiffrat c ein Chiffrat c0 des bitweise invertierten Klartexts
anhängt. Ein NM-Angreifer kann dann den Inhalt von Chiffraten bitweise invertieren, indem er die Reihenfolge von c und c0 vertauscht.
• NM-CPA ; IND-CCA1 : Ein NM-CPA-sicheres Schema kann oBdA so umgebaut werden, dass gilt Ek (Ek (k)) = 0 . . . 0. Das Schema bleibt CPA-, nicht jedoch
CCA1-sicher (O von CCA1 gibt k frei, da es entschlüsseln kann).
Achtung: Ein Schema, für welches Ek (k) = 0 . . . 0 gilt, ist nicht NM-CPA-sicher.
Ein Angreifer kann die Relation R so wählen, dass R(x, a, b) erfüllt ist, genau dann,
wenn Da (b) = x gilt. Dann kann er bei gegebener Challenge y = Ek (x) dazu das
Chiffrat-Tupel ~y = (0 . . . 0, z) mit z = Ek (y) wählen und die Relation ist erfüllt.
Das Ergebnis: R(Dk (y), Dk (0 . . . 0), Dk (z)) = R(x, k, y) ist erfüllt, da Dk (y) = x
gilt.
• IND-CCA2 ⇒ NM-CCA2 : Ein Angreifer, der das NM-CCA2-Spiel gewinnt, kann
Chiffrate so umformen, dass er die Relation zwischen den entsprechenden Klartexten kennt. Damit kann er die Challenge im IND-CCA2-Spiel entsprechend umformen, entschlüsseln lassen und prüfen, ob der erhaltene Klartext in Relation zu m1
oder m2 steht.
• NM-atk ⇒ IND-atk: Ein Angreifer, der Klartexte wiedererkennen kann, kann zum
wiedererkannten Klartext mi einen Klartext m0 wählen (und verschlüsseln lassen),
sodass mi und m0 in einer vom Angreifer gewählten Relation stehen.
Beobachtungen
Diese formalen Sicherheitsbegriffe und deren Beziehungen untereinander lassen uns zu
folgenden negativen (−) und positiven (+) Beobachtungen kommen:
− Volldeterministische Verfahren (ECB) erfüllen keinen der Begriffe
− Selbstsynchronisierende (CBC, CFB) und lineare (OFB, CTR) Verfahren erfüllen
keinen NM-Begriff
+ Ideal Cipher im CBC-Mode ist IND-CPA-sicher (sogar IND-CCA1). Analog dazu
auch jede Chiffre, die kein Angreifer ohne Schlüsselzugriff von einer Ideal Cipher
unterscheiden kann.
+ Um NM-CPA-Sicherheit zu erreichen (sogar IND-CCA2), wird ein IND-CPAsicheres Verfahren mit einem Authentifikationsverfahren (MAC, siehe Abschnitt
11.1) kombiniert. Dies führt zur sogenannten Authenticated Encryption (z. B. den
Modi CCM, CWC, OCB, EAX oder GCM).
61
10 Hashfunktionen
10.1 Definition und Eigenschaften
Definition 10.1.1: (Hashfunktion): Eine Hashfunktion H ist eine Abbildung, die einen
beliebig großen Eingabewert auf eine kleine Ausgabe, den sogenannten Hashwert, abbildet. Formaler lässt sich dies ausdrücken per:
H : {0, 1}∗ → {0, 1}n
bzw. Hk : {0, 1}∗ → {0, 1}|k| (keyed hash-function).
Aus kryptographischer Sicht sollte eine Hashfunktion H folgende Eigenschaften erfüllen:
• Urbildresistenz: Gegeben ein Hashwert h, ist es nicht praktikabel, ein Urbild m zu
finden, d. h. H(m) = h.
formal: Für jeden effizienten Angreifer A (mit Laufzeit polynomiell in der Eingabelänge) soll die folgende Wahrscheinlichkeit vernachlässigbar in einem Sicherheitsparameter λ sein:
Pr A(Hk (m), k) → m0 mit Hk (m0 y) = Hk (m)
Dabei ist (k, m) gleichverteilt zufällig aus {0, 1}λ × {0, 1}p(λ) mit einem beliebigen
aber festen Polynom p ∈ Z[X].
• Kollisionsresistenz: Es ist nicht praktikabel, zwei verschiedene Urbilder m, m0 mit
demselben Hashwert h = H(m) = H(m0 ) zu finden.
formal: Für jeden effizienten Angreifer A (mit Laufzeit polynomiell in der Eingabelänge) soll die folgende Wahrscheinlichkeit vernachlässigbar in einem Sicherheitsparameter λ sein:
Pr A(k) → (m, m0 ) mit Hk (m) = Hk (m0 )
Dabei ist k gleichverteilt zufällig aus {0, 1}λ .
Random Oracle
Ein Random Oracle (RO) ist eine (Über-)Idealisierung einer Hashfunktion und jedem
Urbild m ∈ {0, 1}∗ ist ein vollkommen zufälliger Hashwert h ∈ {0, 1}n zugeordnet (n
ist ein Sicherheitsparameter) und per Orakelzugriff kann jede Maschine im Modell die
entsprechende Funktion H auswerten.
Folgendes gilt es noch anzumerken:
62
• Es gibt (konstruierte) Protokolle, die im Random-Oracle-Modell sicher sind, aber
für keine bekannte Hashfunktion sicher sind.
• Das Random-Oracle- und Ideal-Cipher-Modell sind äquivalent. Mittels eines FeistelNetzwerks lässt sich aus einem RO eine IC konstruieren. Umgekehrt kann mittels
eines Merkle-Damgard-Schemas ein RO aus einer IC konstruiert werden. Beides
wird im folgenden Abschnitt behandelt.
10.2 Merkle-Damgard- & Feistel-Konstruktion
Es soll nun erläutert werden, wie man aus einer Ideal Cipher ein Random Oracle konstruiert und umgekehrt.
Ideal Cipher ⇒ Random Oracle“
”
Die Abbildung 10.1 zeigt wie man durch Verkettung einer Ideal Cipher mithilfe eines Initialisierungsvektors ein Random Oracle per sogenannter Merkle-Damgard-Konstruktion
erhält. Hierbei wird die eigentliche Nachricht m in kleinere Blöcke m1 , . . . , mn unterteilt
und den einzelnen Ideal Ciphern übergeben.
IV
m1
m2
IC
IC
mn
...
IC
H(m1 ||m2 || . . . ||mn )
Abbildung 10.1: Ideal Cipher ⇒ Random Oracle
Es gilt allerdings zu beachten, dass eine einfache Merkle-Damgard-Konstruktion noch
nicht genügt! Das Problem: Gegeben den Hashwert h einer unbekannten Nachricht m,
kann ein Angreifer zu jeder Nachricht m0 den Hashwert H(m||m0 ) berechnen, indem
einfach an die obige Pipeline-Konstruktion weitere Stufen angebaut werden und m0 aufgeteilt und eingegeben wird. Hierbei benutzt man H(m) als internen Hashwert zur Berechnung von H(m||m0 ). Dafür gibt es aber auch Lösungen:
• Wide-Pipe-Konstruktion nach [Luc04]: Es wird bei dieser Konstruktion intern mit
mehr Bits gearbeitet, als ausgegeben werden. Dies verhindert das Auffinden von
Kollisionen bei internen Hashwerten (also den Zwischenhashwerten). Siehe Abbildung 10.2 (a).
• Fast-Wide-Pipe-Konstruktion nach [NP10]: Die Hälfte der erweiterten interne Bits
werden auf den Ausgang des nachfolgenden ICs addiert, anstatt sie wie bei der
Wide-Pipe-Konstruktion an dessen Eingang zu legen. Siehe Abbildung 10.2 (b).
Random Oracle ⇒ Ideal Cipher“
”
Zur Konstruktion einer Ideal Cipher aus einem Random Oracle benötigt man laut
[HKT11] eine Feistel-Struktur mit 14 Runden, wie sie in Abbildung 10.3 angedeutet
63
IV1
m1
m2
...
mn
IC
IC
...
IC
H(m1 || . . . ||mn )
IV2
(a) Wide-Pipe-Konstruktion
IV1
m1
m2
...
mn
IC
IC
...
IC
H(m1 || . . . ||mn )
IV2
(b) Fast-Wide-Pipe-Konstruktion
Abbildung 10.2: Konstruktion eines Random Oracles aus einem Ideal Cipher
ist. Hierbei bezeichnet Ri den rechten Teil des internen Zustands nach der i-ten Runde
und k ist der Schlüssel, der der Hashfunktion Hi zur Verfügung gestellt wird. Unbekannt
ist allerdings, ob auch schon weniger Runden ausreichend sind.
k
H(i||k||Ri )
Hi
Ri
Abbildung 10.3: Random Oracle ⇒ Ideal Cipher
10.3 Äquivalenz von Krypto-Primitiven
Es wird in [CPS08] bemerkt, dass man, um Beweise für die Sicherheit eines KryptoSystems zu konstruieren meist zwei mögliche Ansätze verfolgt. Entweder verwendet man
bestimmte rechnerische Probleme, wie z. B. die Faktorisierung großer Zahlen, die als
schwer lösbar gelten (welche man, könnte man das Krypto-System brechen, dann ebenfalls lösen kann, was ja gerade als schwer machbar gilt), oder man nutzt der Effizienz
zuliebe ein idealisiertes Modell der Wirklichkeit, wie die bereits zuvor erwähnten IdealCipher- und Random-Oracle-Modelle. Die Äquivalenz solcher Modelle oder kryptogra-
64
phischer Konstruktionen, die wir hier Primitive nennen wollen, ist bedauerlicherweise
nicht unbedingt leicht zu zeigen, sodass manche Beweise schwer vergleichbar sind. Am
Beispiel der zuvor schon beschriebenen Gleichheit von Ideal Cipher und Random Oracle
wollen wir die Schwierigkeit von Äquivalenzbeweisen bezüglich bestimmter Definition
aufzeigen.
Eine erste Definition
Eine naive“ Definition für die Gleichheit von Primitiven, welche, wie wir bald sehen
”
werden, unzureichend ist, lautet:
Definition 10.3.1: (Indistinguishability): Eine Primitive Y kann aus X realisiert werden, wenn es eine Turingmaschine M gibt, sodass die Ein-Ausgabe-Verteilung von MX
ununterscheidbar ist von der Ein-Ausgabe-Verteilung von Y. Etwas formaler formuliert
kann man sagen, dass für jeden Unterscheider D gilt:
X
Pr[DM = 1] ≈ Pr[DY = 1].
Indistinguishability reicht nicht, da – sofern der Angreifer z. B. auf innere Rundenfunktionen zugreifen kann – dieser ein anderes Interface hat (eben die Ein- und Ausgänge
der inneren Funktionen). Solche Zugriffe auf die Innereien“ erlaubt das Random-Oracle”
Modell nicht.
Angriff gegen 5-Runden-Feistel
Nach dieser Definition genügt ein 4-Runden-Feistel-Netzwerk, um aus einem Random
Oracle eine Ideal Cipher zu implementieren. Es existiert aber ein Angriff auf die 5Runden-Feistel, welcher in [CPS08] beschrieben ist. Die Idee dieses Angriffes ist, dass eine
Eigenschaft der 5-Runden-Struktur aufgezeigt wird, die bei einer zufälligen Permutation
nicht wirklich zu finden wäre. Die im Folgenden verwendeten Bezeichnungen sind in
Abbildung 10.4 übersichtlich dargestellt. Es seien Y und Y 0 beliebige Werte, die die
Eingabe zu F3 bilden. Sei Z ein weiterer beliebiger Wert, welcher die Eingabe für F4
darstellen soll. Wir setzen Z 0 = F3 (Y ) ⊕ F3 (Y 0 ) ⊕ Z und damit gilt
X = F3 (Y ) ⊕ Z = F3 (Y 0 ) ⊕ Z 0
0
0
0
X = F3 (Y ) ⊕ Z = F3 (Y ) ⊕ Z .
(10.1)
(10.2)
Mit X, X 0 , Y und Y 0 werden nun vier Paare (Xi , Yi ) wie folgt gebildet:
(X0 , Y0 ) = (X, Y 0 ),
(X1 , Y1 ) = (X 0 , Y ),
(X2 , Y2 ) = (X 0 , Y 0 ),
(X4 , Y4 ) = (X, Y 0 ).
Die dazugehörigen zwei Hälften der vier Klartexte seien mit Li und Ri bezeichnet. Wir
erhalten nun
R0 = Y0 ⊕ F2 (X0 ) = Y ⊕ F2 (X)
R1 = Y1 ⊕ F2 (X1 ) = Y ⊕ F2 (X 0 )
R2 = Y2 ⊕ F2 (X2 ) = Y 0 ⊕ F2 (X 0 )
R3 = Y3 ⊕ F2 (X3 ) = Y 0 ⊕ F2 (X).
65
L
R
F1
X
F2
Y
F3
Z
F4
S
F5
T
S
Abbildung 10.4: 5-Runden-Feistelkonstruktion
Mit den dazugehörigen Eingabewerten Z0 , . . . , Z3 für F4 , erhält man mit den Gleichungen
(10.1) und (10.2) diese Zusammenhänge:
Z0 = X0 ⊕ F3 (Y0 ) = X ⊕ F3 (Y ) = Z
Z1 = X1 ⊕ F3 (Y1 ) = X 0 ⊕ F3 (Y ) = Z 0
Z2 = X2 ⊕ F3 (Y2 ) = X 0 ⊕ F3 (Y 0 ) = Z
Z3 = X3 ⊕ F3 (Y3 ) = X ⊕ F3 (Y 0 ) = Z 0 .
Mit Si und Ti seien die Chiffrehälften bezeichnet. Die linken Chiffrehälften können wir
nun ausdrücken als
S0 = Y0 ⊕ F4 (Z0 ) = Y ⊕ F4 (Z)
S1 = Y1 ⊕ F4 (Z1 ) = Y ⊕ F4 (Z 0 )
S2 = Y2 ⊕ F4 (Z2 ) = Y 0 ⊕ F4 (Z)
S3 = Y3 ⊕ F4 (Z3 ) = Y 0 ⊕ F4 (Z 0 ).
Nach dieser etwas mühsamen Beschreibung erhalten wir folgende Beziehungen:
R0 ⊕ R1 ⊕ R2 ⊕ R3 = 0 = S0 ⊕ S1 ⊕ S2 ⊕ S3 .
Damit haben wir vier Klartext-Chiffrat-Paare gefunden, sodass die Addition der rechten
Klartexthälften, ebenso wie die Addition der linken Chiffrathälften null ergibt. Solch
66
eine Eigenschaft kann man bei einer wirklich zufälligen Permutation höchstens mit vernachlässigbarer Wahrscheinlichkeit finden (bei polynomial beschränkter Anfragezahl),
womit gezeigt wurde, dass die 5-Runden-Feistelkonstruktion nicht ausreichen kann.
Eine bessere Definition
Die richtige“ Definition hingegen ist nun:
”
Definition 10.3.2: (Indifferentiability): Eine Primitive Y kann aus X realisiert werden, wenn es eine Turingmaschine M und einen Simulator S gibt, sodass die EinAusgabe-Verteilung von (MX , X) ununterscheidbar ist von der Ein-Ausgabe-Verteilung
von (Y, S Y ). Für jeden Unterscheider D gilt also:
Pr[DM
X ,X
Y
= 1] ≈ Pr[DY,S = 1].
Der Simulator kann nun den Zugriff auf das Innere“ simulieren. Der Unterscheider soll
”
nun nicht erkennen, ob eine Permutation vorliegt und die Rundenfunktionen passend
dazu simuliert werden (IC zu RO) oder ob (zufällig gewählte) Rundenfunktionen zusammengesetzt wurden (RO zu IC).
10.4 Aufbau von SHA-1
Der SHA, was für Secure Hash Algorithm“ steht, wurde von dem National Institute of
”
Standards and Technology (NIST) zusammen mit der National Security Agency (NSA)
entwickelt und 1994 veröffentlicht. Von diesem Algorithmus gibt es mehrere Versionen
und wir werden uns mit SHA-1 beschäftigen, welcher sich folgendermaßen charakterisieren lässt und in Abbildung 10.5 zu sehen ist:
• Der Hash-Wert beträgt bei dieser Variante 160 Bit (intern wird aber mit 512 Bit
gerechnet) und die Initial- bzw. Zwischenzustände werden in fünf 32-Bit-Worten
A, . . . , E gespeichert.
• Es gibt 80 Runden, jeweils 20 mit einer von vier verschiedenen Funktionen fj , welche Verknüpfungen von logischen Operatoren sind und einer von vier Konstanten
cj . Für die ersten 20 Runden verwendet man f1 und c1 , für die nächsten 20 Runden
f2 und c2 , etc. Die verwendeten Funktionen lauten für die i-te Runde:


(B ∧ C) ∨ (¬B ∧ D)




B ⊕ C ⊕ D
(für
(für
fj (B, C, D) =

(B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D) (für




B ⊕ C ⊕ D
(für
0 ≤ i ≤ 19)
20 ≤ i ≤ 39)
40 ≤ i ≤ 59)
60 ≤ i ≤ 79)
• Ein Nachrichtenblock von 512 Bit wird zu 80 32-Bit-Worten expandiert. Die ersten
16 Worte w0 , . . . , w15 sind die ursprüngliche Nachricht, jedes weitere wj wird als
67
160
512
32
B
A
C
D
E
D
E
D
E
D
E
20 Runden mit f 1
C
B
A
20 Runden mit f 2
C
B
A
20 Runden mit f 3
C
B
A
20 Runden mit f 4
+
+
+
+
+
160
Abbildung 10.5: SHA-1: Schematischer Aufbau, die Additionen werden dabei mod 232
durchgeführt
ein zyklischer Linksshift um eine Stelle (bezeichnet als ROL1 ) von jeweils vier
vorangegangenen, aufaddierten Nachrichten berechnet:
ROL1 (wj−16 ⊕ wj−14 ⊕ wj−8 ⊕ wj−3 )
(für 16 ≤ j ≤ 79).
• In Runde i fließt das Wort wi , die Konstante cj , die Funktion fj und die momentanen Zwischenvariablen Ai , . . . , Ei mit ein und bilden die neuen Zwischenvariablen
Ai+1 , . . . , Ei+1 wie folgt:
Ai+1 = ROL5 (Ai ) + fj (i, Bi , Ci , Di ) + Ei + cj + wi ,
Bi+1 = Ai ,
Ci+1 = ROL30 (Bi ),
Di+1 = Ci ,
Ei+1 = Di .
Dies ist in Abbildung 10.6 veranschaulicht.
Nach Ausführung aller Runden, erhält man nun den Hashwert, indem man die Variablen
A bis E aneinander hängt, also A||B||C||D||E. SHA-1 wird mittlerweile seinem Namen
allerdings nicht mehr ganz gerecht, da man einige starke Angriffe gefunden hat, siehe
z. B. [WYY05]. In der Praxis ist SHA-1 allerdings (noch) ungebrochen.
68
A
B
C
D
E
fj
+
+
ROL5
ROL30
A
B
C
D
+
wi
+
ci
E
Abbildung 10.6: SHA-1: Rundenfunktion, die Additionen werden mod 232 durchgeführt
10.5 Angriffsansätze gegen Hashfunktionen
Einige Angriffsansätze gegen Hashfunktionen werden im Folgenden kurz aufgelistet.
Meet-in-the-Middle Man kann eine Urbildsuche mithilfe der Meet-in-the-Middle-Methode
gegen eine Merkle-Damgard-Konstruktion ausführen. Dabei muss der Angreifer die
verwendete Kompressionsfunktion invertieren können.
1. Halbiere eine Nachricht in eine linke und eine rechte Hälfte. Verändere in der
linken Hälfte n/2 Stellen, wobei n die Hashwertlänge ist, sodass man 2n/2
verschiedene linke Nachrichtenhälften erhält.
2. Berechne für alle linken Nachrichtenhälften den Teil-Hashwert, tabelliere dieses Zwischenergebnisse (Vorwärtsschritt).
3. Sortiere die Tabelle.
4. Rechne für jede ebenso veränderte rechte Nachrichtenhälfte vom gegebenen
Bild zum Zwischenergebnis zurück und suche dieses in der Tabelle (Rückwärtsschritt). Ein Treffer bedeutet, dass man eine Kollision gefunden hat.
Fixpunkte Man nutzt Fixpunkte der Kompressionsfunktion f aus, um Kollisionen zu
erzeugen. Man sucht also Zwischenhashwerte h und Nachrichtenblöcke m, für die
gilt f (m||h) = h, sodass man nun unbemerkt Nachrichtenblöcke einbauen kann.
Differentielle Analyse Bei der differentiellen Analyse von auf Blockchiffren basierenden
Hashfunktionen findet man eine Kollision, wenn man eine Ausgabedifferenz mit
dem Wert null finden kann.
69
10.5.1 Praktische Angriffe aus sinnlosen“ Kollisionen
”
Bekannte Angriffe (z. B. gegen den MD5-Hashalgorithmus) erzeugen Kollisionen, bei
denen der Angreifer einen gewissen Teil der Urbilder frei wählen kann, der Rest jedoch
(pseudo-)zufällig aussieht. Trotzdem lassen sich damit realistische Angriffe durchführen,
davon wollen wir nun zwei besprechen.
Dokumentformate
Postscript (und viele andere Dokumentformate) erlauben Statements der Form
if X = Y then TEXT1 else TEXT2.
Sind Werte S, T bekannt, sodass H(if S) = H(if T ), so haben folgende Dokumente
denselben Fingerprint, führen jedoch zu zwei völlig unabhängigen Textausgaben:
• if S = S then TEXT1 else TEXT2
• if T = S then TEXT1 else TEXT2
X.509-Zertifikate für RSA-2048 public keys
Einführend wollen wir kurz den RSA-Aufbau skizzieren und wie man damit Zertifikate erstellen kann. RSA ist ein asymmetrisches Verschlüsselungsverfahren, also wird mit
unterschiedlichen Schlüsseln ver- und entschlüsselt. Der öffentlich Schlüssel zum Verschlüsseln (public key) ist ein Zahlenpaar (e, n), der geheime Schlüssel zum Entschlüsseln
(secret key) lautet (d, n). Hierbei ist n das Produkt zweier großer, unterschiedlicher Primzahlen p und q. Der Wert e mit 1 < e < (p − q)(q − 1) ist teilerfremd zu (p − 1)(q − 1) und
d ist das multiplikative Inverse von e bezüglich des Modulus (p − 1)(q − 1). Ein Sender
kann mit RSA Zertifikate für eine zu sendende Nachricht erstellen, also die Integrität
seiner Nachricht gewährleisten, indem er z. B. einen Hashwert der Nachricht mit dem secret key verschlüsselt. Mithilfe des public keys, welcher dem Sender eindeutig zugeordnet
und öffentlich bekannt sein muss, kann ein Empfänger nun den Hashwert entschlüsseln,
prüfen, ob der Hash der gesendete Nachricht diesem signierten Hashwert entspricht und
sich sicher sein, dass niemand die Daten bei der Übertragung verändert hat, sofern sie
übereinstimmen.
Das Ziel bei diesem Angriff ist nun das Erzeugen von zwei verschiedenen Zertifikaten
mit unterschiedlichem Moduli n, n0 aber demselben Fingerprint. Das Problem ist nun,
dass diese Moduli Primzahl-Produkte sein müssen. Man nimmt an, es seien zwei 1024Bit-Werte q, q 0 gefunden, sodass die entsprechenden Zertifikatanfänge gleiche Hashwerte
haben (dies ist mit dem Angriff von Wang, beschreiben in [WLF+ 05], möglich). Gesucht
ist nun ein b, sodass q · 21024 + b und q 0 · 21024 + b beides gültige RSA-Zahlen sind (also
2048-Bit-Primzahl-Produkte). Dieses b ermittelt man folgendermaßen:
1. Wähle zwei ungefähr 500 Bit große Primzahlen p, p0 .
2. Solange b ≤ 21024 :
70
a) Wähle das minimale b mit p|n = q · 21024 + b und p0 |n0 = q 0 · 21024 + b.
b) Falls n/p oder n0 /p0 nicht prim, erhöhe b um p · p0 .
3. Falls kein passendes b gefunden, wähle neue Primzahlen p, p0 .
Die Erfolgswahrscheinlichkeit pro Iterationsschritt sind ungefähr die Wahrscheinlichkeit,
dass zwei zufällige 1500-Bit-Zahlen prim sind, also ungefähr (1/ log(21500 ))2 ≈ 10−6 . Auf
diese Weise erhält man zwei 2048-Bit-Zahlen, die (bei entsprechendem Zustand der Hashfunktion) auf den ersten 1024 Bit denselben Hashwert liefern (so wurden q, q 0 ja gewählt
und dann per Multiplikation mit 21024 auf die Position der ersten 1024 Bit verschoben).
Auf den zweiten 1024 Bit stimmen sie außerdem überein (da beide das gleiche b haben)
und somit sind zwei verschiedene Zertifikate gefunden worden, die denselben Hashwert
liefern.
71
11 Nachrichten-Authentifikation
11.1 Message Authentication Codes
Ein Message Authentication Code (MAC) ist nach [KL07] ein per symmetrischer Verschlüsselung erzeugter Prüfteil zur Authentifizierung einer gesendeten Nachricht (er dient
der Sicherung vor unbemerkter Manipulation). Es geht nicht um Geheimhaltung – also
findet keine wirkliche Verschlüsselung statt, sondern um Integrität. Selbst beim OneTime-Pad mit perfekter Sicherheit kann man unbemerkt Bits flippen und so z. B. Geldbeträge ändern (falls diese immer an einer festen Position stehen, was bei genau definierten Protokoll ja der Fall sein sollte). Kommen wir nun zu einer etwas formaleren
Definition eines MACs: Gegeben seien endliche Alphabete A, B, die Blocklänge n und
ein Schlüsselraum K. Ein MAC ist gegeben durch eine Familie von Abbildungen
MACk : A∗ → B n mit k ∈ K.
In der Regel gilt A = B = {0, 1}.
Die Anforderungen an einen MAC lauten:
• Gegeben k, muss MACk effizient berechenbar sein.
• Ein effiziente Angreifer mit Orakelzugriff auf MACk (mit zufälligem Schlüssel k)
kann für keine Nachricht m, die er nicht an das Orakel gesendet hat, MACk (m)
berechnen. Ohne Wissen über den Schlüssel kann ein Angreifer also nichts erstellen.
Einige MACs werden im Folgenden kurz vorgestellt.
HMAC
Der HMAC basiert auf einer Hashfunktion, die verschachtelt verwendet und passend
gepaddet wird:
HMACk (m) = Hash((k ⊕ opad) || Hash((k ⊕ ipad) || m)).
Hierbei sind opad ( outer padding“) und ipad ( inner padding“) feste und öffentlich be”
”
kannte Konstanten. Ein innerer Hash reicht nicht, da man bei einer per Merkle-Damgard
erstellten Hash-Funktion, beliebiges an m anhängen könnte und wieder einen gültigen
MAC erhalten würde.
CBC-MAC
Der CBC-MAC basiert im Gegensatz zum HMAC auf einer Blockchiffren. Es wird ein
Klartext m mit dieser Blockchiffren im CBC-Modus mit dem Nullvektor als Initialisierungsvektor verschlüsselt. Der letzte Block dieses Chiffrats ergibt dann den MAC.
72
Achtung: Der CBC-MAC ist bei variabler Nachrichtenlänge formal unsicher! Ein Angriff,
der bei variabler Nachrichtenlänge erfolgen kann, lautet:
1. Erfrage MAC a für Nachricht m = (m1 , ..., mx )
2. Erfrage MAC b für Nachricht n = (a, n1 , ..., ny )
3. Die Nachricht z = (m1 , . . . , mx , 0, n1 , . . . , ny ) hat nun ebenfalls den MAC b
OMAC (One-key MAC)
Der OMAC basiert wie der CBC-MAC auf einer Blockchiffre. Im Wesentlichen ist es der
CBC-MAC mit folgenden Modifikationen:
• Auf den letzten Nachrichtenblock mn wird vor Berechnung des MACs ein schlüsselabhängiger Wert addiert, also z. B. mn ⊕ Enck (0 . . . 0)
• Der MAC ist auch nur ein Teilstring des letzten Chiffrat“-Blocks und nicht der
”
gesamte Block.
Carter-Wegman
Um zu einer Nachricht m der Länge |m| einen MAC s der Länge |s| zu erhalten, wird bei
Carter-Wegman m als Bitvektor interpretiert, eine 1“ angehängt und der entstandene
”
Vektor mit einer (|m| + 1) × |s|-Matrix k (dem Signaturschlüssel) multipliziert. Es gilt
zu beachten, dass jeder Signaturschlüssel nur einmal verwendbar ist!
11.2 Abstreitbare Authentifikation
Man stelle sich folgendes Szenario vor: Man will einer Gruppe von Kommunikationsteilnehmern beweisen, dass man eine Nachricht verfasst hat, aber anschließend, nach erfolgter Authentifikation, soll es diesen nun nicht mehr möglich sein, unbeteiligten Dritten
zu beweisen, wer der Autor dieser authentifizierte Nachricht war. Wie die Lösung dieses
scheinbaren Widerspruchs möglich ist, wird nun erläutert. Anstatt eine Nachricht mi direkt (nicht-abstreitbar) zu signieren, verwendet man MACs mit Zufallsschlüssel ki und
einem Zeitstempel ti . Für einen gewissen Zeitraum kann man nun Nachrichten signieren,
anschließend sollte es jedem möglich sein, Nachrichten zu signieren und zwar wie folgt:
Man sendet ki−1 nicht-abstreitbar signiert zusammen mit der Nachricht mi , also
(mi , MACki (mi ), ti , ki−1 , sign(ki−1 , ti )).
Dann ist die Authentifizierbarkeit erfüllt, erhält man nämlich (mi , MACki (mi )) vor dem
Zeitpunkt ti+1 und später eine gültige Signatur sign(ki , ti+1 ), so ist die Nachricht mi
authentisch. Die Abstreitbarkeit ist aber auch gewährleistet, denn sobald ki öffentlich
ist, kann jedermann beliebige Tupel
(m0i , MACki (m0i ), ti , ki−1 , sign(ki−1 , ti ))
73
berechnen.
Beispiele für die Verwendung von abstreitbarer Authentifikation sind Off-the-Record
Messaging (OTR, für Instant Messaging) und TESLA (ein Broadcasting-AuthentifizierungsProtokoll), welches in [PCTS02] beschrieben wird.
74
Literaturverzeichnis
[BDPR98] Bellare, Mihir ; Desai, Anand ; Pointcheval, David ; Rogaway, Phillip:
Relations among notions of security for public-key encryption schemes. In:
Krawczyk, Hugo (Hrsg.): Advances in Cryptology – CRYPTO 1998 Bd.
1462. Springer Berlin / Heidelberg, 1998. – ISBN 978–3–540–64892–5, S.
26–45
[Bih94]
Biham, Eli: New Types of Cryptanalytic Attacks Using Related Keys. In:
Helleseth, Tor (Hrsg.): Advances in Cryptology – EUROCRYPT 1993 Bd.
765. Springer Berlin / Heidelberg, 1994. – ISBN 978–3–540–57600–6, S.
398–409
[BKR11]
Bogdanov, Andrey ; Khovratovich, Dmitry ; Rechberger, Christian:
Biclique Cryptanalysis of the Full AES. In: Lee, Dong (Hrsg.) ; Wang,
Xiaoyun (Hrsg.): Advances in Cryptology – ASIACRYPT 2011 Bd. 7073.
Springer Berlin / Heidelberg, 2011. – ISBN 978–3–642–25384–3, S. 344–371
[BW00]
Biryukov, Alex ; Wagner, David: Advanced Slide Attacks. In: Preneel,
Bart (Hrsg.): Advances in Cryptology – EUROCRYPT 2000 Bd. 1807. Springer Berlin / Heidelberg, 2000. – ISBN 978–3–540–67517–4, S. 589–606
[CPS08]
Coron, Jean-Sébastien ; Patarin, Jacques ; Seurin, Yannick: The Random
Oracle Model and the Ideal Cipher Model Are Equivalent. In: Wagner,
David (Hrsg.): Advances in Cryptology – CRYPTO 2008 Bd. 5157. Springer
Berlin / Heidelberg, 2008. – ISBN 978–3–540–85173–8, S. 1–20
[Gei09]
Geiselmann, Dr. W.: Datensicherheitstechnik (Signale, Codes und Chiffren
II). Universität Karlsruhe, Institut für Algorithmen und Kognitive Systeme,
2009
[HKT11]
Holenstein, Thomas ; Künzler, Robin ; Tessaro, Stefano: The equivalence of the random oracle model and the ideal cipher model, revisited. In:
Proceedings of the 43rd annual ACM symposium on Theory of computing.
New York, NY, USA : ACM, 2011 (STOC 2011). – ISBN 978–1–4503–0691–
1, S. 89–98
[KL07]
Katz, Jonathan ; Lindell, Yehuda: Introduction to Modern Cryptography
(Chapman & Hall/Crc Cryptography and Network Security Series). Chapman & Hall/CRC, 2007. – ISBN 1584885513
[Luc04]
Lucks, Stefan: Design Principles for Iterated Hash Functions. Cryptology
ePrint Archive, Report 2004/253, 2004
75
[MH81]
Merkle, Ralph C. ; Hellman, Martin E.: On the security of multiple
encryption. In: Commun. ACM 24 (1981), Juli, Nr. 7, S. 465–467. http:
//dx.doi.org/10.1145/358699.358718. – DOI 10.1145/358699.358718. –
ISSN 0001–0782
[NP10]
Nandi, Mridul ; Paul, Souradyuti: Speeding Up the Wide-Pipe: Secure and
Fast Hashing. In: Gong, Guang (Hrsg.) ; Gupta, Kishan (Hrsg.): Progress
in Cryptology – INDOCRYPT 2010 Bd. 6498. Springer Berlin / Heidelberg,
2010. – ISBN 978–3–642–17400–1, S. 144–162
[OW06]
Oorschot, Paul van ; Wiener, Michael: A Known-Plaintext Attack on
Two-Key Triple Encryption. In: Damgård, Ivan (Hrsg.): Advances in Cryptology – EUROCRYPT 1990 Bd. 473. Springer Berlin / Heidelberg, 2006. –
ISBN 978–3–540–53587–4, S. 318–325
[PCTS02] Perrig, Adrian ; Canetti, Ran ; Tygar, J. D. ; Song, Dawn: The TESLA
Broadcast Authentication Protocol. 2002
[WLF+ 05] Wang, Xiaoyun ; Lai, Xuejia ; Feng, Dengguo ; Chen, Hui ; Yu, Xiuyuan: Cryptanalysis of the Hash Functions MD4 and RIPEMD. In: Cramer,
Ronald (Hrsg.): Advances in Cryptology – EUROCRYPT 2005 Bd. 3494.
Springer Berlin / Heidelberg, 2005. – ISBN 978–3–540–25910–7, S. 551–551
[WYY05] Wang, Xiaoyun ; Yin, Yiqun L. ; Yu, Hongbo: Finding Collisions in the
Full SHA-1. In: In Proceedings of Crypto, Springer, 2005, S. 17–36
76

Skript - Arbeitsgruppe Kryptographie und Sicherheit

Transcrição

Documentos relacionados

Mitschrift 21.04.2015

Sicherheitsanalyse des WEP Protokolls im IEEE 802.11

Ausarbeitung

IT-Sicherheit in der Medizin - Webseiten der Mitarbeiter der Universität

f f f f K0 K1 K2 K3 L R L R

Paper

Sherlock Holmes: Das Geheimnis des silbernen Ohrrings

Handout -

Literaturempfehlun gen bis zum Ende der Schulzeit 1

WLAN-Verschlüsselung WEP: Arbeitsweise und Designfehler