Cryptography Reference
In-Depth Information
Reduktionsfunktion an und erhält dadurch
Urbild 2
. Aus diesem berechnet er
Hashwert 2
, woraus durch die Reduktionsfunktion
Urbild 3
entsteht. Hat Mal-
lory auf analoge Weise schließlich auch
Hashwert 3
,
Urbild 3
und
Hashwert 4
berechnet, dann legt er eine Tabellenzeile an, in die er die soeben berechneten
Hashwerte und Urbilder einträgt. Anschließend nimmt Mallory ein neues
Urbild 1
und beginnt wieder von vorne. So entsteht eine Tabelle wie die folgende:
Urbild 1
Hashwert 1
Urbild 2
Hashwert 2
Urbild 3
Hashwert 3
Urbild 4
Hashwert 4
311
11
143
43
559
59
767
67
607
07
91
91
1.183
83
1.079
79
524
24
312
12
156
56
728
28
210
10
130
30
390
90
1.170
70
773
73
949
49
637
37
481
81
...
...
...
...
...
...
...
...
Von dieser Tabelle speichert Mallory nur die erste und letzte Spalte (also jeweils
Urbild 1
und
Hashwert 4
). Den Rest löscht er, um Speicherplatz zu sparen. Mal-
lory kann die zweispaltige Tabelle nun wie folgt nutzen, um zu einem vorgegebe-
nen Hashwert
h
ein passendes Urbild zu suchen:
1.
Zunächst durchsucht Mallory die letzte Spalte (
Hashwert 4
) nach
h
. Wird er
dort fündig (etwa bei
h
=70), dann muss er nur noch das zugehörige
Urbild 4
ermitteln, um ans Ziel zu kommen.
Urbild 4
ist zwar in der Tabelle nicht ge-
speichert, doch mithilfe von
Urbild 1
kann er es durch Anwendung der
Hashfunktion und der Reduktionsfunktion einfach berechnen.
2.
Findet Mallory
h
in der letzten Spalte nicht, dann müsste er als Nächstes in der
drittletzten Spalte suchen (
Hashwert 3
). Diese Spalte hat er jedoch nicht ge-
speichert. Er kann sich allerdings behelfen, indem er auf
h
erst die Reduktions-
funktion und dann die Hashfunktion anwendet. Nach dem Ergebnis dieser
Berechnung sucht er dann wiederum in der letzten Spalte. Wird er dort fündig,
dann kann er mithilfe von
Hashwert 1
das passende
Urbild 3
bestimmen.
3.
Findet sich
h
nicht in der drittletzten Spalte, dann schaut Mallory in der
fünftletzten Spalte nach (
Hashwert 2
). Er sucht jedoch nicht direkt darin (er
hat die Spalte ja nicht gespeichert), sondern wendet auf
h
die Reduk-
tionsfunktion, dann die Hashfunktion, dann erneut die Reduktionsfunktion
und schließlich erneut die Hashfunktion an. Nach dem Ergebnis dieser Be-
rechnung sucht er in der letzten Spalte.
4.
Nach der fünftletzten ist die siebtletzte Spalte an der Reihe. Die Vorgehens-
weise sollte klar sein.
Natürlich kann die Suche auch erfolglos verlaufen - dann ist die Hashwert-
Tabelle zu klein. Als Urbilder kommen in der Praxis oft Buchstabenfolgen zum
Einsatz, bei denen es sich um ein Passwort handeln könnte. Die Reduktionsfunk-
