Kryptografische Hashfunktionen - Kryptografie - page 231

allgemeiner formulieren. Nehmen wir an, ein Jahr habe t Tage. Dann beträgt die
Anzahl der Menschen, die zusammenkommen müssen, damit die Wahrschein-
lichkeit eines gleichen Geburtstags ½ ist, stets etwas mehr als die Wurzel von t .
Was das alles mit kryptografischen Hashfunktionen zu tun hat? Ganz ein-
fach: Will Mallory wissen, wie viele Nachrichten er im Durchschnitt durchpro-
bieren muss, bis er durch Zufall eine Kollision gefunden hat, dann braucht er nur
das Geburtstagsproblem zu bemühen. Die Zahl der möglichen Hashwerte ist
dabei die Anzahl der Tage im Jahr, die Zahl der durchprobierten Nachrichten ist
die Anzahl der Menschen. Hat der Hashwert die Länge n , dann gibt es 2 n mögli-
che Hashwerte. Die Wurzel aus 2 n beträgt 2 n/2 , was bedeutet, dass Mallory im
Schnitt bereits nach 2 n/2 Versuchen eine Kollision findet.
Ein Angriff, der das Geburtstagsphänomen ausnutzt, wird als Geburtstagsan-
griff bezeichnet. Die einfachste Form des Geburtstagsangriffs kennen Sie bereits:
Das Anwenden einer kryptografischen Hashfunktion auf alle möglichen Nach-
richten, bis eine Kollision gefunden ist. Bei einem Hashwert der Länge 128 Bit
benötigt Mallory bei dieser Methode durchschnittlich 2 64 (also etwa 10 19 ) Versu-
che. Um diese mit einem PC durchzuprobieren, ist Mallory einige zehntausend
Jahre beschäftigt. Für die NSA mit ihren Supercomputern dürfte dies jedoch
etwas schneller gehen, weshalb alle neueren kryptografischen Hashfunktionen
160 Bit oder mehr als Länge des Hashwerts verwenden.
Es gibt noch andere Formen des Geburtstagsangriffs. Kann Mallory Nach-
richten, die Alice signiert, vorformulieren, dann funktioniert beispielsweise fol-
gende Methode ( n ist dabei die Länge des Hashwerts in Bit):

1. Mallory, der weiß, dass Alice eine Packung Büroklammern bestellen will, for-

muliert mit einer Substitutionsattacke 2 n/2 Versionen einer unverdächtigen
Bestell-Nachricht (etwa »Ich bestelle eine Packung Büroklammern. Alice«).

2. Mallory formuliert eine Nachricht mit dem von ihm gewünschten Inhalt

(etwa »Ich bestelle einen Staubsauger. Alice«). Diese Nachricht verändert er
fortlaufend durch die von der Substitutionsattacke bekannte Methode und
berechnet jeweils den Hashwert. Diesen vergleicht er dann jeweils mit den
Hashwerten der 2 n/2 unverdächtigen Nachrichten. Das Ganze macht er so
lange, bis er schließlich eine Kollision zwischen einer Büroklammer- und ei-
ner Staubsauger-Nachricht gefunden hat.

3. Die unverdächtige Büroklammer-Nachricht legt Mallory nun Alice zum Sig-

nieren vor (Alice schöpft keinen Verdacht, da sie ja ohnehin Büroklammern
bestellen wollte).

4. Die Staubsauger-Nachricht mit gleichem Hashwert gibt Mallory an seinen

Freund, den Staubsauger-Vertreter, weiter.

Damit eine solche Geburtstagsattacke Erfolg hat, muss Mallory durchschnittlich
2 n/2 Staubsauger-Nachrichten durchprobieren. So etwas ist schon bei einem Hash-
wert der Länge 128 Bit kaum zu schaffen und bei 160 Bit absolut aussichtslos.