Kryptografische Hashfunktionen - Kryptografie - page 230

In diesem Text sucht Mallory nach Wörtern, die er ersetzen kann, ohne dass sich
der Sinn verändert. Hier einige Beispiele:

■ »Samstag« kann Mallory durch »Sonnabend« ersetzen.

■ »16 Uhr« kann er durch »16.00 Uhr« ersetzen.

■ »Alice Onliner« kann er durch »A. Onliner« ersetzen.

■ »hiermit« kann er ganz weglassen.

Nehmen wir an, Mallory habe n Ersetzungsmöglichkeiten gefunden. Durch die
Kombination von Ersetzungen kann er 2 n Staubsauger-Bestellungen mit gleicher
Bedeutung, aber meist unterschiedlichem Hashwert generieren. Mallory berech-
net nun nacheinander alle 2 n Hashwerte, bis er irgendwann auf eine Staubsauger-
Bestellnachricht stößt, die denselben Hashwert wie die abgefangene Nachricht
hat. Damit ist ein zweites Urbild gefunden. Hat der Hashwert der kryptografi-
schen Hashfunktion eine Länge, die kleiner als n ist (also kleiner als die Anzahl
der Ersetzungsmöglichkeiten), dann ist die Wahrscheinlichkeit sehr groß, dass
Mallory mit dieser Methode ein zweites Urbild findet.
Dabei gibt es für eine Substitutionsattacke oft bessere Möglichkeiten als das
Ersetzen von Wörtern. So kann Mallory etwa ein Leerzeichen durch ein anderes
nicht druckbares Zeichen ersetzen, ohne dass ein Unterschied auffällt. Oder er
kann am Ende des Textes einige Leerzeichen hinzufügen. Bei vielen Formaten
(etwa HTML) gibt es zudem die Möglichkeit, Kommentare einzufügen, was Mal-
lory ebenfalls nutzen kann.
Eine Substitutionsattacke funktioniert bei jeder kryptografischen Hashfunk-
tion und bei jeder Art von Nachricht. Die einzige Gegenmaßnahme besteht darin,
dass Alice den Hashwert ausreichend lang wählt, denn je länger der Hashwert,
desto größer die Anzahl der Nachrichten, die Mallory durchprobieren muss. Hat
der Hashwert etwa die Länge 160 Bit, dann muss Mallory entsprechend etwa
160 Ersetzungsmöglichkeiten (oder mehr) suchen und daraus 2 160 Hashwerte
bilden, die er durchprobieren muss. Wenn wir davon ausgehen, dass er im Schnitt
schon nach der Hälfte der durchprobierten Werte Erfolg hat, dann muss er
immerhin 2 159 = 7,3 · 10 47 Werte generieren, was selbst mit den besten jemals
denkbaren Superrechnern nicht vor Ende dieses Universums zu schaffen ist.

Geburtstagsangriff

Versuchen Sie einmal, folgende Frage zu beantworten: Wie viele Menschen müs-
sen in einem Raum versammelt sein, damit mit einer Wahrscheinlichkeit von ½
mindestens zwei davon am gleichen Tag Geburtstag haben? Diese Frage wird
auch Geburtstagsproblem genannt. Die Antwort: Schon wenn 22 Menschen in
einem Raum versammelt sind, dann beträgt die Wahrscheinlichkeit etwa ½ . Dies
bedeutet Folgendes: Wenn wir eine größere Anzahl von 22-köpfigen Menschen-
gruppen zusammenstellen, dann gibt es in etwa der Hälfte davon zwei Personen,
die am gleichen Tag Geburtstag feiern. Das Geburtstagsproblem lässt sich auch