Diskussion:Rainbow Table

Überarbeitungshinweise

Stefan, 14.6.2008: Hi, nach kurzen googlen vermute ich, dass die Zeitvorteile der rainbow-tables auf folgenden Eigenschaften basieren können:
a) Die vorberechneten final-hashs können sortiert werden und daher kann ein match mit einem hash-kandidaten schneller gefunden werden.
Genauer: Bei n Ketten der Länge k müssen im worst-case nur log(n) * k Vergleiche gemacht werden.
b) Die Hashfunktion selbst ist rechenintensiv und muss nur noch auf den Kandidaten und beim Match auf einer Kette durchgeführt werden.
=> Ich denke, dass hauptsächlich a) die Vorteile bringt. Leider wird in dem Artikel nicht darauf eingegangen, wie genau RTs Zeitvorteile bringen. Ein Beispiel wäre sinnvoll. Auch wie sich a) noch parallelisieren läßt wäre interessant.

Aus den derzeitigen Beschreibungen ist der nicht er

Hallo!

Sorry, der Artikel bedarf dringend einer Überarbeitung. Die Linksammlung ist ja ganz gut, aber die Formulierungen und auch die Erklärung was überhaupt Rainbow-Tables sind, ist haarstäubend.

Den OMA-Test besteht der Artikel jedenfalls nicht... Jemand mit etwas Ahnung sollte mal eine ausführlichere Beschreibung der Datenstruktur und zum Time-Memory Trade-Off allgemein schreiben.

--83.135.157.225 00:29, 8. Apr. 2007 (CEST)

Ein Text der mit "Grob gesagt" kann nicht viel gutes bedeuten ... neu formulieren ? (Der vorstehende, unsignierte Beitrag wurde um 03:19, 13. Apr. 2007, von 89.245.118.156 (Beiträge) erstellt. --Saibo (Δ) 21:19, 23. Okt. 2007 (CEST))

"Eine zu Beginn zufällige Zeichenfolge wird verschlüsselt. Aus diesem Hash..." Ein Hash ist keine Verschlüsselung! (Der vorstehende, unsignierte Beitrag wurde um 08:19, 17. Apr. 2007, von 145.253.32.3 (Beiträge) erstellt. --Saibo (Δ) 21:19, 23. Okt. 2007 (CEST))

ARG - WAS IST DAS?! Mal ehrlich, wenn ich nicht heute schon einige andere Seiten gelesen hätte, wäre ich mit dieser Beschreibung gelinde nicht klar gekommen. Aus welchem Kryptho-Lehrbuch für Studenten habt Ihr das bitte abgeschrieben!? (Der vorstehende, nicht signierte Beitrag stammt von 217.224.153.215 (Diskussion • Beiträge) 7:31, 25. Nov 2007) -- Klara 16:28, 29. Dez. 2007 (CET)

Kann mich den Vorredner nur anschließen. Der Artikel ist zu Oberflächlich, um einen Über-/Einblick in die Funktionsweise von Rainbow Tables zu bieten. Der Artikel der englischen Wikipedia ist hier deutlich besser und lässt einen das Prinzip verstehen. (Der vorstehende, nicht signierte Beitrag stammt von 217.9.111.143 (Diskussion • Beiträge) 8:53, 30. Nov 2007) -- Klara 16:28, 29. Dez. 2007 (CET)

Ich habe mich mal hingesetzt und einen Rainbow Table Creator in Java geschrieben.
Damit läßt sich hoffentlich das Ganze leichter verstehen.
Kommentare, Anregungen und Kritiken kommen auf diese Diskussionsseite und nicht in den Wiki-Text.

Der Quelltext ist wirklich sehr Hilfreich. Aus dem Wiki-Text hatte ich entnommen, dass die Reduktionsfunktion eine Art Bruteforce-Anfriff ist, wobei eine Kollision auf den erzeugten Hash gesucht wird. Wie auch immer. Nachdem ich nun weiß wie das ganze gedacht ist hat sich meine Meinung gegenüber dem Wiki-Text geändert. Er ist gut geeignet um um das zu bestätigen was man glaubt zu wissen :D Auf jeden Fall fehlt eine genauere Äußerung zur Reduktionsfunktion. Wie es schon im Quelltext steht - mit ihr steht und fällt alles. --91.14.180.145 22:55, 28. Mai 2008 (CEST)

ÜA Baustein entfernt. Der Artikel wurde inzwischen überarbeitet Nolispanmo Disk. Hilfe? ^± 19:46, 23. Feb. 2008 (CET)

Hashwerte kann man nicht *entschlüsseln*

Zu den oberen Punkten kommt hinzu, dass der Artikel ganz oben schon mal eine falsche Aussage macht. Hashwerte *entschlüsselt* man *NICHT*. Man kann höchsten (mehr oder weniger) effizient ein Urbild (also eine Bytefolge) zu einem gegebenem Bild finden.

Man könnte auch sagen das man nach Kollisionen sucht.--91.14.180.145 23:08, 28. Mai 2008 (CEST)

Kann mich den anderen Kommentaren nur anschließen: Um zu verstehen, was eine Rainbow-Table ist, taugt der Text im Gegensatz zu dem aus der engl. Version von Wikipedia überhaupt nichts!

Eigentlich sucht man auch nicht nach Kollisionen, sondern man "rät" einfach, wie Passwörter, die gehasht wurden, gebildet werden, oder genauer gesagt, welchen Zeichenraum sie umfassen. Ohne Zwang (z.B. eine minimale Länge) sind 1-7 Stellen alphanumerisch mit Gross- und Kleinschreibung in vielen Fällen ausreichend. Da man wenig Lust hat, diesen Zeichenraum für jede Passwort-Hash oder Liste von Hashes immer wieder mit dem Cracker der Wahl durchzugehen berechnet man eine Rainbowtable. Oder lädt sie von ophcrack oder FRT runter. Werden einzelne Passworte nicht gefunden, ist das nicht weiter schlimm, schliesslich kann man diese einem intelligenten Bruteforcer wie John oder einfach einem GPU-basierten Cracker wie dem CUDA-Multiforcer übergeben und hier z.B. ein paar Sonderzeichen hinzufügen.

Konkretes Beispiel: Bei LM-Hashes braucht ein Core eines Xeon 3350 mit Cain ca. 9 Tage um A-Z,0-9 und 32 Sonderzeichen vollständig durchzugehen. Mit der Rainbowtable "lm_all-space#1-7", (~40 GB in 4 Sets von ~600 MB grossen Tabellen) welche ca. 99.9% dieses Zeichenraums abdeckt, braucht er für 10 Hashes knapp 20 Minuten; allerdings mit Aufteilung der Arbeit auf 4 Cores (mit rcracki_mt). Das wäre aber der "Worst-Case", d.h. sowohl muss der komplette Zeichenraum gebruteforced werden als auch alle Tabellen durchgegangen werden. D.h. man müsste Hashes von Passworten haben, welche nicht in dem o.g. Zeichenraum liegen, z.B. die von "ä". "Fair" geschätzt, also von einem Multi-Core Bruteforcer ausgegangen sind dies immer noch >30 Minuten gegen 2 1/4 Tage. Interessant ist dabei auch der Stromverbrauch; einmal erzeugt sind RTs die stromsparenste Variante, um Klartexte von Hashes zu finden.

Allerdings lässt man hier das Verhalten von RTs, dass je mehr Hashes vorgliegen der Suchvorgang immer länger dauert ausser acht - es gibt einen "Break Even", eine Anzahl von Hashes bei denen bruteforcen solange braucht wie die RTs zu durchsuchen. Die üblichen Bruteforcer werden bei größerer Anzahlen von zu prüfenden Hashes nur wenig oder auch garnicht langsamer. In der Realität ist dies aber nicht wirklich von Bedeutung, da man die Hashlisten sortieren kann, z.B. nach "interessant" oder sie schlichtweg auf mehrere Systeme aufteilen kann usw. usw. Zudem werden ja mit dem Durchsuchen der Tabelle immer wieder Klartexte gefunden, und die dazugehörigen Hashwerte müssen nicht mehr kontrolliert werden - damit steigt die Geschwindigkeit wieder. Bei den letzten Dateien, die einen Tabellensatz ausmachen, sind dies dann i.d.R. nur noch die Hashes von Passwörten, welche nicht in dem gewählten Zeichenraum liegen oder die schlicht in den nicht generierten Bereich fallen.

Man ist bei der Generierung von Rainbowtables aber nicht auf vollständige Zeichenräume beschränkt, Muster und Wortlisten können auch als Basis dienen. Z.b. könnte man eine Tabelle für MD5 nach dem Muster 1-6 Stellen A-Z,a-z + 1-4 Stellen 0-9 erstellen. Diese deckt dann Passwörter nach dem Muster "Biggi2005" und "09Juli" oder "klaus75" ab. D.h. man kann den TMTO mit weiteren Maßnahmen zur Reduktion des Zeichenraums kombinieren, in dem man wahrscheinliche Muster statt unwahrscheinlichen wählt. Gemacht wurde das in den "Hybrid"-Tabellen von FRT.

Allerdings kann man in fast (s.u.) allen Fällen argumentieren, dass das Passwort eigentlich "erraten" wird - eine kryptographische Schwäche muss in dem Hashverfahren nicht vorliegen; Konzeptionelle Schwächen, wie die zahlreichen in LM, helfen allerdings. Nicht direkt mit dem Hashverfahren hat die Implementation der Passworteingabe in der jew. Soft- oder Hardware zu tun; wenn eine Software z.B. nur 6 stellige Passwörter zuläßt und keine komplexeren Symbole als Satzzeichen oder Rechensymbole dann hilft es nichts, wenn die Hashfunktion zur Passwortspeicherung selbst komplett Unicode-fähig ist und Klartexte belieber Länge akzeptiert. In dem Fall würde diese Information als Grundlage für die Generierung einer RT-Table "gegen" die Passwortsicherheit dieser Software dienen. Also "Wissen" statt "Raten". --92.74.193.225 (16:12, 27. Sep. 2009 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

ideal zum verstehen/aufbessern/Quellenangabe

http://www.heise.de/security/Von-Woerterbuechern-und-Regenboegen--/artikel/113681/0 --Unterstrichmoepunterstrich 19:21, 26. Sep. 2008 (CEST)

32 Bytes

"so werden pro Datenbankreihe mindestens 32 Bytes für den Hash und 6 Bytes für den Plaintext benötigt" - das ist etwas irreführend, sinnvollerweise würde man es wohl eher nicht als ASCII speichern, sondern direkt die 128 Bit (16 Byte) des Hashes - oder?. --85.179.40.21 16:41, 20. Okt. 2008 (CEST)

Vorschlag: besser Artikel allgemein über TMTO's

Rainbow Tables sind ja nur eine Spezialisierung von normalen TMTO's. Deshalb sollte man vielleicht besser einen Artikel schreiben, der allgemein die Funktionsweise erläutert, und dann noch die Rainbow Tables (und natürlich auch Dingishued Points) als Spezialisierungen erläutern. Dann wäre das Ganze vielleicht etwas besser verständlich! --FalconL 16:55, 3. Mär. 2009 (CET)

Ich versuche jetzt mal, einen Artikel allgemein über TMTO's zu schreiben. Ich werde ihn allerdings offline ausarbeiten müssen. Voraussichtlich im September stelle ich ihn dann ein. -- FalconL 16:04, 29. Jul. 2009 (CEST)

Der Atikel entsteht gerade hier (meine Baustelle). Ich wäre nicht undankbar für ein wenig Hilfe! -- FalconL ^{Dis Bew Akt} 18:40, 13. Nov. 2009 (CET)

Tote Links zu Downloadseiten http://rainbowtables.ddl.cx u. http://cl1p.net/rainbowtables/

Hallo, die Links zu den Downloadseiten von Rainbow-Tables sind tot - sie führen zu leeren Seiten. Stattdessen 0phcrack und FRT zur Verlinkungvorgeschlagen - die sollten beständiger sein - es handelt sich um Projekte, nicht um reine "Tabellenhalden". Hinter Ophcrack steckt u.a. Oechslin selbst, und FRT ist neben Projekten zur Erstellung der GSM/A5-Tabellen die einzige grosse Gruppe, die zusammen frei verfügbare RTs generiert. -- 92.79.151.50 14:39, 6. Nov. 2009 (CET)

PHP-Installationen

"Dieses funktioniert bei Hash-Funktionen ohne Salt, wie es z. B. bei [...] einigen PHP-Installationen [...] der Fall ist." Ich verstehe nicht, was PHP dafür kann. Was ist mit "PHP-Installationen" überhaupt gemeint? Software, die in PHP geschrieben ist (dafür kann dann aber PHP selbst nichts), oder die PHP-Installation selbst? Wenn die PHP-Installation selbst gemeint ist, wo werden dort ungesalzene Hashes verwendet, die irgendwie relevant für Rainbow Tables sind? -- 85.216.58.128 22:54, 10. Mär. 2010 (CET)

Holprige Formulierung. Bestimmte Versionen von PHP verwendeten MD5-Hashes, um Passwörter zu speichern. Das kann man allerdings ändern, deswegen wohl die Formulierung mit den "einigen PHP-Installationen". Eine allgemeinere und zeitlosere Formulierung wäre: "Auch in Webapplikationen werden verschiedene Hashverfahren ohne SALTs, allen voran MD5, zur Speicherung von Passworten verwendet. Bei einer Kompromittierung der Anwendung, z.B. durch eine SQL-Injection, können diese ausgelesen und mit Hilfe von Rainbowtables gecrackt werden. Es 1 Schande. Das mit der Schande kann man weglassen, aber nicht ohne sich schlecht zu fühlen. --92.74.204.49 17:29, 2. Apr. 2010 (CEST)

Gegenmaßnahmen

Der Abschnitt "Gegenmaßnahmen" war m.E. leicht irreführend - er wies auf die Möglichkeit hin, das kurze Passworte mit SALTs geschützt werden können, und das ungewöhnlich Zeichen in Passphrases vorkommen. Vor kurzen Passworten kann in der Realität kein Hashing-Verfahren schützen - auch eine bcrypt-Hash, bei der eine moderne, teure CPU wenige tausend Kandidaten pro Sekunde generieren kann, nützt nicht, wenn das Passwort 4 oder 5 Stellen lang ist. Passphrases wiederum sind Sätze, die bewußt auf Sonderzeichen und ähnliches Verzichten, um merkbarer zu sein - gleichzeitig aber automatisch eine Länge erreichen, welche nicht mehr sinnvoll mit Bruteforcern oder Rainbowtables angegangen werden kann. Z.B. "Ich mag Eis" - 11 Stellen, Buchstaben, Groß- und Kleinschreibung, Leerstellen. Beim reinen Bruteforcen braucht ein System, welches ein Milliarde Kandidaten pro Sekunde generieren kann, 64 Tage (Rechenfehlervorbehalt). Das gleiche System müsste grob 20 mal so lange arbeiten, um eine entsprechende Rainbowtable zu erstellen. Um das noch sinnvoll machen zu können, bräuchte man in dem Fall 20-40 Grafikkarten, High-End, und das alles nur für einfache Verfahren wie NTLM (bzw. MD4) und MD5. Und die Tabelle wäre ein paar TB groß. Wie man sieht, wäre es hier einfach eine qualitativ gute deutsche Wortliste zu erstellen und einfach stets 2-3 Worte daraus zu nehmen und aneinander zu hängen, um einiges wirtschaftlicher. Und Deswegen gibt's nen Entwurf zum korrigieren, viel Spass :) --92.79.151.50 11:30, 18. Jun. 2010 (CEST)

Bild irreführend

Dadurch, dass in dem ersten Bild alle Passwörter auch nach einer Reduktionsfunktion super tolle und etwas dem Leser bekanntes bezeichnende Worte sind, wird suggeriert, dass die Reduktionsfunktion eine Umkehrung der Hashfunktion ist, die einem Hash ein gebräuchliches bzw. sinnvolles Wort zuweist. Soweit ich das weiß, berechnet sie aber einfach irgendein Wort (ob dieses nun sinnvoll ist oder nicht), mit dem weiter gehasht wird.

Ich schlage vor, ein Bild zu wählen, aus dem deutlich wird, dass diese Reduktionsfunktion auch im Prinzip nichts anderes als eine Hashfunktion ist, die aus einem beliebigen Hash ein Wort vorgegebener Länge berechnet, das keineswegs immer sinnvoll ist. Außerdem sollte das Bild vllt. mehr als 3 Iterationen enthalten, um den Vorteil deutlicher zu machen. Enthielte er zum Beispiel 5 Iterationen, könnte man im Text darauf bezug nehmen und sagen, dass man so mit von 2 Werten 5 Passwörter abdeckt. Und dann bitte auch mal konkrete Zahlen nennen, bitte nicht immer nur wie "k Wörter der Länge n, dann Zeitaufwand maximal k * log(n) / 2*n*k" mathematisch korrekt ausdrücken - denn so kann sich kein Normalsterblicher was drunter vorstellen. Einfach mal konkret 2, 3 Zahlen nennen, dass man eine Vorstellung bekommt. - Chris 06:20, 2. Jun. 2011 (CEST)

Weiterhin sollte ein neues Bild in der rechten Skönnte man ja nicht wissen, palte Hashwerte enthalten, nicht Klartextwerte. Denn in Rainbow Tables werden pro Kette der Klartext als Startwert und ein Hashwert als Endwert gespeichert. (nicht signierter Beitrag von SamRank (Diskussion | Beiträge) 09:12, 15. Sep. 2022 (CEST))

Im Bild ist ein Fehler: In Wirklichkeit sind alle Reduktionsfunktionen identisch. Das Bild suggeriert durch die Bezeichnungen R1, R2, R3, dass es unterschiedliche Funktionen seien. Damit zu einem Hash der passende Klartext gewonnen werden kann, müssen die Reduktionsfunktionen aber identisch sein, denn man reduziert und hasht den Hashwert so oft, bis der resultierende Hashwert in der rechten Spalte der Tabelle in irgendeiner Zeile erscheint. Man weiß nicht, in welcherSpalte der Tabelle sich der erste Hash befindet, deshalb wüsste man auch nicht, welche Reduktionsfunktion (R1, R2, ...) man anwenden müsste, wenn sie denn unterschiedlich wären. Die Reduktionsfunktionen müssen deshalb gleich sein.

Mein revert

[1] die urspruengliche version des einleitungssatzes war sprachlich korrekt (inhaltlich habe ich noch ergaenzt, dass das urbild mehrelementig ist). die reduktionsfunktion reduziert die laenge und hat nichts mit der komplexitaetstheoretischen reduktion zu tun, auf die verlinkt wurde. das verlinkte lemma "plan text" hatte ebenfalls nicht viel mit dem genannten plaintext (im sinne von urbild) zu tun. die ueberschrift "gegenmassnahmen" ist treffend, hingegen haben rainbow tables fast immer mit passwoertern zu tun, die neue ueberschrift war verwirrend. der einsatz von salt hat nicht das ziel, die generierung von rainbow tables "sicherer" zu machen. das eingefuegte "aber" ist sinnentstellend. --Mario d 16:23, 3. Jul. 2011 (CEST)

Einleitungssatz wa sprachlich inkorekt, hast du ja jezt aber nochmal ausgemerzt, is jetzt mit dem Urbild vl verständlicher. Glaubs mir, das "dem" war an der falschen Stelle (auch grammatikalisch), hat damit für mich den Lesefluss gehemmt.. Dass Du den Link mit der Reduktion (Theoretische_Informatik) entfernt hast, darüber kann man streiten. Ist doch eine Hashfunktion eine Funktin die das in der Reduktion gennate Prinzip anwendet: "Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen. Durch sie können die Berechenbarkeit oder die Komplexität von Problemen zueinander in Bezug gesetzt werden." Der Abschnitt, der jetzt wieder mit Gegenmaßnahmen betitelt ist: Wogegen sind diese Gegenmaßnahmen. Sie dienen dazu eine Hashfunktion unwirtschaftlich einzusetzen? Warm gibt es dann eine Hashfunktion? So wie jezt ist die Überschrift im Verhältnis zum Text ireführend. Leben wir doch in einer fast nur wirtschaftlich orientierten Gesellschaft. Welches Ziel hat Salt in Verbindng mit Gegenmaßnamen? Soll in dem Abschnitt erklärt werden, weshalb eine Rainbow Tabelle zu einer Hasfunktion statt für einen gesamten Text nur für Passwörter verwendet wird? Dann muss das so geschrieben werden. mfg.--Niesen 17:29, 3. Jul. 2011 (CEST)

die reduktionsfunktion koennte man auch "verkuerzungsfunktion" nennen, das hat mit dem zurueckfuehren eines problems auf ein anderes nichts zu tun. zu den gegenmassnahmen: ein passwort wird gehasht, weil die hashfunktion nicht umkehrbar ist. mit der rainbow table wird sie umgekehrt, die gegenmassnahmen sollen das verhindern, indem das erstellen der rainbow table aufwaendiger wird (mehrfaches iterieren der hashfunktion) und weniger ausbeute bringt (salt). danke fuer deine fragen, ich versuche mal, das einzubauen. --Mario d 17:54, 3. Jul. 2011 (CEST)

zu bruteforcen

Fallen da den Kryptographie-Experten keine verständlicheren Formulierungen ein? Das klingt schon sehr holprig und wie aus einem Nerd-Forum zitiert, was ja die Wikipedia eigentlich nicht sein soll. (nicht signierter Beitrag von 194.145.146.129 (Diskussion) 14:53, 30. Jul 2014 (CEST))

das stimmt, zumindest die einleitung sollte moeglichst wenige fachausdruecke verwenden. ist erledigt. --Mario d 12:54, 31. Jul. 2014 (CEST)

Name erklären

Kann jemand den Namen "Rainbow Table" erklären? Wo ist da eine Analogie zum Regenbogen? --Neitram ✉ 13:28, 1. Okt. 2014 (CEST)

Spät dran, aber ich versuch's mal: Die Rainbow Table ermöglicht es, Kennwörter und die zugehörigen Hashes in einer regenbogenartigen Art und Weise zu organisieren, nämlich in mehreren "Streifen". Jeder von diesen Streifen hat die Eigenschaft, dass er sich gut komprimieren lässt: so, wie man bei einem Regenbogenstreifen nur die Farbe wissen muss, um ihn zu malen, muss man sich bei Rainbow Tables nur den ersten und letzten Eintrag merken, um alle anderen Werte des Streifens effizient wiederherzustellen. Elektrolurch Kontakt 21:17, 18. Okt. 2016 (CEST)

Prima. Klingt plausibel. Wenn es dafür nun noch eine zitierfähige Quelle gibt, sollte diese Erklärung aber nicht auf der DS stehen, sondern im Artikel, oder nicht? --RokerHRO (Diskussion) 11:58, 4. Apr. 2017 (CEST)

Rainbow Tables _sind_ ein Time-Memory-Tradeoff!

Sie werden auch im entsprechenden Artikel als Beispiel für einen Time-Memory-Tradeoff aufgezählt. --RokerHRO (Diskussion) 11:57, 4. Apr. 2017 (CEST)