Rainbow Tables

Rainbow Tables

• Eine volle Hash-Tabelle für alle Passwörter wäre Petabytes groß - unbaubar.
• Rainbow Tables schrumpfen das auf ein paar Hundert GB, damit es überhaupt auf eine Platte passt.
• Bezahlt wird's mit Rechenzeit beim Suchen.

Idee

• Mittelweg zwischen Brute Force und voller Hash-Tabelle
• Brute Force: nichts gespeichert, alles live hashen → langsam, kein Platz
• Volle Tabelle: alles gespeichert → schnell, aber riesig (Petabytes)
• Rainbow Table: nur Teil gespeichert, Rest beim Suchen nachrechnen → tauscht Platz gegen Rechenzeit

Zwei Funktionen

H = Hash (Passwort -> Hash)

• normale Richtung

R = Reduktion (Hash -> Passwort-String)

• keine Umkehrung, erzeugt nur wieder etwas passwortförmiges

Kette

• abwechselnd H und R anwenden

abc12 --H--> 9f3a.. --R--> delta --H--> 77b1.. --R--> zonk9
  ^                                                     ^
Anfang                                                 Ende
(gespeichert)                                     (gespeichert)
          <---- alles dazwischen wird verworfen ---->

• nur Anfang und Ende jeder Kette speichern
• 1000 Glieder pro Kette -> 1 Eintrag statt 1000 -> Platzgewinn

Suchen

• ab eigenem Hash selbst Kette bauen (R, H, R, H ...)
• nach jedem Schritt prüfen: Treffer auf gespeichertes Ende?
• Treffer -> zugehörigen Anfang nehmen
• Kette von vorne durchrechnen -> darin liegt das Passwort

Warum "Rainbow"

• pro Position andere Reduktionsfunktion (R1, R2, R3 ...)
• verhindert Zusammenlaufen/Kollision der Ketten
• Abfolge der Funktionen = "Regenbogen"