MD5-Rainbow-Tables
Thomas N. hat mir gestern die Funktionsweise von Rainbow-Tables erklärt. Dabei handelt es sich um eine optimierte Version eines Wörterbuchs, das für alle möglichen Passwörter die MD5-Summen enthält. So ein Wörterbuch ist praktisch, um ein Passwort zu ermitteln, wenn man lediglich die gehashte Repräsentation vorliegen hat und kein Salting zum Einsatz kommt.
Das Problem: So ein Wörterbuch wird sehr schnell sehr groß. Bei siebenstelligen Passwörtern, die theoretisch aus 26 Groß- und Kleinbuchstaben sowie allen Ziffern bestehen muss man mit rund 75 GB rechnen. Eine äquivalente Rainbow-Table benötigt hingegen nur einige Gigabytes. Dennoch lassen sich mit einer solchen Tabelle praktisch alle Passwörter innerhalb weniger Minuten ermitteln.
Dies wird durch geschickte Kettenberechnung und Umwandlung von Hashwerten in Klartext (mit einer so genannten Reduktionsfunktion) realisiert. Rainbow-Tables reduzieren den Speicherbedarf auf Kosten einer etwas höheren Berechnungszeit.
Die Theorie dazu hat Phillipe Oechslin publiziert. Eine anschauliche Erklärung gibt es online.Das Projekt FreeRainbowTables verfolgt das Ziel, große populäre Rainbow-Tables verteilt mit Hilfe von tausenden Rechnern zu berechnen
Eine wirksame Gegenmaßnahme ist die Speicherung von Passwörtern als gesaltete Hashes. Eine PHP-Implementierung dieses Verfahrens ist verfügbar.
Eine Alternative zu Rainbow-Tables sind MD5-Datenbanken wie http://md5.thekaine.de/ oder http://md5.xpzone.de/ oder http://gdataonline.com/ oder http://md5.rednoize.com.
Wie Steven Murdoch vor einer Weile durch Zufall bemerkt hat, kann man auch Google nach einem unbekannten MD5-Hash fragen. Das funktioniert erstaunlich gut.