Was sind Rainbow Tables?

Was wie ein lustiges Kinderspielzeug klingt, ist in Wahrheit ein mächtiges Werkzeug, um Passwörter zu entschlüsseln. Eine relativ große Gruppe von Menschen auf beiden Seiten der Legalität setzt viel Energie in das Cracken von Passwörtern – weil sie sich durch den kriminellen Vorgang Profit versprechen oder weil sie Experten sind, die Sicherheitsstandards regelmäßig auf Wirksamkeit überprüfen müssen. Regenbogentabellen machen es unter bestimmten Gegebenheiten möglich, Passwörter binnen Sekunden herauszufinden.

Auch wenn Sie keine kriminellen Machenschaften im Schilde führen, lohnt es, das Prinzip zu verstehen. Mit dem Wissen im Hinterkopf verstehen Sie als Nutzer besser, warum komplexe Passwörter nötig sind und was Sie als Anbieter eines Webangebots beachten müssen, um Ihre Passwörter abzusichern.

Passwörter werden heutzutage (hoffentlich) nicht mehr unverschlüsselt im Internet gespeichert. Wenn Nutzer einer Internetplattform ein Passwort für ihr Konto festlegen, taucht die Zeichenfolge nicht im Klartext in irgendeiner Datenbank auf einem Server auf. Dieses Verfahren wäre viel zu unsicher: Ein Hacker müsste nur Zugang zu der Datenbank erlangen und könnte sofort in die Benutzerkonten jedes einzelnen Users eindringen. Für E-Commerce, Onlinebanking oder E-Government-Dienste wären das fatale Fälle. Stattdessen verwenden die Onlineservices unterschiedliche kryptografische Mechanismen, um die Passwörter der Nutzer zu verschlüsseln: In den Datenbanken selbst taucht nur noch ein Hashwert des Passwortes auf. Aus dem Hashwert kann – selbst wenn man die Krypto-Funktion kennt – nicht das Passwort direkt ermittelt werden. Es gibt keine Möglichkeit, den Vorgang zurückzurechnen. Stattdessen verwenden Hacker z. B. Brute-Force-Attacken: Hierbei rät ein Computerprogramm prinzipiell so lange, bis es die richtige Zeichenfolge gefunden hat. Diese Methode kann auch mit Passwort-Wörterbüchern kombiniert werden. In diesen Dateien – die man über das Internet beziehen kann – finden sich zahlreiche Passwörter, die entweder sehr beliebt sind oder bei einem vorherigen Angriff auf ein anderes System erbeutet wurden. So sparen Hacker Zeit bei der Entschlüsselung: Sie probieren zunächst alle Passwörter im Wörterbuch durch. Abhängig von der Komplexität der Passwörter (Länge und verwendete Zeichenarten) kann dies aber einige Zeit und Rechenkapazitäten kosten.

Rainbow Tables gehen noch einen Schritt weiter als Passwort-Wörterbücher: Auch diese Tabellen findet man im Internet und kann sie zum Knacken von Passwörtern verwenden. In diesen Dateien, die teilweise mehrere Hundert Gigabyte groß sein können, liegen passend zum verwendeten Verschlüsselungsalgorithmus Passwörter zusammen mit ihren Hashwerten. Allerdings nicht komplett: Stattdessen erzeugt man bestimmte Ketten, aus der die eigentlichen Werte leicht berechnet werden können, und reduziert so den Speicherbedarf der immer noch sehr großen Tabellen. Mit den Regenbogentabellen lassen sich also Hashwerte, die man in einer Datenbank gefunden hat, zu ihren Passwörtern im Klartext zu ordnen.

Um zu verstehen, wie Regenbogentabellen funktionieren, muss man sich zumindest die grundlegende Funktionsweise von Krypto-Algorithmen vor Augen führen. Dann fällt es auch leichter, den Vorteil der vorgefertigten Tabellen und damit auch den Time-Memory Tradeoff zu verstehen.

Seitdem man kryptografische Hashfunktionen bei der Verschlüsselung einsetzt, haben sich die entsprechenden Algorithmen immer wieder verändert. Standards, die noch vor 10 Jahren als unknackbar galten, sieht man heutzutage als grobe Verstöße gegen die Sicherheit an. Allen gemein ist allerdings, dass der zu verschlüsselnde Inhalt durch Algorithmen läuft und am Ende ein Hashwert erzeugt wird. Dieser Hashwert ist in der Regel eine hexadezimale Zahl mit einer bestimmten Länge. Ganz egal, wie lang der ursprüngliche Inhalt ist, am Ende kommt z. B. immer ein 128-bit-Hashwert heraus. Drei Eigenschaften sind für die Verschlüsselung ganz entscheidend:

1. Die gleiche Eingabe erzeugt immer den gleichen Hashwert: Nur so kann der Wert als Prüfsumme funktionieren. Ist das eingegebene Passwort identisch mit dem in der Datenbank gespeicherten? Nur wenn beide Hashwerte gleich sind, darf das System den Zugang gewähren.
2. Ein Hashwert sollte immer einmalig sein: Unterschiedliche Eingaben dürfen nicht den gleichen Hashwert erzeugen. Nur so kann die Funktion sicherstellen, dass auch das richtige Passwort eingegeben wurde. Da die Anzahl der möglichen Hashwerte begrenzt ist, die Anzahl der möglichen Eingaben allerdings nicht, können solche Kollisionen nicht ausgeschlossen werden. Moderne Hashfunktionen und Hashes mit einer ausreichenden Länge minimieren das Risiko aber so gut es geht.
3. Hashwerte lassen sich nicht zurückrechnen: Aus dem Hashwert selbst kann niemals der Originalinhalt abgeleitet werden. Deshalb kann man Hashwerte auch nicht entschlüsseln, wie manchmal unscharf behauptet wird. Stattdessen kann man die Hashwerte nur nachvollziehen.
4. Hashfunktionen müssen recht komplex sein – aber nicht zu sehr: Um Sicherheit zu gewährleisten, darf ein Algorithmus nicht zu schnell arbeiten, denn das würde auch Angreifern die Arbeit erleichtern. Zu komplex sollte die Umwandlung aber auch nicht sein, denn sie muss schließlich auch in der Praxis angewendet werden.

Die in Regenbogentabellen enthaltenen Hashwerte werden nicht erst bei einem Angriff erstellt, sondern bereits im Vorfeld: Angreifer können die Rainbow Tables beziehen und zum Herausfinden von Passwörtern nutzen. Diese Dateien sind allerdings sehr groß. Damit der benötigte Speicherplatz nicht ausufert, verwenden Rainbow Tables daher eine Reduktionsfunktion: Diese Funktionen wandeln den Hashwert in einen Plain-Text um. Wichtig: Die Reduktionsfunktion macht den Hashwert nicht rückgängig, gibt also nicht den ursprünglichen Plain-Text (z. B. das Passwort) aus – denn das ist nicht möglich –, sondern einen komplett neuen.

Aus diesem Text erzeugt man erneut einen Hashwert. In einer Regenbogentabelle findet dies nicht nur einmal statt, sondern vielmals, sodass eine Kette entsteht. In der finalen Tabelle tauchen aber schließlich nur das erste Passwort und der letzte Hashwert einer Kette auf. Auf Basis dieser Informationen und unter Berücksichtigung der verwendeten Reduktionsfunktionen lassen sich auch alle anderen Werte ermitteln. Der zu knackende Hashwert wird nach den gleichen Regeln immer wieder reduziert und gehasht, wobei man jedes Zwischenergebnis mit den in der Tabelle vorhandenen Werten abgleicht.

Die Herausforderung beim Erstellen der Tabelle liegt darin, dass die Ausgangsinhalte, die den Beginn einer neuen Kette darstellen, nicht bereits als Plain-Text in einer vorangegangenen Kette aufgetaucht sein dürfen. Mithilfe dieser Technik lässt sich die Größe solcher Tabellen extrem verkleinern, und doch haben sie noch einen Umfang von mehreren Hundert Gigabyte.

Von einem Time-Memory Tradeoff spricht man grundsätzlich, wenn man eine längere Laufzeit zugunsten von weniger Speicherbedarf in Kauf nimmt – oder andersherum. Eine Brute-Force-Attacke belegt sehr wenig Speicherplatz, da die kryptografischen Berechnungen bei jedem Angriff von Neuem durchgeführt werden. Eine Tabelle hingegen, in der Milliarden von Passwörtern zusammen mit ihren Hashwerten vertreten sind, belegt enorm viel Speicherplatz, kann dafür aber die Entschlüsselung sehr schnell durchführen. Rainbow Tables stellen einen Kompromiss aus beidem dar: Das Prinzip führt zwar auch Echtzeitberechnungen durch, aber in einem geringeren Maße und spart dadurch im Vergleich zu vollständigen Tabellen deutlich an Speicherplatz.

Die Ausgangssituation: Man besitzt einen bestimmten Hashwert und möchte das eigentliche Passwort dahinter erfahren. Zunächst durchsucht man die Liste nach diesem Hashwert. Findet man ihn im Anfang oder im Ende einer Kette, ist das Passwort relativ schnell gefunden, denn nun braucht man nur die Wiederholungen der Kette nachzuvollziehen und erhält so das gewünschte Ergebnis. Aber was passiert, wenn man den Hashwert nicht in der Tabelle findet?

In diesem Fall beginnt man mit einer Reduktion des Hashwerts, mit der gleichen Funktion, mit der auch die Ketten erstellt wurden. Das Ergebnis durchläuft wiederum die Hashfunktion. Dies wiederholt man so lange, bis man den Hashwert in einem der Endpunkte wiederfindet. Dies gibt einem aber noch nicht das gesuchte Passwort. Allerdings hat man nun die entsprechende Kette gefunden, in der der Hashwert steckt. Deshalb beginnt man nun am Anfangspunkt der Kette und führt erneut abwechselnd die Reduktionen und das Hashing durch, bis man zum gesuchten Hashwert gelangt und damit auch zum Klartext des Passworts.

Am Ende mag man sich doch fragen, was diese Tabellen nun mit Regenbögen zu tun haben. In der Praxis verwendet man nicht nur eine Reduktionsfunktion, sondern in jedem Schritt eine andere. Dies sorgt für ein besseres Ergebnis bei der Reduktion und vermeidet, dass sich Hashwerte in der Tabelle wiederholen, hat allerdings den Nachteil, dass das Finden von Kombinationen von Hashwerten und Passwörtern in den Ketten etwas komplexer ist.

So müssen die Reduktionen der Reihe nach durchgegangen werden: Geht man davon aus, dass man die Kette mit den Reduktionen R₁, R₂, R₃ gebaut hat, würde man bei der Suche erst mit der Funktion R₃ anfangen. Liefert dies kein Ergebnis, greift man erst zu R₂ und dann zu R₃ und so weiter. Innerhalb der Tabelle lassen sich die unterschiedlichen Reduktionsfunktionen mit Farben markieren, was bei entsprechend vielen Iterationen zu einem bunten Regenbogen führen kann, woraus sich der Name ergibt.

Zur Erklärung: Das eingegebene Passwort ist k. Bei m handelt es sich in diesem Fall um einen beliebigen Multiplikator (in diesem Beispiel 2000). Für A setzt man in der Regel den Goldenen Schnitt ( ) an. Modulo (mod) extrahiert den Rest einer Division, die in dieser Funktion durch 1 durchgeführt wird. Die Gaußklammern runden am Ende das Ergebnis auf eine ganze Zahl ab, falls notwendig. Das Ergebnis h(k) ist schließlich der Hashwert h zur Eingabe k.

Da unser Hashwert aus vier Stellen besteht, füllen wir am Anfang mit einer 0 auf: 0408.

In einer Regenbogentabelle zu dieser Hashfunktion müssen nun Reduktionsfunktionen wirken. Eine sehr einfache Möglichkeit, den Hashwert zu reduzieren, ist beispielsweise, nur die letzten beiden Ziffern zu verwenden. So ist im Fall des Passworts 78 und dem zugehörigen Hashwert 0408 die Reduktion 08. Hiervon bildet man erneut den Hashwert mithilfe der vorgestellten Funktion und so weiter.

Die Häufigkeit der Wiederholungen kann frei gewählt werden. Je häufiger man eine Wiederholung macht, umso weniger Speicherplatz braucht die Rainbow Table – dafür steigt allerdings die Bearbeitungszeit. In diesem Beispiel werden wir die Reduktion dreimal durchführen.

Die obige Tabelle zeigt die kompletten Ketten mit den Ergebnissen der Hash- und Reduktionsfunktionen. Ziel einer Regenbogentabelle ist es allerdings, den Umfang zu kürzen. Deshalb sind in der fertigen Rainbow Table nur der linke und der rechte Rand der Tabelle enthalten. Alle anderen Werte lassen sich daraus erschließen.

Nun sind nicht mehr alle Hashwerte in der Tabelle vorhanden. Wenn man nun z. B. weiß, dass sich hinter dem Hashwert 1888 ein Passwort verbirgt, würde man nun die erstellte Regenbogentabelle durchsuchen und feststellen, dass der Wert nicht in der Tabelle auftaucht, sondern sich in einer Kette verbirgt. Demnach muss man nun eine Reduktion des Wertes durchführen, was 88 ergibt. Auch dieser Wert ist nicht Teil der Tabelle, also berechnet man erneut den Hashwert (0768) und die Reduktion (68). Der dazugehörige Hashwert 0048 befindet sich in der dritten Zeile. Doch das Passwort in der gleichen Zeile (03) gehört nicht direkt zu dem Hashwert, denn es ist nur der Anfang der Kette.

Aber es liefert den Ausgangspunkt für die nächste Berechnung: Aus 03 berechnet man den Hashwert 1708. Diesen reduziert man zu 08 und bildet erneut den Hashwert: 1888 – der gesuchte Hashwert. Zu diesem Wert gehört also das Passwort 08.

Wer nun verstanden hat, wie Angreifer unter Zuhilfenahme einer Regenbogentabelle in Nutzerkonten eindringen können, dem sollte klar sein, dass man geeignete Abwehrmechanismen einsetzen muss. Sowohl Nutzer als auch die Verantwortlichen der Webangebote können Maßnahmen ergreifen, um solche Attacken zu unterbinden oder zumindest zu erschweren.

Für Nutzer selbst gilt generell: Passwörter sollten möglichst lang sein und sowohl Großbuchstaben, Kleinbuchstaben, Ziffern und andere Zeichen enthalten – dies hilft gegen Brute-Force-Attacken und Regenbogentabellen, da die Entschlüsselung zu aufwendig wird. Mit der Länge des Passworts steigt auch die Größe der benötigten Tabelle exponentiell. Außerdem ist es ratsam, keine wirklichen Wörter zu verwenden, sondern zufällige Zeichenketten, um Angriffen auf Basis von Wörterbüchern vorzubeugen. Dabei können Passwort-Manager helfen.

Ganz wichtig ist aber auch – ganz unabhängig davon, welche Form von Attacken die Angreifer einsetzen – Passwörter nicht mehr als einmal zu verwenden: Hat jemand es einmal, geschafft eine Datenbank zu korrumpieren, die Passwörter zu entschlüsseln und persönliche Daten abzugreifen, ist es ein Leichtes, alle weiteren Konten im Internet mit genau diesem Passwort auszuprobieren.

Aber auch Betreiber von Servern können einiges tun, um ihre Nutzer zu schützen. Im ersten Schritt sollte man natürlich versuchen, Angreifer erst gar nicht an die Datenbanken mit den Hashwerten zu lassen. Dass das einfacher gesagt als getan ist, beweisen die vielen Einbrüche auch auf Servern von großen Unternehmen. Deshalb muss man zwangsläufig den Hashwert sichern. Das beginnt damit, dass man keine veralteten Algorithmen verwendet.

Sowohl MD5 als auch SHA-1 gelten schon seit längerem als unsicher und entsprechende Regenbogentabellen sind einfach im Internet zu finden. Mit diesen lassen sich Passwörter, die so gehasht wurden, binnen Sekunden herausfinden. Deshalb ist es unerlässlich, dass man sich ständig informiert, ob es neue Algorithmen gibt bzw. wie sicher die verwendete Hashfunktion noch ist. SHA-2 und so auch dessen bekannteste Variante SHA-256 gelten immer noch als sicher, inzwischen ist aber auch SHA-3 verfügbar, was noch länger Sicherheit verspricht.

Um das Entschlüsseln durch Regenbogentabellen um einiges schwieriger zu gestalten, verwendet man heutzutage das sogenannte Salt: Wenn ein Nutzer ein Passwort festlegt, erstellt das System zusätzlich dazu einen zufälligen Wert, das Salt. Dieser Wert fließt zusammen mit dem Passwort in die Hashfunktion und erzeugt so einen anderen Wert, als das Passwort allein.

Salt und Hashwert liegen gemeinsam in der Datenbank. Dieser Umstand wirkt verwirrend: Angreifer, die den Inhalt der Datenbank erhalten, haben somit den Nutzernamen, den Hashwert und den dazugehörigen Salt. Tatsächlich werden Brute-Force- und Wörterbuch-Attacken so nicht vermieden, aber gerade gegen Rainbow Tables hilft die Zusatzmaßnahme. Eine solche Tabelle ist ja im Vorfeld erstellt, auf der Basis eines Hashalgorithmus und unabhängig von der Datenbank, die man benutzt. Die Salts können also nicht in Regenbogentabellen enthalten sein, da der Schöpfer der Tabelle den Salt noch nicht kannte.

Ein weiterer Vorteil von Salt ist, dass Nutzer sich diese nicht merken müssen. Daher können sie vollkommen chaotisch sein und vor allem auch sehr lang. Das macht die Hashwerte selbst wiederum so komplex, dass die Arbeit mit ihnen erschwert wird. Außerdem verhindert ein Salt, dass zwei oder mehr Personen das gleiche Passwort eingeben und so auch den gleichen Hashwert in die Datenbank schreiben. Schließlich hilft Salt auch bei dem Problem, dass Nutzer immer wieder das gleiche Passwort für verschiedene Dienste benutzen. Der gespeicherte Hashwert ist aufgrund des Salts bei allen Diensten anders.

Neben Salt gibt es auch noch Pepper: Dieser erschwert wiederum den Angriff mit Brute Force oder Wörterbüchern. Auch der Pepper ist eine zufällige Zeichenfolge, die – am besten in Kombination mit Salt – zusammen mit dem Passwort in den Hashwert einfließt. Im Gegensatz zum Salt speichert man den Pepper nicht zusammen mit den anderen Login-Daten in einer Datenbank, sondern getrennt und an einem möglichst sicheren Ort.

Häufig wird eine feste Zeichenkette für alle Passwörter der Plattform verwendet. Deshalb hilft Pepper nicht gegen die Tatsache, dass mehrere Nutzer das gleiche Passwort besitzen, denn sie verwenden auch den gleichen Pepper, was wiederum zu identischen Hashwerten führt. Dementsprechend sollten Administratoren eine Kombination aus Salt und Pepper wählen.