Rainbowtables

Bei einer Rainbow-Table handelt es sich um ein vorberechnetes und gespeichertes Nachschlagewerk für Hashes. Eine Tabelle besteht aus zig Ketten, die ein Startwort und einen Endhash besitzen.

Grundlagen

Jeder von euch hat schon einmal eine MD5 Prüfsumme einer CD heruntergeladen und diese Prüfsumme mit dem Image auf eurer Platte verglichen. Stimmt die Prüfsumme, so habt ihr die Nutzdaten ohne Übertragungsfehler heruntergeladen.

Niemand würde aber auf die Idee kommen, aus dem 32 Zeichen langen Hash die CD-Nutzdaten zurückgewinnen zu wollen. Hashen ist eine One-Way-Operation, aus einem Hash kann man nicht die Eingangsdaten zurückgewinnen.

Da das Zurückrechnen nicht geht, könnte man bei Passwörtern einen Dictionary-Angriff starten und hoffen, dass man die richtigen Wörter, aus denen das Passwort gebildet wird, in seinem Wörterbuch hat. Das dauert sehr lange und muss für jeden gesuchten Hash wiederholt werden, da man nur durch das Vergleichen zum Ziel kommt. Alle vorberechneten Plaintext:Hash-Paare in einer Datenbank zu speichern, würde extrem viel Platz wegnehmen. Also suchen wir nach einer Möglichkeit, Millionen von Hashes kompakt zu speichern.
Die Lösung: Rainbow-Tables

Erstellung

Man nimmt ein Startwort, einen Plaintext, und hasht ihn, reduziert ihn um ihn erneut zu hashen und wiederholt diese Schrittfolge 10.000 mal.

 String plaintext, first, ciphertext;

 plaintext = first = "abcdefg";

 for ( int i=0; i<10000; i++ ) {
   ciphertext = hash_it (plaintext);
   plaintext = reduce_it (ciphertext);
 }

 System.out.printf ("%s:%s\n", first, ciphertext);

Diese Schrittfolge erzeugt genau eine Kette in der Tabelle. Regenbogentabellen bestehen aus Tausenden solcher Ketten.

Anwendung

Nach dem langwierigen Prozess der Erstellung besitzen wir eine fertige Tabelle zum Nachschlagen. Jede Kette besteht aus einem Startwort und einem Endhash und alle Hashes (und Plaintexte) IN der Kette sind auffindbar. Wir suchen nun den Plaintext für 97fae39bfd56c35b6c860aa468c258e0 ("Domino"). Wenn dieser Hash auf der rechten Seite unserer Tabelle in Zeile 25 zu finden ist, dann müssen wir Zeile 25 von Anfang bis Ende durchlaufen, um an den gesuchten Hash (damit haben wir auch den Plaintext) zu kommen. Finden wir den Hash aber nicht auf der rechten Seite, dann reduzieren wir den Hash, beispielsweise auf die ersten 6 Zeichen, hashen dann "97fae3" und bekommen 8bf57f707d0f8390ae5339b2ce708f67. Jetzt suchen wir diesen Hash auf der rechten Seite und machen das solange, bis wir wirklich einen Final-Hash auf der rechten Seite gefunden haben. Sollten wir als Beispiel unseren gesuchten Hash auf diese Weise 5000 mal reduziert und gehasht haben, so befindet sich unser Passwort hoffentlich in der Mitte der Kette, die wir jetzt neu berechnen müssen.

Schaut euch einfach mal das Java Beispiel in der Linkliste an. Da habt ihr was zum Spielen...

Weblinks

Sorry: aber die gibt es fast alle nicht mehr:

• Ein mehr Online Datenbank
• Online Datenbank (derzeit dicht)
• Hashkiller.com - Riesige Datenbank und Webcrack/Listcrack System
• leicht verständliche Implementierung in Java
• Diverse Rainbow Tables zum Download per .torrent

---

dieser artikel ist kurz. bau ihn aus!