· 

Rainbow Tables

1. Einführung

Der Begriff Rainbow Table klingt zunächst einmal nach einem infantil angehauchtem Spielzeug, doch in Wirklichkeit verbirgt sich dahinter ein sehr mächtiges Tool zum Entschlüsseln von Passwörtern. Im Prinzip handelt es sich dabei um einen hoch effizient gespeicherten, vorberechneten Brute Force Angriff. Diese Datenstruktur wurde von Philippe Oechslin entwickelt.


2. Voraussetzungen und grundlegende Funktionsweise

Wir gehen von einer Menge an Hashwerten aus, zu denen das ursprüngliche Passwort im Klartext berechnet werden soll. Da es sich bei Hash-Funktionen um mathematische Einwegfunktionen handelt, die nur theoretisch und nicht praktisch umzukehren sind, ist das Hashen von Passwörtern (zumindest in der Theorie) eine sichere Speichermöglichkeit. Wir gehen weiterhin davon aus, dass der zum Hashen verwendete Algorithmus (z. B. SHA512) bekannt ist. Der Aufbau einer Rainbow-Table muss vom verwendeten Hash-Algorithmus unabhängig funktionieren. Die Passwörter, die mithilfe einer Rainbow-Table geknackt werden sollen, dürfen nicht gewürzt sein! Näheres zum Würzen von Passwörtern mit Salz und Pfeffer erfährst du hier.

Der Grundgedanke bei einer Rainbow-Table ist, dass man eine Liste an Passwortkandidaten führt, die dann gehasht wird und deren Hashes dann mit einer Reduktionsfunktion zu neuen Passwortkandidaten reduziert werden. Es gibt verschiedene Arten von Reduktionsfunktionen. Eine einfache (aber, wie wir später noch sehen werden, nicht sinnvolle) Möglichkeit bestünde darin, nur die letzten fünf Zeichen des Hashwerts zu betrachten. Diese neuen Passwortkandidaten werden dann wiederum gehasht, reduziert, gehasht, reduziert, gehasht usw.. Auf diese Art und Weise entsteht eine Kette von Hashwerten und Passwortkandidaten, an deren Ende ein Hashwert steht. Anhand des folgenden Schaubilds siehst du, weshalb man bei diesem Vorgehen von einer Rainbow-Table spricht.

Gespeichert werden dann nur der erste Passwortkandidat und der letzte Hashwert, der sich durch die Kette ergeben hat. Zwischen dem ersten Passwortkandidaten und dem letzten Hashwert befinden sich also (abhängig von der Anzahl an Runden) potentiell tausende Hashwerte, die zwar berechnet, aber nicht gespeichert wurden. Die Berechnung kann mit dem ersten gespeicherten Passwortkandidaten und dem Wissen um die Reduktionsfunktion jedoch rekonstruiert werden. Durch die hoch effiziente Speicherung der Ketten (bestehend aus Passwort-Kandidaten und Hashwerten) kann hier ein Kompromiss aus Rechenaufwand bzw. Laufzeit und Speicherbedarf geschlossen werden. In der Informatik nennt man das einen Time Memory Trade-Off (kurz TMTO). Dieser Trade-Off ist nötig, da man bei einem 8-stelligen Passwort, bei dem 100 Zeichen pro Stelle erlaubt sind, schon 10 Millionen Werte gespeichert werden müssen (und dabei bleibt es ja nicht). Bei zu vielen Einträgen wird irgendwann auch die Suche erschwert. Lange Ketten in der Rainbow-Table bedeuten zwar weniger Speicherbedarf aber auch mehr Rechenaufwand beim Rekonstruieren einer gefundenen Kette. Es kommt jedoch eher selten vor, dass die gesamte Kette durchgerechnet werden muss, weshalb lange Ketten wünschenswert sind, zumal die Rekonstruktion oft in hinreichend kurzer Zeit möglich ist. Die Güte der verwendeten Reduktionsfunktion spielt ebenfalls eine entscheidende Rolle beim Aufbau der Rainbow-Table, doch dazu später mehr.

Der erste Passwortkandidat in einer Kette sollte nicht schon in einer anderen Kette vorgekommen sein, da andernfalls unnötige Daten gespeichert werden. Das Ziel der Berechnung ist allerdings, dass im Optimalfall jeder mögliche Passwortkandidat in irgendeiner berechneten Kette vorkommt, denn wenn das nicht der Fall ist, dann gibt es Hashwerte, zu denen das dazugehörige Passwort nicht in der Rainbow Table nachgeschlagen werden kann.

Der Algorithmus zum Aufbau einer Rainbow-Table erwartet als Intput also eine endliche Menge an Passwort-Kandidaten, einen Hash-Algorithmus, eine Reduktionsfunktion und eine Anzahl an Runden, die angibt, wie oft der Passwortkandidat gehasht und reduziert werden soll.


3. Passwortkandidat in einer Rainbow-Table finden

Es sind nun zwei Schritte notwendig, um zu einem Hashwert das dazugehörige Passwort in der Rainbow-Table nachzuschlagen: 

  1. Der Hashwert wird in allen gespeicherten Einträgen der Rainbow-Table gesucht (das ist jeweils das letzte Glied in der Passwortkandidat-Hashwert-Kette). Man sucht also (vereinfacht ausgedrückt) in der letzten Spalte der Hashwert-Kette. Wenn kein passender Wert in der Tabelle gefunden wurde, wird der Hashwert mit der Reduktionsfunktion in einen neuen Passwortkandidaten überführt und dieser dann gehasht. Der so entstandene neue Hashwert wird dann erneut in der Rainbow-Table gesucht. Es wird jetzt quasi in der vorletzten Spalte der Hashwert-Kette gesucht. Die Spalten der Rainbow-Table werden folglich von hinten nach vorne durchlaufen. Da die Ketten rekonstruierbar sind, ist das ohne Weiteres möglich. Man wiederholt diesen Schritt solange, bis entweder ein Hashwert gefunden oder die Anzahl der Spalten der Rainbow-Table überschritten wurde.
  2. Wenn der gegebene Hashwert in der Rainbow-Table gefunden wurde, dann kennt man zwar die"richtige" Zeile in der Rainbow-Table und damit den ersten Passwortkandidaten, doch man kennt das tatsächliche Passwort noch nicht. Die gefundene Kette muss nun schrittweise neu berechnet werden. Das ist aber kein Problem, da die Berechnung einer Kette recht schnell erfolgen kann (auch bei sehr langen Ketten). Hierzu verwendet man (wie zuvor schon) den ersten Passwortkandidaten, hasht ihn, reduziert ihn, hasht das Ergebnis, reduziert es usw.. In jedem Zwischenschritt wird überprüft, ob der berechnete Hashwert mit dem des gegebenen Hashwert übereinstimmt. Wenn das der Fall ist, hat man das Passwort gefunden.

 


4. Die Reduktionsfunktion

Wie bereits erwähnt, muss für den Aufbau einer Rainbow-Table eine leistungsstarke Reduktionsfunktion verwendet werden. Folgende Richtlinien gilt es dabei zu beachten:

  1. Die Reduktionsfunktion sollte möglichst "sinnvolle" Passwortkandidaten erzeugen. Ausschließlich kryptische Aneinanderreihungen von Zahlen und Buchstaben (z. B. direkt aus dem Hashwert) sind nicht sinnvoll!
  2. Die Reduktionsfunktion berechnet im Idealfall nur mögliche Passwortkandidaten. Wenn sich ein Angreifer also auf eine bestimmte Zeichenmenge beschränkt, dann sollte die Reduktionsfunktion nicht aus diesem Bereich hinauslaufen. Ein limitierter Zeichensatz schränkt aber auch gleichzeitig die Anzahl der zu prüfenden Passwortkandidaten ein. Eine Rainbow-Table, die aus dem gesamten UTF-8-Zeichensatz alle möglichen Passwörter einer bestimmten Länge speichert, kann in der Praxis kaum verwendet werden. Hier ist wieder der Time Memory Trade-Off (TMTO) zu beachten.
  3. Die Reduktionsfunktion muss zu einem gegebenen Hashwert immer das selbe Ergebnis (also denselben Passwortkandidaten) liefern.
  4. Die Reduktionsfunktion sollte möglichst wenige Kollisionen erzeugen. Eine Kollision im Kontext von Rainbow-Tables bedeutet, dass aus zwei verschiedenen Hashwerten derselbe Passwortkandidat berechnet wird. Das Problem entsteht aus der mangelnden Injektivität, die Hash-Funktionen im Allgemeinen inhärent ist. 

Die Qualität der Reduktionsfunktion wird maßgeblich durch die Kollisioneigenschaft bestimmt. Wenn in der Rainbow-Table eine Kollision auftritt, dann gibt es Passwortkandidaten, die mehrmals in verschiedenen Ketten (also redundant) gespeichert worden sind. Da Reduktionsfunktionen gemäß Gebot 3 für einen bestimmten Hashwert immer denselben Passwortkandidaten erzeugen sollen, sind damit auch alle folgenden Passwortkandidaten doppelt gespeichert, was bei langen Ketten einen durchaus nicht zu vernachlässigenden Aufwand für die Rekonstruktion bedeutet.

Um Angriffe mit Rainbow-Tables noch effizienter zu gestalten, kann man als initiale Passwortkandidaten häufig verwendete Passwörter nutzen. Dazu gibt es zahlreiche Listen im Internet. Dadurch sind sogar auf relativ sichere Algorithmen wie SHA512 sehr effiziente Angriffe möglich.


5. Das Problem mit gewürzten Passwörtern ...

Um einem Angreifer den Einsatz von Rainbow-Tables zu versalzen, würzt man Passwörter mit einem Salt und/oder Pepper. Durch den Einsatz eines Salts, wird das Nachschlagen des Passwortes in einer Rainbow Table erheblich erschwert, da diese im Vorfeld berechnet wird. Wenn ein n-Bit langes Salt verwendet wird, dann müssen 2 hoch n mal so viele Passwortkandidaten berechnet werden wie ohne den Einsatz eines Salts. Selbst wenn das Salt für ein Passwort bekannt ist, könnte man es nur auf dieses Passwort anwenden, wodurch das Erstellen einer Rainbow-Table nicht mehr effektiv ist. Beachte aber, dass diese Würz-Mechanismen den Angreifer nur ausbremsen und nicht zwangsläufig aufhalten, da alle bekannten Verfahren auf mathematischen Problemen basieren, die nur in der Praxis kaum lösbar sind ... in der Theorie hingegen schon. Das einzig theoretisch sichere Verfahren ist das One-Time-Pad.