GPU Brute-Force: Das Ende der Rainbowtables? (Update)

Rainbowtables

Bis heute sind Rainbowtables das non plus ultra wenn es um Hash Cracking geht. Vereinfacht gesagt sind Rainbowtables große Tabellen in denen viele Passwörter mit den dazugehörigen Hashes drin stehen:
c20ad4d76fe97759aa27a0c99bff6710:12
202cb962ac59075b964b07152d234b70:123
Wenn man einen Hash cracken möchte braucht man also nur die Rainbowtables zu durchsuchen. Wenn der Hash in der Tabelle drin steht findet man ihn und damit das Passwort gewöhnlich viel schneller als mit einem normalen Brute-Force Programm. Wenn der Hash nicht drin steht ist die Rainbowtable natürlich wertlos.

Nachteile:

• Rainbowtables muss man natürlich erstmal generieren. Mit nur einem Computer ist das kaum zu schaffen, selbst der schnellste Desktop-PC braucht für gute Rainbowtables mehrere Monate.
• Gute Rainbowtables verbrauchen viel Speicherplatz. Mit 60 GB muss man mindestens rechnen. Klar in der heutigen Zeit sind 500 GB Festplatten schon fast standard, trotzdem ist es eine imense Datenmenge.
• Man braucht für jeden Hash Typ eigene Tables.
• Salted Hashes machen Rainbowtables nutzlos.

Das Projekt Free Rainbow Tables schaltet den ersten Nachteil schon fast aus. Das Projekt generiert mit Hilfe von aktuell ca. 1280 Computern die Rainbowtables. Jeder kann auch mitmachen beim Generieren, man muss nur das speziell dafür entwickelte Tool DistrRTgen auf dem PC laufen lassen. Jeder kann sich dort auch die fertig generierten und sehr effizienten Tables runterladen.

Brute-Force und Salted Hashes

Der 3. und 4. Nachteil könnten aber bald das aus für die Rainbowtables bedeuten. Beschleunigt wird das durch die Möglichkeit die Grafikkarte zum brute-forcen zu benutzen.
Schon seit die Rainbowtables Technik entwickelt wurde wird gepredigt, dass sie nutzlos gegen Salted Hashes sind. Den Web-/Entwicklern war das lange Zeit egal und sie haben den Rat einfach ignoriert. Dank diser Ignoranz konnten die Rainbowtables erst so richtig aufblühen, obwohl es doch so einfach ist einen Hash gegen die Rainbowtables immun zu machen. Man nehme einen zufällig generierten String, hängt ihn vor oder hinter das eigentliche Passwort und hashed das ganze z.b. mit MD5. Beispiel:
Zufällig generierter String: a0*qow92?+#O9siw9
Das eigentliche User Passwort: 123
Das wird nun MD5 gehasht: a0*qow92?+#O9siw9123 und ergibt 230af2f781d88c072f704fd96c92a1bc
Natürlich muss man nun zu dem MD5 Hash auch noch den Salt speichern ;) so z.b. 8027f6832595271f25a48acad929a08b:a0*qow92?+#
Keine Rainbowtable ist in der Lage ein 20 stelliges MD5 Passwort zu cracken mit großen und kleinen Buchstaben, Sonderzeichen und Zahlen. Es wird wohl auch nie eine Rainbowtable geben die das kann, man bräuchte dafür mehr Speicherplatz als rapidshare.com momentan zur Verfügung hat. Die Web-/Entwickler haben aber jetzt reagiert, heute benutzt fast jedes neue CMS oder Forensystem salted Hashes.
Ganz anders sieht es aus mit einem Brute-Force Programm, ein normales Tool bräuchte für diesen Salted Hash wenige Millisekunden. Warum das? Weil man bei einem Programm den Salt eingeben kann. Das Programm muss also nur ein 3-stelliges Zahlen Passwort cracken. Dem Programm macht es also nichts aus das der Hash salted ist, es wird zwar etwas langsamer sein, aber ansonsten macht ein Salt nicht mehr Probleme als ohne Salt.

GPU Brute-Force

Der einzige Grund warum Rainbowtables auch heute noch so beliebt sind ist ganz klar die Geschwindigkeit. Ein normales Brute-Force Programm das vor allem den CPU benutzt ist viel langsamer als eine Rainbowtable. Dieser Geschwindigkeitsvorteil könnte aber bald verschwinden, dank GPGPU.
Die GPUs (Grafikprozessoren) der heutigen Grafikkarten sind schon seit längerer Zeit (viel) leistungsfähiger als die CPUs. Einer der schnellsten CPUs den man heute kaufen kann ist der Intel Extreme QX9770 er schafft ca. 46 GigaFLOPs (Floating Point Operations Per Second). Die Schnellste Grafikkarte zurzeit ist die Geforce GTX 280, sie schafft ca. 933 GigaFLOPs (fast 1 TeraFLOP). Also wäre die schnellste GraKa (kostet ca. 400€) ca. 20 mal schneller beim brute-forcing als der schnellste CPU (kostet ca. 1000€). Gegen den schnellsten Supercomputer der zurzeit ca. 1026 TeraFLOPs schafft hört sich das natürlich noch sehr wenig an, aber der Unterschied GraKa <-> CPU ist enorm.
Leider fehlt es momentan noch ein bisschen an Brute-force Programmen die mit dem GPU arbeiten. Aber es liegt wohl auch daran das die Technik erst noch am kommen ist. Um den GPU für sowas zu „missbrauchen“ braucht man natürlich eine API.
Nivida nennt die Technologie CUDA http://www.nvidia.de/object/cuda_learn_de.html
ATIs Lösung Stream SDK ist CUDA momentan noch klar unterlegen, deshalb gibt es zurzeit nur Programme die mit Nividia GraKas arbeiten. Das ist zwar sehr schade, aber was will man machen wenn ATI schläft…

Schauen wir uns mal an was GPU Brute-Forcing wirklich bringt. Hier haben wir ein schönes MD5 GPU Brute-Force Programm http://bvernoux.free.fr/md5/index.php. Laut Entwickler schafft das Programm 200 Millionen Hashes pro Sekunde mit der Grafikkarte 8800GT (ca. 500 GFLOPs). Ganz schön viel wenn man z.b. das gute CPU Brute-force Programm MDCrack anschaut: http://membres.lycos.fr/mdcrack MDCrack schafft auf einem 2x XEON 3.2GHz (DC + HT) gerade mal 42 Millionen Hashes pro Sekunde. mdcrack
Laut eigenem Test weiss ich auch das eine GeForce 8800 GTS 512 bei MD5 ca. 489 Millionen Hashes pro Sekunde schafft. Ein unglaublicher Wert, den erstmal kein CPU so schnell schaffen wird.

Hier mal eine Liste mit GPU Brute-Force Programmen (Alle für Nividia GraKas):

• Extreme GPU Bruteforcer (Shareware, MD5/MySQL/SHA-1/NTLM, )
• GPU MD5 Crack (Freeware, MD5)
• BarsWF (Freeware, MD5)
• Lightning Hash Cracker (Freeware, MD5)
• CuMD5 (Open-Source, MD5)
• nvCUDA (Open-Source, MD5/Mysql)

Auf den Websieten der Tools findet man übrigens auch noch sehr gute Übersichtsgrafiken, die auch ganz klar belegen das der GPU hier sehr viel schneller ist als ein CPU.

Hoffen wir mal das bald noch mehr und bessere GPU Bruteforcer entwickelt werden und das ATI mal in die Gänge kommt. Wer also gerne brute-forced sollte sich eine Nividia Graka zulegen, es lohnt sich auf jedenfall. In spätestens einem Jahr wird sich zeigen ob die Rainbowtables nur noch unnötiger Datenmüll sind oder nicht, die Zukunft spricht aber klar gegen die Regenbogentabellen: Fast nur noch salted Hashes und mehr GPU Power.

Bleibt nur noch die Frage, was können die Web-/Entwickler tun um ihre Produkte besser vor Hackern zu schützen? Die Antwort ist aber auch ganz klar: sicherere Hash Algorithmen einsetzen.

Bitte mit diesem Wissen nur euer eigenes Passwort auf Sicherheit testen ;-)

Update 1:

Ich habe es jetzt mal selber ausprobiert, das Ergebnis ist sehr geil:

Ich besitze eine GeForce 8800 GTS 512 und schaffe ~489 Millionen Hashes pro Sekunde, nebendran steht auch was mein CPU (C2D E8400) nur schafft…

Update 2:

Am 25. September wurde die Version 0.7 des BarsWF Programms released. Ein paar Bugs wurden gefixt und die Farben der Ausgabe sind nun auch viel ansehnlicher. Man hat jetzt auch mehr Einstellungsmöglichkeiten mit denen man wahrscheinlich noch mehr Speed beim bruteforcen erreichen kann.
Viele Tests haben jetzt auch bestätigt, dass BarsWF das momentan beste und schnellste GPU Bruteforce Programm auf dem Markt ist. Es ist nur sehr schade das man bisher nur MD5 bruteforcen kann.
In einem Kommentar hat der Entwickler uns auch mitgeteilt das wahrscheinlich im Oktober 2008 eine Version für ATI/AMD Grafikkarten erscheinen wird.