Bei einer Rainbow Table (engl. für Regenbogentabelle) handelt es sich um eine von Philippe Oechslin entwickelte Datenstruktur. Diese dient der schnellen und speichereffizienten Suche nach der ursprünglichen Zeichenfolge (meist ein Passwort) für einen gegebenen Hashwert. Und auch wenn der Speicherbedarf höher ist, so ist die Suche über eine Rainbow Table schneller als bei der Brute-Force-Methode.
Verwendet werden Rainbow Tables bei Penetrationstests, in der IT-Forensik und bei der Wiederherstellung und dem Hacken von Passwörtern. Möglich ist das aber nur, wenn eine Hashfunktion verwendet wird, bei der kein Salting stattfindet.
Ausgangspunkt einer Rainbow Table ist dabei immer ein erstes Passwort. Dieses Passwort wird mit einer vorher gewählten Hashfunktion in einen Hashwert umgewandelt. Anschließend wird der Hashwert durch eine Reduktionsfunktion geleitet, um im Ergebnis ein weiteres komplett neues Klartextpasswort zu erhalten, was wiederum in einen Hashwert umgewandelt wird.
So wird zum Beispiel aus dem Passwort “ABCXYZ123$” der Hashwert “zl9wkb2”. Aus dem Hashwert “zl9wkb2” wird mit der Hilfe der Reduktionsfunktion das Klartextpasswort “Sommer2020!” und aus diesem der Hashwert “2dh7wm1”.
Dieser Vorgang findet viele Male statt, sodass am Ende eine lange Kette entsteht, wo sich Passwörter und Hashwerte abwechseln. Gespeichert werden in der finalen Tabelle aber nur das erste Passwort und der letzte Hashwert. Diese beiden Werte und die verwendete Reduktionsfunktion reichen aus, um alle anderen Werte innerhalb der Kette zu ermitteln.
Eine Tabelle besteht dabei aus mehreren Ketten. Damit es hierbei zu keiner Kollision kommt ist es wichtig, dass ein Start-Passwort in keiner anderen Kette innerhalb der Tabelle vorkommt. Dennoch sollten alle möglichen Passwörter berücksichtigt werden. Um für bessere Ergebnisse zu sorgen, kann bei jedem Schritt eine andere Reduktionsfunktion verwendet werden. Da diese oft mit unterschiedlichen Farben dargestellt werden, ähnelt eine fertige Tabelle oft einem bunten Regenbogen, daher der Begriff Rainbow Table.
Liegt nun ein Hashwert vor für den das Passwort ermittelt werden soll, so wird zuerst geschaut, ob der Hashwert bereits als Wert in der finalen Tabelle gespeichert wurde. Ist das der Fall, so müssen nur die Wiederholungen der Kette “Hash -> Reduktion -> Hash -> Reduktion …” so lange durchgeführt werden, bis man am Ende der Kette angelangt ist, wo das Klartextpasswort an vorletzter Stelle vor dem Hashwert steht.
Lässt sich der Hashwert nicht direkt in der Rainbow Table finden, so beginnt man mit der Reduktion des Hashwerts, mit der auch die Ketten erstellt wurden. Das Ergebnis wird erneut gehasht und der Vorgang so lange wiederholt, bis der Hashwert mit einem der Hashwerte in der Tabelle übereinstimmt, um die entsprechende Kette zu finden. Anschließend beginnt man am Anfang der Kette und führt nun abwechselnd die Hash- und Redukionsfunktion durch, bis der gesuchte Hashwert und somit das Passwort gefunden wurde.
Rainbow Tables können dabei mehrere Hundert Gigabyte groß sein, je nach Länge einer Kette, bzw. Anzahl der Iterationen. Dabei gilt, je länger die Iterationen gewählt werden, desto kleiner ist die dabei entstehende Tabelle. Am einfachsten ist es, wenn die Anzahl der Iterationen gleich 1 ist. In diesem Fall steht in jeder Zeile ein Kennwort mit dem dazugehörigen Hashwert, was bei Milliarden von möglichen Passwörtern, entsprechend viele Zeilen bedeuten.