Ziele und Wege der Kryptographie - Kryptographie und IT-Sicherheit - page 32

Das Finden von einer zweiten Nachricht zu einem gegebenen Hashwert h(m) und das Finden
von zwei verschiedenen Nachrichten mit gleichem Hashwert wird als Kollision bezeichnet. Es
klingt zunächst paradox, dass in dem Beispiel zu einem gegebenen Hashwert 2 7.840 verschiede-
ne Nachrichten existieren, aber keine davon zu finden sei. „Nicht Finden“ heißt, dass die Auf-
gabe, eine Kollision zu finden, praktisch nicht durchführbar ist.

M

H

Abb. 1-18: Hashfunktion
Abbildung einer großen Menge M von Nachrichten
auf eine Menge H von Hashwerten.

Beispiel:
m = 1 KByte |M| = 2 8.000
h = 160 Bit |H| = 2 160
Menge der Nachrichten mit gleichem Hashwert:
im Mittel: |M| / |H| = 2 8.000 / 2 160 = 2 7.840 .

Der anschauliche Grund dafür ist, dass die Nachrichten mit gleichen Hashwerten nicht wie in
Abb. 1-18 in Teilmengen geordnet sind, sondern in M verstreut sind. Beim Prüfen von zu-
fallsmäßig gewählten Nachrichten auf einen vorgegebenen Hashwert ist die Trefferquote äu-
ßerst gering, nämlich 2 7.840 / 2 8.000 = 2 -160 . D.h. im Mittel muss man 2 160 mal „würfeln“, bis ein
Treffer erzielt wird. Wenn 10 9 Computer auf der Welt je 10 9 Nachrichten je sec prüfen, dann
wird eine Kollision im Mittel nach 2 160 / (10 9 ·10 9 ) sec 5·10 22 Jahren gefunden (zum Ver-
gleich: Das Alter des Weltalls wird mit 10 bis 20·10 9 Jahren angegeben.)
Wenn es praktisch nicht durchführbar ist, eine Kollision zu finden, dann wird eine Hashfunkti-
on als kollisionsresistent bezeichnet. Man unterscheidet ferner die Eigenschaften schwach
kollisionsresistent und stark kollisionsresistent . Der Hashwert h(m) ist charakteristisch für die
Nachricht m und wird deshalb auch als Fingerabdruck oder Message-Digest bezeichnet. Wei-
teres zu Hashfunktionen, siehe Kap. 3. Eine Visualisierung, wie sensibel Hashfunktionen auf
kleinste Änderungen in der Nachricht reagieren, findet sich in CrypTool im Menü Einzelver-
fahren \ Hashverfahren \ Hash-Demo.

1.3.5.2 Einwegfunktionen
Kryptographische Hashfunktionen haben wir bereits als Einwegfunktion kennen gelernt. Hash-
funktionen sind jedoch nicht eineindeutig, zu einem Hashwert existieren viele Nachrichten.
Daneben gibt es auch eineindeutige Einwegfunktionen.
Einwegfunktionen sind hier in einem diskreten, endlichen Zahlenraum definiert.
Für eine eineindeutige Einwegfunktion y=f(x) und ihre Umkehrfunktion x=f -1 (y) gilt:
y=f(x) y ist aus x einfach zu berechnen.
x=f -1 (y) Zu einem gegebenen Wert y existiert immer ein x, aber die Aufgabe, diesen
Wert x zu finden, ist praktisch nicht durchführbar. Der Aufwand dafür steigt z.B. exponentiell
mit der Stellenlänge der verwendeten Zahlen.