Cryptography Reference
In-Depth Information
fruchten. Zum Beispiel wurde Matsui inspiriert durch die einige Jahre zuvor von Biham
und Shamir entwickelte differenzielle Kryptanalyse [33, 34, 32]. Eine gute einführende Be-
schreibung der linearen und differentiellen Kryptanalyse findet sich in [92].
Wie bereits in Abschnitt 4.5 erwähnt ist AES so konstruiert, dass zumindest die be-
kannten Kryptanalyse-Techniken scheitern (sollen). Bisher gilt AES in der Tat als sicher.
Allerdings wurden bereits Schwachstellen aufgedeckt, die glücklicherweise bisher jedoch
nicht von praktischer Bedeutung sind. Während sich viele Arbeiten zur Kryptanalyse
von AES mit vereinfachten Varianten von AES beschäftigen, insbesondere mit Varianten,
in denen die Anzahl der Runden reduziert ist (siehe, z. B. [35]), wird in [36] ein erster
kryptographischer Angriff auf AES mit Schlüsseln der Länge 256 Bit und voller Runden-
zahl vorgestellt. Von größerer praktischer Bedeutung sind zur Zeit aber Schwachstellen,
die sich auf die Implementierung von AES und damit zusammenhängende Seitenkanalan-
griffe (siehe auch Abschnitt 1.4) beziehen. So wurden zum Beispiel in [29, 159] Angriffe
auf Implementierungen von AES gefunden, die es erlauben, den verwendeten Schlüssel
dadurch zu extrahieren, dass die Zeit für die Verschlüsselung von Nachrichten gemessen
wird (
timing attacks
).
Der Begriff der pseudozufälligen Funktionen (PRF) wurde von Goldreich, Goldwasser
und Micali [82] definiert und es wurde gezeigt, wie man diese Funktionen aus sogenannten
Pseudozufallsgeneratoren konstruieren kann. Das Konzept der Pseudozufallsgeneratoren
wurde von Yao [170] eingeführt. Ein Pseudozufallsgenerator ist ein e
zienter Algorith-
mus, der einen Bitvektor bestimmter Länge als Eingabe bekommt und einen längeren
Bitvektor als Ausgabe liefert. Wird die Eingabe zufällig gewählt, so sollte ein Unterschei-
der nicht zwischen der Ausgabe des Generators und einem tatsächlich zufällig gewählten
Bitvektor gleicher Länge unterscheiden können. Ein Pseudozufallsgenerator erweitert also
einen zufällig gewählten Bitvektor auf einen längeren zufällig »aussehenden« Bitvektor.
Eine erste Konstruktion eines Pseudozufallsgenerators basierend auf speziellen Annah-
men in der algorithmischen Zahlentheorie wurde von Blum und Micali [40] vorgestellt.
In [170] hat Yao gezeigt, dass Pseudozufallsgeneratoren aus beliebigen Einwegfunktionen
(siehe Bemerkungen am Ende von Abschnitt 4.7) konstruiert werden können. Das Kon-
zept der Einwegfunktionen wurde bereits von Die und Hellman vorgeschlagen [64] und
später von Yao [170] formalisiert. Wir werden Einwegfunktionen (mit Hintertür) in Ab-
schnitt 6.4.2 kennenlernen. Wie man aus Pseudozufallsfunktionen Pseudozufallspermuta-
tionen (PRP) gewinnt, wurde von Luby and Rackoff in [116] gezeigt. Aus den genannten
Resultaten folgt, dass Pseudozufallsfunktionen und -permutationen aus Einwegfunktio-
nen konstruiert werden können, wobei die Existenz solcher Funktionen wiederum aus be-
stimmten Annahmen in der algorithmischen Zahlentheorie folgt. Umgekehrt wurde von
Impagliazzo und Luby gezeigt, dass die Existenz von Einwegfunktionen notwendig für
die Existenz von Pseudozufallsgeneratoren, -funktionen, -permutationen sowie anderer
Primitive ist [94]. Im Lehrbuch von Goldreich [80] werden die genannten Konstruktionen
und die Zusammenhänge zwischen den genannten kryptographischen Primitiven ausführ-
lich beschrieben. Wie bereits am Ende von Abschnitt 4.7 erwähnt, sind diese (beweisbar
sicheren) Konstruktionen leider nicht praktikabel.
Das in Abschnitt 4.8 vorgestellte PRF/PRP-Switching Lemma wurde u. a. in [27, 152]
bewiesen (siehe auch Referenzen in diesen Arbeiten). In diesen Arbeiten wird eine nütz-
liche und in der Kryptographie mittlerweile weitverbreitete Beweistechnik erläutert, bei
