Cryptography Reference
In-Depth Information
3.
Gib Hashwert zurück.
gib
g
|y|−
1
zurück
Beweisen Sie, dass MD2
f
eine kollisionsresistente Hashfunktion ist, wenn die zugrunde
liegende Kompressionsfunktion
f
kollisionsresistent ist. Zeigen Sie dazu, wie man aus
einer Kollision für MD2
f
e
zient eine Kollision für
f
konstruieren kann.
8.7
Anmerkungen und Hinweise
Wie bereits in Abschnitt 8.1 erwähnt, finden kryptographische Hashfunktionen breite An-
wendung in der Kryptographie und Informationssicherheit. So werden sie zum Beispiel
zur Integritätsprüfung von Dateien (siehe Abschnitt 8.1), in symmetrischen Authentifizie-
rungsverfahren (siehe Abschnitt 9.4), für digitale Signaturen (siehe Abschnitt 10.3) und
in Verschlüsselungverfahren (siehe Abschnitt 6.4.3) eingesetzt. Eine häufige Anwendung
ist auch das Speichern von Passwörtern in einer Datei. Dabei werden statt der Passwörter
nur die Hashwerte der Passwörter gespeichert. Ist die verwendete Hashfunktion Urbild-
resistent, dann sollte es, auch wenn man die Passwortdatei vorliegen hat, schwer sein, auf
die eigentlichen Passwörter zu schließen; jedenfalls dann, wenn die Passwörter nicht allzu
leicht geraten werden können (Wörterbuchangriff).
Der Begriff der Urbild-Resistenz stimmt mit dem der Sicherheit für Einwegfunktionen
überein, den wir in Abschnitt 6.4.2 definiert haben, dort allerdings für Einwegfunktionen
mit Hintertür. Wie in Abschnitt 6.8 erwähnt, wurde dieser Begriff bereits von Di
e und
Hellman vorgeschlagen [64] und später von Yao [170] formalisiert. Der Begriff der Zweites-
Urbild-Resistenz findet sich in [124], wird dort allerdings als schwache Kollisionsresistenz
bezeichnet. Eine erste formale Definition der Kollisionsresistenz wurde von Damgård in
[60] festgehalten. Eine Arbeit von Rogaway und Shrimpton [142] bündelt alle Definitionen
(auch in unterschiedlichen Varianten) und untersucht die Beziehungen zwischen diesen
systematisch. Diese Arbeit beinhaltet insbesondere die Lösung zu Aufgabe 8.6.1.
In [22] wird der Geburtstagsangriff auch für den Fall, dass Hashwerte nicht gleich-
verteilt sind bei zufälliger Wahl einer Nachricht, ausführlich behandelt [22] (siehe auch
Aufgabe 8.6.4).
Das heute sogenannte Merkle-Damgård-Prinzip wurde unabhängig von Damgård [61]
und Merkle [124] vorgeschlagen. Auch die in den Aufgaben 8.6.7 und 8.6.8 vorgestellten
Konstruktionen gehen auf die Arbeiten von Damgård und Merkle zurück (siehe auch
[157]).
Die zur Zeit in der Praxis am häufigsten eingesetzten Hashfunktionen, wie , SHA-1
und SHA-2, sind, wie in Abschnitt 8.4 erwähnt, alle nach dem Merkle-Damgård-Prinzip
konstruiert. Wir gehen im Folgenden genauer auf diese Hashfunktionen ein.
Die Hashfunktion MD5 wurde 1992 von Rivest entwickelt [141]. Sie löste die ebenfalls
von Rivest 1990 entwickelte Hashfunktion MD4 ab, für die kurz nach ihrer Veröffentli-
chung Schwachstellen und 1995 von Dobbertin schließlich Kollisionen gefunden wurden
[66]. Der von Dobbertin vorgestellte Angriff auf MD4 nutzte dabei zunächst Schwächen
der MD4-Kompressionsfunktion aus, um Kollisionen für diese Funktion zu finden. Der
Angriff konnte dann mit recht wenig Aufwand auf die ganze Hashfunktion erweitert wer-
den.
