Cryptography Reference
In-Depth Information
schon ein Hashfunktion-Durchlauf sicher genug ist. In diesem Fall führt die
Hash-Iteration jedoch dazu, dass auch Mallory für jede Prüfung 100 Durchläufe
benötigt. Seine Suche wird dadurch um den Faktor 100 langsamer. Natürlich
kann Alice auch 1.000 oder 1.589 Durchläufe wählen - je nachdem, welchen Per-
formanzverlust sie in Kauf nehmen will.
Regenbogentabellen
Kryptografische Hashfunktionen haben für Mallory einen entscheidenden Vor-
teil: Da es keinen Schlüssel gibt, erzeugt dasselbe Urbild bei Verwendung dersel-
ben Hashfunktion immer denselben Hashwert - überall und zu jeder Zeit. Hat
Mallory erst einmal eine Kollision oder ein passendes Urbild gefunden, dann lässt
sich dieser Erfolg nicht mehr aus der Welt schaffen. Bei einem Verschlüsselungs-
verfahren ist das anders: Hier können Alice und Bob eine erfolgreiche Schlüssel-
suche durch einen Schlüsselwechsel zunichte machen.
Die beschriebene Tatsache kann Mallory nutzen, indem er eine möglichst
große und ständig wachsende Sammlung von Urbild-Hashwert-Paaren anlegt
(
Hashwert-Tabelle
). Falls es mehrere Sammlungen gibt, lassen sich diese zu einer
besonders großen Hashwert-Tabelle vereinigen, die beispielsweise im Internet
veröffentlicht wird. Sucht Mallory zu einem bestimmten Hashwert ein passendes
Urbild, dann schaut er in der Hashwert-Tabelle nach. Dies ist ziemlich mühsam,
da Mallory mit einer riesigen Tabelle hantieren muss. Allerdings ist das Lesen
eines Urbild-Hashwert-Paares aus einer Tabelle immer noch deutlich performan-
ter als das Berechnen des Hashwerts aus dem Urbild.
Wie Sie leicht nachvollziehen können, funktionieren Hashwert-Tabellen
besonders gut im Zusammenhang mit Wörterbuch-Angriffen. So kann Mallory
beispielsweise zu jedem Wörterbucheintrag vorab den passenden Hashwert
berechnen und speichern. Hat Mallory eine geeignete Tabelle zur Hand, dann
wird ein Wörterbuch-Angriff deutlich effektiver, wobei zudem Hash-Iterationen
viel von ihrer Wirkung verlieren.
Als größter Nachteil einer Hashwert-Tabelle gilt, dass Mallory eine enorme
Menge an Speicher benötigt. Mehrere Kryptografen haben daher in den letzten
Jahren Verfahren vorgeschlagen, mit denen sich Speicher einsparen lässt, ohne
dabei zu viel an Geschwindigkeit einzubüßen. Praktisch alle dieser Verfahren sind
Varianten einer Methode, die ich im Folgenden an einem Beispiel erklären will.
Wir nehmen an, dass das Urbild eine positive ganze Zahl ist (z.B. 311). Als Hash-
funktion nehmen wir eine Funktion, die alle Stellen bis auf die letzten zwei streicht
(dies ist zwar keine kryptografische Hashfunktion, reicht aber aus, um die
Methode zu erklären). Der Hashwert von 311 ist also 11. Außerdem benötigen wir
eine sogenannte
Reduktionsfunktion
. Als einfaches Beispiel verwenden wir hierfür
eine Funktion, die den Eingabewert mit 13 multipliziert (aus 11 wird also 143).
Mallory geht nun wie folgt vor: Er nimmt ein beliebiges Urbild (
Urbild 1
) und
berechnet dazu den Hashwert (
Hashwert 1
). Auf
Hashwert 1
wendet er die
