Mitternachtshacking

Rainbow Tables sind eine clevere Sache. Philippe Oechslin war 2003 der Pionier, der mit seiner Arbeit „Making a Faster Cryptanalytic Time-Memory Trade-Off“ die Grundlagen für vorberechnete Hash-Tabellen geschaffen hat. Hash-Tabellen sind immer dann sehr praktisch, wenn die Passwörter in einem simplen Hash gespeichert sind. Das kommt beispielsweise bei Windows LAN-Manager Authentisierung vor, aber auch hier in dieser WordPress-Installation. Hier ist das Passwort ein einfacher MD5-Hash.

Das Problem mit Rainbow Tables ist, dass sie lediglich ein gewisse Wahrscheinlichkeit garantieren, den gefundenen Hash zu brechen. Je größer die Tabelle um so größer auch die Wahrscheinlichkeit aber Tabellen können dann sehr groß werden. Außerdem lohnen sich Rainbow Tables nur, wenn man mehrere Passwörter brechen will. Bei einem einzelnen Passwort ist ein Brute Force Angriff praktisch immer schneller. Für sieben Zeichen benötigt das Berechnen der Rainbow Table etwa eine Woche, das Ermitteln eines Passworts kann dann in 30 Sekunden erfolgen. Der Brute Force Angriff auf ein einzelnes Passwort ist in der Regel in 24 Stunden erfolgreich.

Das Problem ist jedoch, große Rainbow Tables brauchen viel Platz. Die Tabelle für ein 8-Zeichen Passwort mit 99% Wahrscheinlichkeit braucht etwa 1,5 TB (1500 GB) . Das ist jetzt nicht dramatisch, da beispielsweise Western Digital 650 GB Festplatten für unter 100 Euro verkauft. Aber bei längeren Passwörtern wachsen die Tabellen massiv an.  Ok, man kann die Wahrscheinlichkeit reduzieren. 90% Wahrscheinlichkeit passt auf 700 GB, 1% Wahrscheinlichkeit bereits auf eine einzelne CD-ROM.

Und jetzt nehmen wir folgenden Gedanken an … wir erzeugen Hashes für Passwörter bis meinetwegen 32 Zeichen. Und zwar genau so viele verschiedene, dass wir damit 1 TB Daten füllen können. Mehr nicht. Das ist eine Rainbow Table mit einer geringen Wahrscheinlichkeit, so etwa in der Größenordnung 0,01 %. Allerdings für beliebige Passwörter. Die Wahrscheinlichkeit, dass „G0%dP@ssw0rd“ dabei ist, ist genauso groß wie für „abc“. Im Grunde sind dann alle Passwörter gleich gut, sie haben alle die gleiche Wahrscheinlichkeit erraten zu werden. Und was ist, wenn nicht nur ich so eine Tabelle erzeuge (und Passwortabfragen per Webinterface zulasse) sondern 100 andere Leute auch. Natürlich zufällig andere Tabellen. Klar wird es Überschneidungen geben aber insgesamt auch viele unterschiedliche Passwörter.

Ich finde diese Idee ein klein wenig beängstigend. Sie stammt übrigens von The [SNS] Technologies, einer russischen Firma, die u.a. The UDC anbietet, ein Programm zum Brechen von Hashes. Für nicht Russischsprachler gibt es bei InsidePro eine Übersetzung.

In Summe erkennen wir also, dass einfache Hashes zum Speichern von Passwörtern nicht mehr geeignet sind. Die richtige Lösung gibt es auch schon seit mindestens 50 Jahren: Salted Hashes. Jedes Passwort wir mit einem Salt kombiniert und dann erst gehashed. Der Salt wird im Klartext neben dem Passwort-Hash gespeichert. Damit lassen sich Rainbow Tables effizient aushebeln. Ich schrieb dazu im September etwas, weil Matasano die Gefahr von Rainbow Tables und die Gegenmaßnahmen sehr gut erklärt hat.

Das schlimme ist, wir wissen das im Grunde seit 50 Jahren. Und trotzdem verwendet Software wie dieses WordPress hier immer noch simple MD5-Hashes zum Speichern von Passwörtern. Also nichts gelernt. Und das finde ich jetzt wirklich beängstigend.