Was sind Rainbow Tables?

Was wie ein lustiges Kin­der­spiel­zeug klingt, ist in Wahrheit ein mächtiges Werkzeug, um Pass­wör­ter zu ent­schlüs­seln. Eine relativ große Gruppe von Menschen auf beiden Seiten der Legalität setzt viel Energie in das Cracken von Pass­wör­tern – weil sie sich durch den kri­mi­nel­len Vorgang Profit ver­spre­chen oder weil sie Experten sind, die Si­cher­heits­stan­dards re­gel­mä­ßig auf Wirk­sam­keit über­prü­fen müssen. Re­gen­bo­gen­ta­bel­len machen es unter be­stimm­ten Ge­ge­ben­hei­ten möglich, Pass­wör­ter binnen Sekunden her­aus­zu­fin­den.

Auch wenn Sie keine kri­mi­nel­len Ma­chen­schaf­ten im Schilde führen, lohnt es, das Prinzip zu verstehen. Mit dem Wissen im Hin­ter­kopf verstehen Sie als Nutzer besser, warum komplexe Pass­wör­ter nötig sind und was Sie als Anbieter eines Web­an­ge­bots beachten müssen, um Ihre Pass­wör­ter ab­zu­si­chern.

Pass­wör­ter werden heut­zu­ta­ge (hof­fent­lich) nicht mehr un­ver­schlüs­selt im Internet ge­spei­chert. Wenn Nutzer einer In­ter­net­platt­form ein Passwort für ihr Konto festlegen, taucht die Zei­chen­fol­ge nicht im Klartext in ir­gend­ei­ner 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 Be­nut­zer­kon­ten jedes einzelnen Users ein­drin­gen. Für E-Commerce, On­line­ban­king oder E-Go­vern­ment-Dienste wären das fatale Fälle. Statt­des­sen verwenden die On­line­ser­vices un­ter­schied­li­che kryp­to­gra­fi­sche Me­cha­nis­men, um die Pass­wör­ter der Nutzer zu ver­schlüs­seln: In den Da­ten­ban­ken selbst taucht nur noch ein Hashwert des Pass­wor­tes auf. Aus dem Hashwert kann – selbst wenn man die Krypto-Funktion kennt – nicht das Passwort direkt ermittelt werden. Es gibt keine Mög­lich­keit, den Vorgang zu­rück­zu­rech­nen. Statt­des­sen verwenden Hacker z. B. Brute-Force-Attacken: Hierbei rät ein Com­pu­ter­pro­gramm prin­zi­pi­ell so lange, bis es die richtige Zei­chen­fol­ge gefunden hat. Diese Methode kann auch mit Passwort-Wör­ter­bü­chern kom­bi­niert werden. In diesen Dateien – die man über das Internet beziehen kann – finden sich zahl­rei­che Pass­wör­ter, die entweder sehr beliebt sind oder bei einem vor­he­ri­gen Angriff auf ein anderes System erbeutet wurden. So sparen Hacker Zeit bei der Ent­schlüs­se­lung: Sie probieren zunächst alle Pass­wör­ter im Wör­ter­buch durch. Abhängig von der Kom­ple­xi­tät der Pass­wör­ter (Länge und ver­wen­de­te Zei­chen­ar­ten) kann dies aber einige Zeit und Re­chen­ka­pa­zi­tä­ten kosten.

Rainbow Tables gehen noch einen Schritt weiter als Passwort-Wör­ter­bü­cher: Auch diese Tabellen findet man im Internet und kann sie zum Knacken von Pass­wör­tern verwenden. In diesen Dateien, die teilweise mehrere Hundert Gigabyte groß sein können, liegen passend zum ver­wen­de­ten Ver­schlüs­se­lungs­al­go­rith­mus Pass­wör­ter zusammen mit ihren Hash­wer­ten. Al­ler­dings nicht komplett: Statt­des­sen erzeugt man bestimmte Ketten, aus der die ei­gent­li­chen Werte leicht berechnet werden können, und reduziert so den Spei­cher­be­darf der immer noch sehr großen Tabellen. Mit den Re­gen­bo­gen­ta­bel­len lassen sich also Hashwerte, die man in einer Datenbank gefunden hat, zu ihren Pass­wör­tern im Klartext zu ordnen.

Um zu verstehen, wie Re­gen­bo­gen­ta­bel­len funk­tio­nie­ren, muss man sich zumindest die grund­le­gen­de Funk­ti­ons­wei­se von Krypto-Al­go­rith­men vor Augen führen. Dann fällt es auch leichter, den Vorteil der vor­ge­fer­tig­ten Tabellen und damit auch den Time-Memory Tradeoff zu verstehen.

Seitdem man kryp­to­gra­fi­sche Hash­funk­tio­nen bei der Ver­schlüs­se­lung einsetzt, haben sich die ent­spre­chen­den Al­go­rith­men immer wieder verändert. Standards, die noch vor 10 Jahren als un­knack­bar galten, sieht man heut­zu­ta­ge als grobe Verstöße gegen die Si­cher­heit an. Allen gemein ist al­ler­dings, dass der zu ver­schlüs­seln­de Inhalt durch Al­go­rith­men läuft und am Ende ein Hashwert erzeugt wird. Dieser Hashwert ist in der Regel eine he­xa­de­zi­ma­le Zahl mit einer be­stimm­ten Länge. Ganz egal, wie lang der ur­sprüng­li­che Inhalt ist, am Ende kommt z. B. immer ein 128-bit-Hashwert heraus. Drei Ei­gen­schaf­ten sind für die Ver­schlüs­se­lung ganz ent­schei­dend:

1. Die gleiche Eingabe erzeugt immer den gleichen Hashwert: Nur so kann der Wert als Prüfsumme funk­tio­nie­ren. Ist das ein­ge­ge­be­ne Passwort identisch mit dem in der Datenbank ge­spei­cher­ten? Nur wenn beide Hashwerte gleich sind, darf das System den Zugang gewähren.
2. Ein Hashwert sollte immer einmalig sein: Un­ter­schied­li­che Eingaben dürfen nicht den gleichen Hashwert erzeugen. Nur so kann die Funktion si­cher­stel­len, dass auch das richtige Passwort ein­ge­ge­ben wurde. Da die Anzahl der möglichen Hashwerte begrenzt ist, die Anzahl der möglichen Eingaben al­ler­dings nicht, können solche Kol­li­sio­nen nicht aus­ge­schlos­sen werden. Moderne Hash­funk­tio­nen und Hashes mit einer aus­rei­chen­den Länge mi­ni­mie­ren das Risiko aber so gut es geht.
3. Hashwerte lassen sich nicht zu­rück­rech­nen: Aus dem Hashwert selbst kann niemals der Ori­gi­nal­in­halt ab­ge­lei­tet werden. Deshalb kann man Hashwerte auch nicht ent­schlüs­seln, wie manchmal unscharf behauptet wird. Statt­des­sen kann man die Hashwerte nur nach­voll­zie­hen.
4. Hash­funk­tio­nen müssen recht komplex sein – aber nicht zu sehr: Um Si­cher­heit zu ge­währ­leis­ten, darf ein Al­go­rith­mus nicht zu schnell arbeiten, denn das würde auch An­grei­fern die Arbeit er­leich­tern. Zu komplex sollte die Um­wand­lung aber auch nicht sein, denn sie muss schließ­lich auch in der Praxis an­ge­wen­det werden.

Die in Re­gen­bo­gen­ta­bel­len ent­hal­te­nen Hashwerte werden nicht erst bei einem Angriff erstellt, sondern bereits im Vorfeld: Angreifer können die Rainbow Tables beziehen und zum Her­aus­fin­den von Pass­wör­tern nutzen. Diese Dateien sind al­ler­dings sehr groß. Damit der benötigte Spei­cher­platz nicht ausufert, verwenden Rainbow Tables daher eine Re­duk­ti­ons­funk­ti­on: Diese Funk­tio­nen wandeln den Hashwert in einen Plain-Text um. Wichtig: Die Re­duk­ti­ons­funk­ti­on macht den Hashwert nicht rück­gän­gig, gibt also nicht den ur­sprüng­li­chen 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 Re­gen­bo­gen­ta­bel­le 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 In­for­ma­tio­nen und unter Be­rück­sich­ti­gung der ver­wen­de­ten Re­duk­ti­ons­funk­tio­nen lassen sich auch alle anderen Werte ermitteln. Der zu knackende Hashwert wird nach den gleichen Regeln immer wieder reduziert und gehasht, wobei man jedes Zwi­schen­er­geb­nis mit den in der Tabelle vor­han­de­nen Werten abgleicht.

Die Her­aus­for­de­rung beim Erstellen der Tabelle liegt darin, dass die Aus­gangs­in­hal­te, die den Beginn einer neuen Kette dar­stel­len, nicht bereits als Plain-Text in einer vor­an­ge­gan­ge­nen Kette auf­ge­taucht sein dürfen. Mithilfe dieser Technik lässt sich die Größe solcher Tabellen extrem ver­klei­nern, und doch haben sie noch einen Umfang von mehreren Hundert Gigabyte.

Von einem Time-Memory Tradeoff spricht man grund­sätz­lich, wenn man eine längere Laufzeit zugunsten von weniger Spei­cher­be­darf in Kauf nimmt – oder an­ders­her­um. Eine Brute-Force-Attacke belegt sehr wenig Spei­cher­platz, da die kryp­to­gra­fi­schen Be­rech­nun­gen bei jedem Angriff von Neuem durch­ge­führt werden. Eine Tabelle hingegen, in der Mil­li­ar­den von Pass­wör­tern zusammen mit ihren Hash­wer­ten vertreten sind, belegt enorm viel Spei­cher­platz, kann dafür aber die Ent­schlüs­se­lung sehr schnell durch­füh­ren. Rainbow Tables stellen einen Kom­pro­miss aus beidem dar: Das Prinzip führt zwar auch Echt­zeit­be­rech­nun­gen durch, aber in einem ge­rin­ge­ren Maße und spart dadurch im Vergleich zu voll­stän­di­gen Tabellen deutlich an Spei­cher­platz.

Die Aus­gangs­si­tua­ti­on: Man besitzt einen be­stimm­ten Hashwert und möchte das ei­gent­li­che Passwort dahinter erfahren. Zunächst durch­sucht 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 Wie­der­ho­lun­gen der Kette nach­zu­voll­zie­hen und erhält so das ge­wünsch­te 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 durch­läuft wiederum die Hash­funk­ti­on. Dies wie­der­holt man so lange, bis man den Hashwert in einem der Endpunkte wie­der­fin­det. Dies gibt einem aber noch nicht das gesuchte Passwort. Al­ler­dings hat man nun die ent­spre­chen­de Kette gefunden, in der der Hashwert steckt. Deshalb beginnt man nun am An­fangs­punkt der Kette und führt erneut ab­wech­selnd die Re­duk­tio­nen 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 Re­gen­bö­gen zu tun haben. In der Praxis verwendet man nicht nur eine Re­duk­ti­ons­funk­ti­on, sondern in jedem Schritt eine andere. Dies sorgt für ein besseres Ergebnis bei der Reduktion und vermeidet, dass sich Hashwerte in der Tabelle wie­der­ho­len, hat al­ler­dings den Nachteil, dass das Finden von Kom­bi­na­tio­nen von Hash­wer­ten und Pass­wör­tern in den Ketten etwas komplexer ist.

So müssen die Re­duk­tio­nen der Reihe nach durch­ge­gan­gen werden: Geht man davon aus, dass man die Kette mit den Re­duk­tio­nen 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 un­ter­schied­li­chen Re­duk­ti­ons­funk­tio­nen mit Farben markieren, was bei ent­spre­chend vielen Ite­ra­tio­nen zu einem bunten Re­gen­bo­gen führen kann, woraus sich der Name ergibt.

Zur Erklärung: Das ein­ge­ge­be­ne Passwort ist k. Bei m handelt es sich in diesem Fall um einen be­lie­bi­gen Mul­ti­pli­ka­tor (in diesem Beispiel 2000). Für A setzt man in der Regel den Goldenen Schnitt ( ) an. Modulo (mod) ex­tra­hiert den Rest einer Division, die in dieser Funktion durch 1 durch­ge­führt wird. Die Gauß­klam­mern 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 Re­gen­bo­gen­ta­bel­le zu dieser Hash­funk­ti­on müssen nun Re­duk­ti­ons­funk­tio­nen wirken. Eine sehr einfache Mög­lich­keit, den Hashwert zu re­du­zie­ren, ist bei­spiels­wei­se, nur die letzten beiden Ziffern zu verwenden. So ist im Fall des Passworts 78 und dem zu­ge­hö­ri­gen Hashwert 0408 die Reduktion 08. Hiervon bildet man erneut den Hashwert mithilfe der vor­ge­stell­ten Funktion und so weiter.

Die Häu­fig­keit der Wie­der­ho­lun­gen kann frei gewählt werden. Je häufiger man eine Wie­der­ho­lung macht, umso weniger Spei­cher­platz braucht die Rainbow Table – dafür steigt al­ler­dings die Be­ar­bei­tungs­zeit. In diesem Beispiel werden wir die Reduktion dreimal durch­füh­ren.

Die obige Tabelle zeigt die kom­plet­ten Ketten mit den Er­geb­nis­sen der Hash- und Re­duk­ti­ons­funk­tio­nen. Ziel einer Re­gen­bo­gen­ta­bel­le ist es al­ler­dings, 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 er­schlie­ß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 Re­gen­bo­gen­ta­bel­le durch­su­chen und fest­stel­len, dass der Wert nicht in der Tabelle auftaucht, sondern sich in einer Kette verbirgt. Demnach muss man nun eine Reduktion des Wertes durch­füh­ren, was 88 ergibt. Auch dieser Wert ist nicht Teil der Tabelle, also berechnet man erneut den Hashwert (0768) und die Reduktion (68). Der da­zu­ge­hö­ri­ge 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 Aus­gangs­punkt für die nächste Be­rech­nung: 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 ver­stan­den hat, wie Angreifer unter Zu­hil­fe­nah­me einer Re­gen­bo­gen­ta­bel­le in Nut­zer­kon­ten ein­drin­gen können, dem sollte klar sein, dass man geeignete Ab­wehr­me­cha­nis­men einsetzen muss. Sowohl Nutzer als auch die Ver­ant­wort­li­chen der Web­an­ge­bo­te können Maßnahmen ergreifen, um solche Attacken zu un­ter­bin­den oder zumindest zu er­schwe­ren.

Für Nutzer selbst gilt generell: Pass­wör­ter sollten möglichst lang sein und sowohl Groß­buch­sta­ben, Klein­buch­sta­ben, Ziffern und andere Zeichen enthalten – dies hilft gegen Brute-Force-Attacken und Re­gen­bo­gen­ta­bel­len, da die Ent­schlüs­se­lung zu aufwendig wird. Mit der Länge des Passworts steigt auch die Größe der be­nö­tig­ten Tabelle ex­po­nen­ti­ell. Außerdem ist es ratsam, keine wirk­li­chen Wörter zu verwenden, sondern zufällige Zei­chen­ket­ten, um Angriffen auf Basis von Wör­ter­bü­chern vor­zu­beu­gen. Dabei können Passwort-Manager helfen.

Ganz wichtig ist aber auch – ganz un­ab­hän­gig davon, welche Form von Attacken die Angreifer einsetzen – Pass­wör­ter nicht mehr als einmal zu verwenden: Hat jemand es einmal, geschafft eine Datenbank zu kor­rum­pie­ren, die Pass­wör­ter zu ent­schlüs­seln und per­sön­li­che Daten ab­zu­grei­fen, ist es ein Leichtes, alle weiteren Konten im Internet mit genau diesem Passwort aus­zu­pro­bie­ren.

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 Da­ten­ban­ken mit den Hash­wer­ten zu lassen. Dass das einfacher gesagt als getan ist, beweisen die vielen Einbrüche auch auf Servern von großen Un­ter­neh­men. Deshalb muss man zwangs­läu­fig den Hashwert sichern. Das beginnt damit, dass man keine ver­al­te­ten Al­go­rith­men verwendet.

Sowohl MD5 als auch SHA-1 gelten schon seit längerem als unsicher und ent­spre­chen­de Re­gen­bo­gen­ta­bel­len sind einfach im Internet zu finden. Mit diesen lassen sich Pass­wör­ter, die so gehasht wurden, binnen Sekunden her­aus­fin­den. Deshalb ist es un­er­läss­lich, dass man sich ständig in­for­miert, ob es neue Al­go­rith­men gibt bzw. wie sicher die ver­wen­de­te Hash­funk­ti­on noch ist. SHA-2 und so auch dessen be­kann­tes­te Variante SHA-256 gelten immer noch als sicher, in­zwi­schen ist aber auch SHA-3 verfügbar, was noch länger Si­cher­heit ver­spricht.

Um das Ent­schlüs­seln durch Re­gen­bo­gen­ta­bel­len um einiges schwie­ri­ger zu gestalten, verwendet man heut­zu­ta­ge das so­ge­nann­te Salt: Wenn ein Nutzer ein Passwort festlegt, erstellt das System zu­sätz­lich dazu einen zu­fäl­li­gen Wert, das Salt. Dieser Wert fließt zusammen mit dem Passwort in die Hash­funk­ti­on und erzeugt so einen anderen Wert, als das Passwort allein.

Salt und Hashwert liegen gemeinsam in der Datenbank. Dieser Umstand wirkt ver­wir­rend: Angreifer, die den Inhalt der Datenbank erhalten, haben somit den Nut­zer­na­men, den Hashwert und den da­zu­ge­hö­ri­gen Salt. Tat­säch­lich werden Brute-Force- und Wör­ter­buch-Attacken so nicht vermieden, aber gerade gegen Rainbow Tables hilft die Zu­satz­maß­nah­me. Eine solche Tabelle ist ja im Vorfeld erstellt, auf der Basis eines Hash­al­go­rith­mus und un­ab­hän­gig von der Datenbank, die man benutzt. Die Salts können also nicht in Re­gen­bo­gen­ta­bel­len 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 voll­kom­men 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 ver­hin­dert 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 ver­schie­de­ne Dienste benutzen. Der ge­spei­cher­te 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ör­ter­bü­chern. Auch der Pepper ist eine zufällige Zei­chen­fol­ge, die – am besten in Kom­bi­na­ti­on 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 Zei­chen­ket­te für alle Pass­wör­ter 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 iden­ti­schen Hash­wer­ten führt. Dem­entspre­chend sollten Ad­mi­nis­tra­to­ren eine Kom­bi­na­ti­on aus Salt und Pepper wählen.