Rainbow Table

Grundidee und Bedeutung

Eine Rainbow Table ist eine von Philippe Oechslin entwickelte Datenstruktur, mit der sich zu einem gegebenen Hashwert schnell und speichereffizient die ursprüngliche Zeichenfolge – meist ein Passwort – suchen lässt. Sie wird bei der Passwortwiederherstellung (Passwort-Cracking), in der IT-Forensik und bei Penetrationstests eingesetzt.

Ihr Grundprinzip ist ein Time-Memory Tradeoff: Die Suche ist erheblich schneller als Brute Force, benötigt aber mehr Speicher als eine reine Berechnung. Voraussetzung ist eine Hashfunktion ohne Salt, wie sie beispielsweise bei Passwörtern früherer Windows-Versionen und bei vielen Routern verwendet wurde. Umfangreiche Tabellen wurden unter anderem für LM-Hashes und MD5 berechnet.

Eine Rainbow Table speichert nicht alle möglichen Passwörter und Hashwerte einzeln, sondern fasst sie in Ketten (Chains) zusammen. Gespeichert werden normalerweise nur das erste Kennwort und der letzte Hashwert jeder Kette. Die Tabelle wird einmalig erstellt und anschließend als Nachschlagetabelle verwendet.

Aufbau und Suche in einer Kette

Eine Hashfunktion ordnet einer Binärfolge beliebiger Länge eine Binärfolge fester Länge zu. Bei MD5 beträgt die Ausgabelänge 128 Bit beziehungsweise 32 4-Bit-Zeichen. Für eine Zeichenkette der Länge n wird zunächst ein Hashwert berechnet. Eine Reduktionsfunktion R wandelt diesen Hash wieder in eine Zeichenkette der Länge n um. Hash- und Reduktionsfunktion können danach abwechselnd beliebig oft angewendet werden. Die Folge der Zwischenergebnisse bildet eine Kette; gespeichert werden Anfangs- und Endwert. Wird dieser Vorgang x-mal mit verschiedenen Ausgangswerten durchgeführt, entsteht eine universelle Rainbow Table.

Beim Erstellen muss verhindert werden, dass ein Kennwort, das bereits in einer Kette vorkommt, erneut als Startkennwort verwendet wird. Gleichzeitig sollen alle möglichen Kennwörter in den Ketten vorkommen. Die Kettenlänge entspricht der Anzahl der Iterationen. Je länger die Ketten sind, desto kleiner wird die Tabelle. Bei nur einer Iteration enthält sie im einfachsten Fall alle Kennwort-Hash-Paare.

Die Suche nach einem Passwort erfolgt in zwei Stufen. Zuerst wird der gesuchte Hashwert wiederholt durch Reduktions- und Hashfunktion geführt, bis ein erzeugter Hash in der Spalte der letzten Kettenglieder erscheint. Dadurch wird eine passende Kette auf der „rechten Seite“ der Tabelle gefunden. Anschließend wird die Kette vom gespeicherten Startkennwort aus neu berechnet, bis der gegebene Hashwert erreicht ist. Das Kennwort unmittelbar vor diesem Hashwert ist das gesuchte Kennwort.

Reduktion, Aufwand und typische Anwendung

Die Reduktionsfunktion verkürzt einen Hashwert auf n Zeichen und erzeugt daraus ein neues mögliches Klartextkennwort. Unterschiedliche Ausgangszeichenfolgen können denselben Hashwert erzeugen; dies nennt man eine Kollision. Um solche Zusammenstöße und Wiederholungen zu begrenzen, werden verschiedene Reduktionsfunktionen R₁, …, Rₖ periodisch angewendet. Bei schlecht programmierten oder trivialen Reduktionsfunktionen entstehen nach wenigen Läufen Kollisionen und interne Schleifen. Dann sind viele berechnete Elemente nicht eindeutig unterscheidbar und das Verfahren kann versagen.

Das Verfahren spart Speicher, weil eine Kette mit n Elementen durch ihren Start- und Endwert repräsentiert wird. So lassen sich n−1 Hashes später neu berechnen. Bei einer Kettenlänge von n = 10.000 sind 9.999 Hash-Berechnungen nötig, um den Ursprungstext eines Hashes zu finden. Die Erfolgswahrscheinlichkeit hängt von der Qualität der Reduktionsfunktionen und den Parametern der Tabelle ab. Reduziert eine Funktion beispielsweise nur auf Zahlen, kann der Klartext „Domino“ nicht gefunden werden. Reduziert sie auf sieben Stellen, werden 6-stellige Klartexte nicht berechnet.

Im Beispiel wird der MD5-Hash 97fae39bfd56c35b6c860aa468c258e0 in Hexadezimaldarstellung gesucht. Er gehört zur Zeichenfolge „Domino“. Eine vollständige Datenbank mit allen Hashes und Klartexten wäre bei 64 möglichen Zeichen [A-Za-z0-9./] und sechs Stellen sehr groß: Es gibt 64⁶ Variationen. Für jedes Paar würden 16 Byte für den Hash und 6 Byte für den Plaintext benötigt; insgesamt wären dies etwa 1,4 Terabyte. Rainbow Tables verringern diese Datenmenge, indem sie nur Kettenanfänge und -enden speichern.

Perfekte und nicht perfekte Tabellen

In einer perfekten Rainbow Table kommt kein Passwort innerhalb der Ketten doppelt vor. Deshalb benötigt sie die geringste Anzahl von Ketten, um alle Passwörter darzustellen. Ihre Erzeugung erfordert jedoch mehr Berechnungsaufwand.

In einer nicht perfekten Rainbow Table treten redundante Passwörter in den Ketten auf. Sie lässt sich schneller erzeugen, benötigt anschließend aber mehr Speicherplatz als eine perfekte Rainbow Table.

Schutzmaßnahmen gegen Rainbow Tables

Rainbow Tables greifen vor allem dann, wenn Passwörter mit einer kryptographischen Hashfunktion ohne zusätzliche Zufallswerte gespeichert wurden. Mehrere Maßnahmen machen ihre Erstellung oder Verwendung weniger wirtschaftlich.

Längere Kennwörter vergrößern den Umfang einer benötigten Rainbow Table. Ab einer bestimmten Länge ist ihre Berechnung wegen der Generierungsdauer, der Stromkosten und des Speicherbedarfs nicht mehr wirtschaftlich. Lange Kennwörter können beispielsweise als Sätze statt als einzelne Wörter verwendet werden.

Ein Salt ist ein im Idealfall zufällig erzeugter Wert, der vor dem Hashen an das Passwort angehängt wird. Das Salt wird zusammen mit dem Hashwert gespeichert und ist daher kein Geheimnis. Bei dem Passwort 123456 und dem Salt ABC wird beispielsweise 123456ABC gehasht. Ein festes Salt allein verhindert Rainbow Tables nicht wesentlich, weil eine eigene Tabelle für dieses bekannte Salt erstellt werden kann. Entscheidend ist, dass das Salt für jedes Passwort zufällig neu erzeugt wird. Eine Tabelle für ABC hilft dann bei XYZ nicht; für jedes weitere Salt müsste eine neue Tabelle erstellt werden. Dadurch wird das Verfahren bei vielen möglichen Salts unwirtschaftlich oder technisch nicht realisierbar. Salts schützen jedoch keine kurzen Passwörter grundsätzlich, sondern erhöhen beim Vorliegen mehrerer Passwörter den Aufwand des Brute-Force-Angriffs.

Der Aufwand steigt weiter, wenn ein Passwort mehrfach gehasht wird. Üblich sind mehrere tausend Iterationen. Erst die Kombination aus Salts und Iterationen bietet eine gewisse Resistenz gegen typische Angriffsmethoden: Das Salt erschwert oder verhindert die wirtschaftliche Erstellung von Tabellen, die Iterationen verlangsamen Brute-Force-Angriffe. MD5 (crypt) verwendet Salts mit einer Länge von 12 bis 48 Bit und 1000 Iterationen. Rainbow Tables und reines Brute Forcing sind dafür unter realen Bedingungen unwirtschaftlich.

Beim Pepper-Verfahren wird das Passwort vor der Hashberechnung mit einer geheimen Zeichenfolge kombiniert. Der Pepper wird nicht in der Datenbank gespeichert, sondern an einem möglichst sicheren Ort hinterlegt und gilt für alle Passwörter. Gelangt ein Angreifer an den Pepper, etwa durch Kontrolle über den Server, bietet er keinen Vorteil mehr. Hat er dagegen nur Zugriff auf die Datenbank, kennt er zwar die Hashwerte, diese beruhen aber auf langen Kombinationen aus Passwort und starkem Pepper. Da solche Kombinationen in keinem Wörterbuch stehen, ist ein Wörterbuchangriff sinnlos.