Rainbow Table

Die rainbow table bzw. Regenbogentabelle ist eine von Philippe Oechslin entwickelte Datenstruktur, die eine schnelle, probabilistische Entschlüsselung von Hash-Werten ermöglicht. Die Geschwindigkeitsvorteile werden durch erhöhten Speicheraufwand erreicht. Sie funktioniert bei Hash-Funktionen, wie sie z. B. bei den Passwörtern für Windows NT, einigen PHP-Installationen oder vielen Routern verwendet werden.

Funktionsweise

Eine zufällige Zeichenkette wird durch eine Hash-Funktion H in einen Ciphertext transformiert. Das Ergebnis der Hash-Funktion wird durch eine Reduktions-Funktion R in eine neue Zeichenkette umgewandelt, die die gleiche Länge der Eingangs-Zeichenkette besitzt. Dieser Schritt wird n-mal wiederholt und bildet am Ende eine Kette (Chain). Gespeichert werden Anfangs- und Endwert dieser Kette. Diese Schrittfolge wird ebenfalls n-mal wiederholt und bildet eine universelle Rainbow-Tabelle.

Reduktionsfunktion

Diese Funktion reduziert als Beispiel den 32 Zeichen langen MD5-Hash auf n-Zeichen. Jede dieser Reduktionen liefert dank MD5 eine neue, "eindeutige" Zeichenkette oder eine Kollision. Um Kollisionen zu vermeiden, verwendet man verschiedene Reduktionsfunktionen, die periodisch angewendet, eine eindeutige Zuordnung der Eingangs-Zeichenkette und des Ausgangshashes ermöglichen. Dieses Verfahren stellt eine effizientere Methode für n-stellige Zeichenketten dar als beispielsweise ein Brutforce Angriff mit Schlüsselsuche von [a-//////], da bei letzterem zig Zeichenketten in Hashes umgewandelt werden, die mit hoher Wahrscheinlichkeit niemals fallen, bzw gewählt, werden.

Anwendung

Gesucht wird die Zeichenfolge, aus der mittels MD5 der Hash-Wert 97fae39bfd56c35b6c860aa468c258e0 erzeugt wurde. Der herkömmliche Weg, alle MD5-Hashes für alle möglichen Variationen zu berechnen und diese zu vergleichen, ist sehr rechenintensiv und muss bei neuen Suchläufen wiederholt werden.

Sinnvoll wäre es nun, die bereits berechneten Hashes in einer Datenbank zu speichern und bei erneuten Suchläufen nur noch vergleichen zu müssen, ob der gesuchten Hash schon bekannt ist. Bei einer Suche über 64 mögliche Zeichen [A-Za-z0-9./], die jede Stelle des Eingangstextes haben könnte, ergeben sich bei 6 Stellen $64^{6}$ Variationen. Werden nun Hash und Wert (KEY-VALUE Pairs) in einer Datenbank gespeichert, so werden pro Datenbankreihe mindestens 32 Bytes für den Hash und 6 Bytes für den Plaintext benötigt.

Diese Datenmengen lassen sich meistens nicht verarbeiten und müssen reduziert werden.

Sinnvoller Mittelweg ist nun die Rainbow-Tabelle

Anstatt alle Werte samt Schlüsseln zu speichern, werden nur die anfängliche Zeichenkette und der Ausgangswert (Hash) einer n-elementigen Kette gespeichert. Auf diese Weise lassen sich n-Hashes durch einen Start- und Endwert repräsentieren und in vergleichsweise kurzer Zeit neu berechnen, wiederfinden. Ist einer der Endpunkte der Kette der gesuchte (Eingangs-)Hash, so wird diese Kette neu berechnet.

Bei schlecht programmierten oder trivialen Reduktionsfunktionen treten nach wenigen Läufen Kollisionen auf, die zu Wiederholungen der reduzierten Texte und somit auch der Hashes führen. Solche internen Schleifen tragen dann dazu bei, dass der Algorithmus versagt: Man berechnet mühsam Tausende von Elementen und nur 5 im Worst-Case sind eindeutig unterscheidbar.

Die Wahrscheinlichkeit, aus den reduzierten Hashes genau den gesuchten Eingangstext zu erhalten, ist abhängig von der Güte der Reduktionsfunktion(en) und den Parametern bei der Erstellung der Rainbow-Tabellen.

Erstellen einer Rainbow-Table

Es gibt zwei Programme, die sich mit dem Erstellen von Rainbow-Tables befassen:

RainbowCrack wird als ausführbares Windows-Programm und als Quellcode zum Download angeboten. Unter Windows startet man das Unterprogramm rcrack.exe mit diversen Parametern in einem Konsolenfenster. Falls man unter Linux, Solaris oder anderen Unix Derivaten eine Rainbow-Table erstellen möchte, lädt man sich den Quellcode herunter und übersetzt diesen mit Hilfe eines Compilers in Maschinensprache. Danach startet man rcrack und erstellt, auch hier mittels diverser Parameter, die Rainbow Table.

Durch die Parameter kann man genau vorgeben, welche Größe, welchen Zeichensatz und welchen Algorithmus man haben möchte. Das Erstellen einer Rainbow Table dauert -- je nach Einstellung und Rechenleistung -- zwischen mehreren Tagen bis Monaten. Aus diesem Grund kamen Programmierer auf die Idee, die Rechenleistung auf mehrere Computer zu verteilen. Dies ermöglicht das Programm DistrRTgen. Es basiert teilweise auf dem Quellcode von RainbowCrack. Auch hier gibt es eine Windows-Version und den Quellcode zum Download. Dadurch lassen sich Rainbow Tables weitaus schneller erstellen.

Die Website FreeRainbowTables.com lässt von der Community mittels DistrRTgen Rainbow-Tables erstellen und bietet diese auf der Website zum Download an.

Gegenmaßnahmen

Eine wirkungsvolle Möglichkeit, den Einsatz von Rainbow Tables zum Entschlüsseln zu verhindern, ist es, Hash-Funktionen mit Salt einzusetzen. Durch den Salt wird erreicht, dass vorberechnete Tabellen ohne diesen Salt unwirksam sind.

Siehe auch

Quellen