Rainbow-Tables: Verständnisfragen

ascer

Captain
Dabei seit
Juni 2008
Beiträge
3.418
Hallo Community,


ich beschäftige mich zurzeit unter anderem mit IT-Security und hatte gerade entsprechende Aufgaben zu Hash-Verfahren und Angreifermodellen zu erledigen.

Die derzeit, meines Kenntnisstands nach, effizienteste Methode um gehashte Passwörter zu knacken sind Rainbow-Tables. Mir ist allerdings die Funktionsweise noch nicht ganz klar. Kennt sich hier eventuell jemand damit aus?

Um Kollisionen zu vermeiden (Wiederholungen von reduzierten Klartextpasswörtern, die dann zu Wiederholungen in den entsprechenden Hashes führen) verwendet man ja unterschiedliche Reduktionsfunktionen, daher ja auch der Name Rainbow-Tables, mir ist aber noch nicht ganz klar, wie das konkret aussieht.

Gehe wir mal von folgendem Beispiel, ausgedachtem Beispiel für MD5-Hashes aus:

Startwort: 123456 -> MD5
Starthash: e10adc3949ba59abbe56e057f20f883e -> Reduktionsfunktion1
-
2. Wort: 325951 -> MD5
2. Hash: 38a84d0439956131e6c1f612940a79a6 -> RF2
-
3. Wort: 912345 -> MD5
3. Hash: 5961f2505be01e4022aa387b4fd3b617 -> RF3
-
Endwort: 612364 -> MD5
Endhash: 19fab58f1241d1c215ea3db6e29352ed

Mir ist noch nicht ganz klar, wie da genau Rechenzeit bei gespart werden soll, denn sobald die Tabelle erstellt ist speichert man ja nur Startwort und Endhash bzw. Endwort. Wenn ich jetzt also auf der Suche nach dem Wort zu dem 3. Hash "5961f2" wäre, könnte ich doch gar nicht wissen, in welcher Tabelle ich nachschauen muss? Sprich in dieser hier oder einer der ewig vielen anderen, die man ebenfalls erstellt hat.

D.h. doch, dass ich eigentlich in jeder Tabelle die mir zur Verfügung steht nachgucken muss, bis ich eine Lösung gefunden habe. Dies wiederum bedeutet doch aber, dass ich jede Tabelle, also jede Kette von vorn nach hinten durchlaufen, sprich noch einmal kalkulieren muss. Wo ist denn da Rechenzeit bei gespart worden?

Und von der Speicherplatzkomplexität: Um nicht wieder erneut Rechenzeit zu vergeuden, muss ich doch die Reduktionsfunktionen zusätzlich zu der Tabelle speichern?!


Viele Grüße

ascer
 
Zuletzt bearbeitet:

Bartmensch

Commodore
Dabei seit
Mai 2010
Beiträge
4.360
Bei den Rainbow Tables wird das sogenannte "Times-Memory-Tradeoff" Prinzip verwendet.
Bei den Rainbow-Tabellen hat die konsequente Anwendung dieses Prinzips zu einer kompletten Zweiteilung der Lösung geführt. In einem völlig eigenständigen Vorbereitungsprogramm werden mit ganz erheblichem Rechenaufwand große Tabellen vorbereitet. Andere Programme nutzen die vorbereiteten Tabellen, um damit in relativ geringer Zeit Verschlüsselungen oder Passwörter zu brechen.

Nur daher rührt die Zeitersparnis bei Verwendung der Tables.
Wenn man sich die Größe der Tables anschaut, ist das verständlich.

Hier noch ein netter Link zu einer erklärenden PDF:
http://ia700508.us.archive.org/21/i...interne_Angriffe_auf_Windows_NT_5-Systeme.pdf

Und die CT hatte auch noch was:
http://www.heise.de/security/artikel/Von-Woerterbuechern-und-Regenboegen-270088.html
 
Zuletzt bearbeitet:

Daaron

Fleet Admiral
Dabei seit
Dez. 2011
Beiträge
13.487
Der Trick ist, dass du einmal mit hohem Aufwand eine riesige, generisch nutzbare Liste von Key-Value-Paaren aufbaust, in dem Falle Hash -> Klartext. Danach kannst du diese Liste immer wieder anwenden.
1x viel Arbeit, 10000x quasi keine
 

Valhal

Ensign
Dabei seit
Nov. 2014
Beiträge
140
Rainbowtables sind ein Relikt und nicht mehr zeitgemäßig. Früher (vor GPU-Computing) waren die CPUs sehr langsam für Hash Bruteforce, deshalb war es deutlich besser die Hashwerte vorzukalkulieren und diese in riesigen Tabellen zu speichern. Rainbowtables lohnten sich erst so ab ca. 30 Gigabyte. Bei Tabellen unter 30 Gigabyte war der CPU wiederum besser dran.

GPU Computing existiert seit ca. 2007. Die Bruteforce-Geschwindigkeit stieg sprunghaft an. GPUs waren sofort ca. 10 mal schneller als CPUs. https://hashcat.net/oclhashcat/

Neben GPU Computing war die zunehmende Verbreitung von Salts das Todesurteil. Heute gibt es kaum noch Anwendungen die keinen Salt einsetzen.
 

tiash

Lt. Junior Grade
Dabei seit
Sep. 2014
Beiträge
501
Rainbowtables sind ein Relikt und nicht mehr zeitgemäßig.
Das halte ich so für eine SEHR gefährliche Aussage!
Warum sollte ich Rainbow Tables nicht auch auf GPUs nutzen? Warum nicht sogar auf speziell dafür programmierten FPGA-Chips?
Der Vorteil ist heute noch der Gleiche wie früher. Stecke ich Zeit in eine Vorberechnungsphase kann ich in der Live-Phase, also beim wirklichen Cracken von Hashes, Zeit sparen.

Natürlich ist die Verwendung von Hashes eine Maßnahme, um davor zu schützen, genau genommen vor dem großen Vorteil mit einer einzigen Rainbow Table viele Millionen Passwörter gleichzeitig angreifen zu können.
Salts werden aber längst noch nicht überall eingesetzt (in einer solchen Welt würde ich zu gern leben!), oder sie werden falsch eingesetzt (zu kurz gewählt, so dass sie Rainbow Tables nicht verhindern), oder oder oder..

Rainbow Tables sind noch lang nicht out.
 

Daaron

Fleet Admiral
Dabei seit
Dez. 2011
Beiträge
13.487
Salts werden aber längst noch nicht überall eingesetzt (in einer solchen Welt würde ich zu gern leben!), oder sie werden falsch eingesetzt (zu kurz gewählt, so dass sie Rainbow Tables nicht verhindern), oder oder oder..
Um diesen Aspekt mal mit realistischen Werten zu unterstreichen:
Magento, immerhin eines der größten und beliebtesten freien Shopsysteme, verwendet md5 mit einem zweistelligen alphanumerischen Salt...
 

Valhal

Ensign
Dabei seit
Nov. 2014
Beiträge
140
Rainbowtables sind nur noch im Spezialfall sinnvoll.

z.b. bei LM Hashes sind die maximalen Zeichen auf 7 begrenzt.
z.b. bei A5/1 (GSM) können spezielle tables das cracking beschleunigen

Rainbowtables allgemein machen keinen Sinn mehr, weil auch der Speicherbedarf und Berechnungszeit extrem steigt (exponentiell). Solche riesigen Tables verlangen dann auch viel Arbeitsspeicher und viel Platz... schnelle Zugriffszeiten und Geschwindigkeit, also SSDs zum Speichern.
 

Daaron

Fleet Admiral
Dabei seit
Dez. 2011
Beiträge
13.487
RAM und Permanentspeicher sind billig, also wo liegt das Problem?
Angenommen, ich habe eine sehr umfangreiche md5-Rainbowtable... im Hinblick auf die aktuell laufende (und recht erfolgreiche) Magento-Einbruchsserie kann ich hier extrem zeitnah große Mengen sehr interessanter Daten entschlüsseln.
 

Valhal

Ensign
Dabei seit
Nov. 2014
Beiträge
140
Weil du mit z.b. einer hd7970 eine Geschwindigkeit von 8581 Millionen Hashes pro Sekunde erreichst, wirst du mit einem Wörterbuch und ein paar Regeln viel schneller und viel mehr Erfolg haben. Die meisten Benutzerpasswörter bestehen nun mal aus einem Wort + Abwandlungen z.B. Zahlen am Ende des Wortes.
 

Daaron

Fleet Admiral
Dabei seit
Dez. 2011
Beiträge
13.487
Wenn du ein spezifisches Passwort willst, ja. Aber wenn dir die Daten von 50.000 Magento-Installationen in die Hand fallen (~200.000 sind aktuell verwundbar), dann crackst du nciht mehr jedes Passwort einzeln.
 

Valhal

Ensign
Dabei seit
Nov. 2014
Beiträge
140
Sorry aber von Hash Cracking hast du keine Ahnung. Diese Geschwindigkeit bezieht sich doch auf Listen cracken. Wenn du 10000 Benutzerpasswörter cracken musst, hast du 40-50% davon nach einer Stunde gecrackt mit dem GPU.

2mal 290X in den Rechner und die Sache ist schneller erledigt als du es dir vorstellen kannst, wobei du 100% nie erreichen wirst. Aber 60-70% der Passwörter geht immer.
 
Top