Was sind Regenbogentische und wie werden sie verwendet?

Regenbogentabellen werden häufig mit verwechselt eine andere, einfachere Technik, die Rechenzeiten nutzt Torage-Kompromiss bei der Kennwortwiederherstellung: Hash-Tabellen.

Hash-Tabellen werden erstellt, indem jedes Wort in einem Kennwortwörterbuch gehasht wird. Die Passwort-Hash-Paare werden in einer Tabelle gespeichert, sortiert nach Hash-Wert. Um eine Hash-Tabelle zu verwenden, nehmen Sie einfach den Hash und führen Sie eine binäre Suche in der Tabelle durch, um das ursprüngliche Passwort zu finden, falls vorhanden.

Regenbogentabellen sind komplexer. Das Erstellen einer Regenbogentabelle erfordert zwei Dinge : eine Hashing-Funktion und eine Reduktionsfunktion. Die Hashing-Funktion für einen bestimmten Satz von Regenbogentabellen muss mit dem Hash-Passwort übereinstimmen, das Sie wiederherstellen möchten. Die Reduktionsfunktion muss einen Hash in etwas umwandeln, das als Passwort verwendet werden kann. Eine einfache Reduktionsfunktion ist Base64 Codieren Sie den Hash und kürzen Sie ihn dann auf eine bestimmte Anzahl von Zeichen.

Regenbogentabellen bestehen aus „Ketten“ einer bestimmten Länge: beispielsweise 100.000. Um die Kette zu erstellen, wählen Sie einen zufälligen Startwert aus Wenden Sie die Hashing- und Reduktionsfunktionen auf diesen Startwert und seine Ausgabe an und wiederholen Sie die 100.000-fache Iteration. Nur der Startwert und der Endwert werden gespeichert. Wiederholen Sie diesen Vorgang, um so viele Ketten wie gewünscht zu erstellen.

So stellen Sie a wieder her Passwort mit Rainbow Tables wird der Passwort-Hash durchlaufen der obige Vorgang für die gleiche Länge: in diesem Fall 100.000, aber jedes Glied in der Kette bleibt erhalten. Jedes Glied in der Kette wird mit dem Endwert jeder Kette verglichen. Wenn es eine Übereinstimmung gibt, kann die Kette rekonstruiert werden, wobei sowohl die Ausgabe jeder Hashing-Funktion als auch die Ausgabe jeder Reduktionsfunktion beibehalten werden. Diese rekonstruierte Kette enthält den Hash des betreffenden Kennworts sowie das Kennwort, mit dem es erstellt wurde.

Die Stärken einer Hash-Tabelle bestehen darin, dass die Wiederherstellung eines Kennworts blitzschnell ist (binäre Suche) und die Person erstellt Die Hash-Tabelle kann auswählen, was darin enthalten ist, z. B. die Top-10.000-Passwörter. Die Schwäche im Vergleich zu Rainbow Tables besteht darin, dass Hash-Tabellen jedes einzelne Hash-Passwort-Paar speichern müssen.

Rainbow Tables haben den Vorteil, dass die Person, die diese Tabellen erstellt, durch Auswahl der Anzahl der Links auswählen kann, wie viel Speicher benötigt wird jede Kette. Je mehr Verknüpfungen zwischen dem Startwert und dem Endwert bestehen, desto mehr Kennwörter werden erfasst. Eine Schwäche ist, dass die Person, die die Ketten erstellt, die von ihnen erfassten Passwörter nicht auswählt, sodass Rainbow Tables nicht für gängige Passwörter optimiert werden können. Bei der Kennwortwiederherstellung werden auch lange Ketten von Hashes berechnet, was die Wiederherstellung zu einem teuren Vorgang macht. Je länger die Ketten sind, desto mehr Passwörter werden in ihnen erfasst, aber es wird mehr Zeit benötigt, um ein Passwort darin zu finden.

Hash-Tabellen eignen sich für gängige Passwörter, Rainbow-Tabellen eignen sich für sichere Passwörter. Der beste Ansatz wäre, so viele Passwörter wie möglich mithilfe von Hash-Tabellen und / oder herkömmlichem Cracken mit einem Wörterbuch der Top-N-Passwörter wiederherzustellen. Verwenden Sie für diejenigen, die noch übrig sind, Regenbogentabellen.

Kommentare

• Oh meine Güte, ich gebe zu, schockiert zu sein – ich diskutiere und erkläre alle Regenbogentabellen Zeit, und die ganze Zeit scheint es, dass ich einer der “ häufig verwirrten “ gewesen bin! Ich würde total +1000 Mal, ich habe hier wirklich etwas Neues gelernt (und ich dachte, ich wüsste die Antwort). Ich bin froh, dass ich die Frage gestellt habe … Danke!
• Um genau zu sein (jetzt, wo du meine Augen geöffnet hast, habe ich etwas mehr recherchiert :)), unterscheiden sich Rainbow Tables von Hellman Hash Chains durch die Verwendung mehrere verschiedene Reduktionsfunktionen. In der Tat komplexer … aber wirklich eine sehr schöne Idee (Ah! Ist das , warum sie ‚ “ Rainbow “ Tabellen?)
• Ich stimme zu, dass dies eine sehr gute Erklärung ist. In meiner Antwort habe ich es einfach erklärt und es auch wirklich falsch erklärt, indem ich zu einfach war.Das Schöne an Regenbogentabellen ist die Tatsache, dass sie nicht jeden Hash-Wert speichern. Ich werde meine bearbeiten, aber auch darüber abstimmen, da dies definitiv eine bessere Erklärung ist.
• Hmm … Je mehr ich darüber nachdenke, desto realer sind Rainbow Tables in realen Systemen bei weitem nicht Hash-Tabellen. Wie Sie bereits sagten, sind Hash-Tabellen für gängige Kennwörter viel besser (da sie um eine Größenordnung schneller sind und die Größenanforderungen für ein Kennwortwörterbuch natürlich viel kleiner sind als der gesamte mögliche Bereich von Kennwörtern). Und wen ‚ machen wir Witze? Die meisten Passwörter fallen in diese Kategorie. Es ist sehr selten (und wird es einige Zeit dauern), dass Sie RT anrufen müssen.
• Leider haben Sie mich hier verloren: “ Um ein Kennwort mithilfe von Rainbow Tables wiederherzustellen, wird das Kennwort für dieselbe Länge dem oben beschriebenen Vorgang unterzogen. “ Wie kann das Kennwort den Vorgang durchlaufen, wenn es ‚ ist nicht einmal bekannt? Meinten Sie den Passwort-Hash? Außerdem gibt es ‚ Folgendes: “ Jedes Glied in der Kette wird mit dem Endwert jeder Kette verglichen. “ Ich kann keine Situation erkennen, in der ein Glied in der Kette mit dem Endwert in der Kette übereinstimmen würde, da der Gliedwert kontinuierlich gehasht und reduziert würde.

Es gibt viele gute Erklärungen für Regenbogentabellen. Diese Funktionsweise von Regenbogentabellen ist besonders gut. Auch der Wikipedia-Artikel hat eine sehr gute Erklärung. Für eine etwas ausführlichere Lektüre lautet das endgültige Dokument zu diesem Thema Ein schnellerer kryptoanalytischer Zeit-Speicher-Kompromiss .

Eine einfache Erklärung für Regenbogentabellen ist, dass sie eine Zeitspeicher-Kompromissmethode verwenden. Das heißt, anstatt einen Ziel-Hash-Wert und ein Wörterbuch von Wörtern zu nehmen, dann jedes Wort zu hashen und den Vergleich im laufenden Betrieb durchzuführen (Brute-Force-Ansatz mit etwas wie John ), Sie haben stattdessen alle Werte im Wörterbuch im Voraus gehasht (dies kann je nach Wörterbuchgröße sehr lange dauern). Sobald dies erledigt ist, können Sie so viele Hashes wie Sie möchten mit den vorab gehashten Werten in den Regenbogentabellen vergleichen. Dies ist erheblich schneller als die erneute Berechnung der Hashes.

Die Erklärung, die ich hier zuvor in geschrieben habe Das Bemühen, kurz zu sein, war irreführend, da es nicht die Verwendung von Reduzierungen erklärte, die Regenbogentabellen verwenden. Für eine bessere Erklärung, bis ich dieses Bit umschreibe, siehe @ Crunge-Antwort .

Sie können die Regenbogentabellen entweder selbst mit einer Anwendung wie RainbowCrack oder Sie können sie aus Quellen wie The Shmoo Group , Kostenlose Rainbow Tables -Projektwebsite, Ophcrack -Projekt und viele andere Orte, je nachdem, für welche Art von Hashes Sie Tabellen benötigen.

Zum Schutz vor einem auf Rainbow Table basierenden Angriff besteht die effektivste Methode zur Bekämpfung darin, sicherzustellen, dass jeder Hash in einem System gesalzen ist . Dies macht vorgenerierte Regenbogentabellen unbrauchbar und würde bedeuten, dass ein Angreifer einen benutzerdefinierten Satz von Tabellen generieren müsste, um sie gegen die Ziel-Hashes zu verwenden. Dies wäre nur möglich, wenn er das Salz kennt.

Kommentare

• Wenn Sie für jedes Kennwort ein anderes Salt verwenden und es unverschlüsselt in der Datenbank aufzeichnen, wird das Angegriffene müssten für jeden Hash einen benutzerdefinierten Satz von Tabellen generieren, der das Ziel der Übung zunichte macht. Der Sinn der Regenbogentabelle besteht darin, den gesamten Passwortraum brutal zu erzwingen und dann alle Passwörter für eine Brute-Force abzurufen Anstrengung; Wenn Sie ‚ nur ein Passwort pro Regenbogentabelle erhalten, können Sie den Hash genauso gut direkt brutal erzwingen.

Zweck und Relevanz

Regenbogentabellen helfen dabei, schwierige Passwörter zu knacken, dh solche, die nicht einmal in einem großen Wörterbuch gefunden werden können. Passwörter wurden in der Vergangenheit als einfache Hashes in Datenbanken gespeichert. Dies ist der Grund, warum Regenbogentabellen wirksam sind: Erstellen Sie eine einzelne Regenbogentabelle (langsam) und führen Sie eine beliebige Anzahl von Datenbanken mit Hashes aus (schnell).

Heutzutage verwenden immer mehr Systeme geeignete Kennwortspeicheralgorithmen wie Bcrypt, Scrypt oder Argon2. Siehe: Wie können Kennwörter sicher [gespeichert] werden? Diese Algorithmen sind Nicht mehr „anfällig“ für Regenbogentabellen: Da jeder Hash eindeutig ist, funktionieren Regenbogentabellen auch dann nicht mehr, wenn die Passwörter gleich sind.

Deshalb sind Regenbogentabellen heute unbeliebt.Auch wenn etwas Modernes wie Argon2 nicht verwendet wird, wissen Entwickler heutzutage normalerweise, dass sie zumindest ein Salz verwenden sollten. Das reicht bereits aus, um eine Regenbogentabelle unbrauchbar zu machen.

Funktionsweise

Erstellen einer Tabelle

Stellen Sie sich vor, wir erstellen eine Regenbogentabelle mit nur zwei Ketten mit einer Länge von jeweils 5. Die Regenbogentabelle ist für die fiktive Hash-Funktion MD48 vorgesehen, die 48 Bit (nur 12 hexadezimale Zeichen) ausgibt. Beim Erstellen der Kette sehen wir Folgendes:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

Wir beginnen mit 0, da dies die erste Kette ist (Wir brauchen nur einen Wert, um damit zu beginnen.) Wenn wir dies mit MD48 hashen, wird daraus cfcd208495d5. Jetzt wenden wir eine „redu“ -Funktion an, die diesen Hash im Grunde wieder in a formatiert Passwort, und wir erhalten „z“. Wenn wir das erneut hashen, erhalten wir fbade9e36a3f, reduzieren es dann erneut und erhalten renjaj820 Es gibt noch einige Zyklen, und das Endergebnis ist WLgOSj.

Gleiches gilt für die zweite Kette. Wir beginnen einfach mit einem anderen Wert und machen dasselbe. Dies endet mit 0uUoAD.

Unsere vollständige Regenbogentabelle lautet nun:

WLgOSj => 0 0uUoAD => 1 

Das ist alles, was Sie speichern müssen.

Nachschlagen eines Hashs

Nehmen wir an, wir haben online einen Hash gefunden, 7668b2810262. Lassen Sie uns ihn anhand unserer Tabelle knacken!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

Um selbst damit herumzuspielen, wurden die obigen Beispiele mit diesem Python-Skript erstellt: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Skalierungseigenschaften

Kurz gesagt:

• Schnelle Suchvorgänge bedeuten größere Tabellen, vorausgesetzt, die Abdeckung bleibt gleich.
• Bessere Abdeckung bedeutet entweder langsamere Suchvorgänge oder größere Tabellen.
• Kleinere Tabellen bedeuten entweder langsamere Suchvorgänge oder schlechtere Abdeckung.

In den folgenden Abschnitten wird davon ausgegangen, dass die Zeit pro Hash + -Reduktion 1 µs beträgt und Kollisionen nicht berücksichtigt werden. Dies sind alles Standardnummern, die als Beispiele und nicht als exakte Werte gedacht sind.

Suchzeit

Wenn eine Hash + -Reduktionsoperation eine Mikrosekunde dauert, würde das Generieren einer Tabelle mit einer Million Ketten und 10 000 Reduktionen pro Kette ungefähr 3 Stunden dauern:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 Stunden.

Das Nachschlagen in dieser Tabelle dauert durchschnittlich 10 Millisekunden. Dies liegt daran, dass wir normalerweise chain_length/2 -Reduktionen durchlaufen müssen, bevor wir herausfinden, welche Kette den Hash enthält. Beispielsweise müssen wir möglicherweise 3000 Reduzierungen für einen Hash vornehmen, bevor wir einen Wert finden, der in der Tabelle enthalten ist. Als nächstes müssen wir diese Kette von Anfang an wiederholen, bis wir den passenden Wert gefunden haben. Wenn wir nur 3000 tun mussten, um es in unserer Tabelle zu finden, müssen wir von Anfang an 7000 Reduzierungen vornehmen, um zum richtigen Punkt in der Kette zu gelangen. Grundsätzlich führen wir beim Nachschlagen so viele Operationen aus wie beim Generieren einer einzelnen Kette. Daher beträgt die Suchzeit das 10 000-fache einer Mikrosekunde, dh zehn Millisekunden (oder eine Centisekunde, wenn Sie so wollen).

Speicheranforderungen

Wenn Sie eine vollständige, schnelle Nachschlagetabelle für eine Hash-Funktion erstellen möchten, selbst für MD5, benötigen Sie „immer noch hundert Milliarden Milliarden Terabyte Speicher.“ s nicht sehr hilfreich. Aber was ist, wenn wir nur Passwörter in Kleinbuchstaben bis zu 10 Zeichen behandeln möchten?

Wenn wir höchstens 30 Sekunden nach einem Hash suchen möchten und davon ausgehen, dass wir 1 Mikrosekunde (eine Millionstel Sekunde) pro Hash benötigen + Zyklus reduzieren, dann können wir eine Kettenlänge von: 1 million × 30 = 30 Millionen haben. Es gibt 26 ¹⁰ (oder 10 ¹⁴ ) mögliche Kleinbuchstaben mit 10 Zeichen, und pro Kette decken wir 30 Millionen Werte ab. Damit haben wir 4 Millionen Ketten. Wir wissen, dass in jeder Kette nur ein Start- und ein Endwert gespeichert sind und dass die Werte jeweils 10 Zeichen umfassen. 2 × 10 × 4 million = 76 MiB-Daten.

Das Generieren der Tabelle durch Durchlaufen aller Kennwörter mit 10 Zeichen dauert lange: 30 Sekunden pro Kette, mal 4 Millionen Ketten ungefähr 91 Jahre. Viele Leute wären jedoch an einer solchen Tabelle interessiert. Wenn Sie also 1092 CPUs (= 91 × 12) zusammenlegen, dauert dies nur 1 Monat. Dies zeigt, wie klein eine solche Tabelle mit dem darin enthaltenen Kennwortbereich verglichen werden kann: Suchvorgänge dauern nur 30 Sekunden und Sie müssen nur 76 MB Daten speichern.

Schlussfolgerung

Regenbogentabellen können sein Wird als Zeit-Speicher-Kompromiss betrachtet : Man speichert nur einen kleinen Teil der Tabelle und stellt ihn durch zusätzliche Berechnungen zur Suchzeit wieder her. Dies ist einer der Gründe, warum Salze oder besser gesagt ein guter Passwortspeicheralgorithmus wie Scrypt oder Argon2 wichtig sind, um Passwörter sicher zu halten.Eine Regenbogentabelle kann ein gesalzenes Passwort nur wiederherstellen, wenn die Tabelle einen Eintrag enthält, der groß genug ist, um sowohl das Salt als auch das Passwort zu enthalten. Dies wäre extrem ineffizient und würde den gesamten Zweck zunichte machen.

Beachten Sie, dass bei der Verschlüsselung etwas Ähnliches gilt: Wenn Benutzer Dateien mit einem Kennwort verschlüsseln, kann eine Regenbogentabelle erstellt werden, um die Dateien zu knacken. Angenommen, die Software verwendet AES, und der erste Block der Datei sollte mit dem vom Benutzer angegebenen Kennwort auf „Kennwortkorrektur“ entschlüsselt werden. In einer Regenbogentabelle wird dann AES anstelle einer Hash-Funktion verwendet.

Wenn Sie mit einem Kennwort umgehen (ein Geheimnis von unbekannter Stärke, insbesondere wenn der Benutzer es möglicherweise wiederverwendet), führen Sie es immer durch einen geeigneten (langsamen) Kennwortspeicheralgorithmus, um es langsam und eindeutig zu knacken. P. >

Kommentare

• Gute Erklärung. Wenn ich das richtig verstanden habe, liegt die Kraft von Regenbogentischen in einer guten Reduktionsfunktion, oder? Wie komme ich auf eine gute? Und wie vermeide ich Kollisionen für alle Kandidaten in den Ketten?
• @ Kyu96 Gute Fragen! Ich kenne die Antwort nicht ‚, aber es würde mich interessieren, wenn Sie eine finden. Auf dieser Seite geht es nur um die allgemeine Frage, was eine Regenbogentabelle ist, und nicht um Einzelheiten wie das Entwerfen eines Algorithmus. Sie sollten eine neue Frage öffnen , aber auf dieser Website geht es darum, “ Assets vor digitalen Bedrohungen zu schützen “ (iirc ). Ich denke, es wäre ein Thema für unsere Schwesterseite crypto.stackexchange.com , bei der es um “ geht die Mathematik und Eigenschaften kryptografischer Systeme, ihre Analyse (“ Kryptoanalyse „) und Nebenthemen, aus denen Kryptologie im Allgemeinen besteht, wie z. B. Zufallszahlen Generation. “