it-swarm-eu.dev

Was sind Regenbogentische und wie werden sie verwendet?

Wo finde ich einen? Gibt es am Ende einen Topf voll Gold?
Wie schütze ich mich vor ihnen?


Aus dem Area51-Vorschlag

Diese Frage war IT-Sicherheitsfrage der Woche.
Lesen Sie den 9. September 2011 Blogeintrag für weitere Details oder eigene einreichen Frage der Woche.

149
AviD

Rainbow-Tabellen werden häufig mit einer anderen, einfacheren Technik verwechselt, die einen Kompromiss zwischen Rechenzeit und Speicher bei der Kennwortwiederherstellung nutzt: 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 es vorhanden ist.

Regenbogentabellen sind komplexer. Das Erstellen einer Rainbow-Tabelle erfordert zwei Dinge: eine Hashing-Funktion und eine Reduktionsfunktion. Die Hashing-Funktion für einen bestimmten Satz von Rainbow-Tabellen muss mit dem Hash-Passwort übereinstimmen, das Sie wiederherstellen möchten. Die Reduktionsfunktion muss einen Hash in etwas verwandeln, das als Passwort verwendet werden kann. Eine einfache Reduktionsfunktion besteht darin, den Hash von Base64 zu codieren und dann auf eine bestimmte Anzahl von Zeichen abzuschneiden.

Regenbogentische bestehen aus "Ketten" einer bestimmten Länge: beispielsweise 100.000. Um die Kette zu konstruieren, wählen Sie einen zufälligen Startwert. Wenden Sie dann die Hashing- und Reduktionsfunktionen auf diesen Startwert und seine Ausgabe an und iterieren Sie 100.000 Mal weiter. Nur der Startwert und der Endwert werden gespeichert. Wiederholen Sie diesen Vorgang, um beliebig viele Ketten zu erstellen.

Um ein Kennwort mithilfe von Rainbow Tables wiederherzustellen, wird der Kennwort-Hash für dieselbe Länge wie oben beschrieben ausgeführt: 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 Passworts sowie das Passwort, das sie erstellt hat.

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

Regenbogentabellen haben den Vorteil, dass die Person, die diese Tabellen erstellt, durch Auswahl der Anzahl der Glieder in jeder Kette auswählen kann, wie viel Speicher benötigt wird. 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 Kennwörter, Rainbow-Tabellen für sichere Kennwö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 die verbleibenden Regenbogentabellen.

180
Crunge

Es gibt viele gute Erklärungen dafür, was Rainbow-Tabellen sind. Diese Funktionsweise von Rainbow-Tabellen 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 Papier zu diesem Thema Einen schnelleren kryptoanalytischen Zeit-Speicher-Kompromiss eingehen .

Eine einfache Erklärung für Regenbogentabellen ist, dass sie eine Zeitgedächtnis-Kompromiss-Technik verwenden. Das heißt, anstatt einen Ziel-Hash-Wert und ein Wörterbuch mit Wörtern zu nehmen, dann jedes Wort zu hashen und den Vergleich im laufenden Betrieb durchzuführen (Brute-Force-Ansatz mit etwas wie John ), hassten Sie stattdessen alle Werte im Wörterbuch im Voraus (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 Rainbow-Tabellen vergleichen. Dies ist erheblich schneller als die erneute Berechnung der Hashes.

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

Sie können die Rainbow-Tabellen entweder selbst mit einer Anwendung wie RainbowCrack generieren oder sie aus Quellen wie The Shmoo Group , Free Rainbow Tables project herunterladen Website, 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 Rainbow-Tabellen 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.

15
Mark Davidson

Zweck und Relevanz

Regenbogentabellen helfen dabei, schwierige Passwörter zu knacken, d. H. Solche, die in einem großen Wörterbuch nicht einmal zu finden sind. Passwörter wurden in der Vergangenheit als einfache Hashes in Datenbanken gespeichert. Dies ist der Effekt von Rainbow-Tabellen: Erstellen Sie eine einzelne Rainbow-Tabelle (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 für Rainbow-Tabellen nicht mehr "anfällig": Da jeder Hash eindeutig ist, auch wenn die Kennwörter gleich sind, werden Rainbow-Tabellen-Nr längere Arbeit.

Deshalb sind Rainbow-Tische heute unbeliebt. Auch wenn etwas Modernes wie Argon2 nicht verwendet wird, wissen Entwickler heutzutage normalerweise, dass sie zumindest ein Salz verwenden sollten. Das reicht schon aus, um einen Rainbow-Tisch unbrauchbar zu machen.

Wie sie arbeiten

Erstellen einer Tabelle

Stellen Sie sich vor, wir erstellen eine Rainbow-Tabelle mit nur zwei Ketten mit einer Länge von jeweils 5. Die Rainbow-Tabelle ist für die fiktive Hash-Funktion MD48 vorgesehen, die 48 Bit (nur 12 hexadezimale Zeichen) ausgibt. Beim Aufbau 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, Weil es 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 "Reduzieren" -Funktion an, die diesen Hash im Grunde genommen wieder in ein Passwort formatiert, und am Ende erhalten wir "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.

Unser kompletter Regenbogentisch lautet jetzt:

WLgOSj => 0
0uUoAD => 1

Das ist alles was Sie aufbewahren müssen.

Nach einem Hash suchen

Nehmen wir an, wir haben online einen Hash gefunden, 7668b2810262. Lass es uns mit unserem Tisch 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: https://Gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb erstellt )

Skalierungseigenschaften

Zusamenfassend:

  • 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 eine 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 Baseball-Nummern, die als Beispiele dienen und keine exakten Werte.

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, was 10 Millisekunden entspricht (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. Das ist nicht sehr hilfreich. Aber was ist, wenn wir nur Kleinbuchstaben bis zu 10 Zeichen behandeln möchten?

Wenn wir höchstens 30 Sekunden damit verbringen möchten, nach einem Hash zu suchen, und davon ausgehen, dass wir 1 Mikrosekunde (eine Millionstel Sekunde) pro Hash + Reduktionszyklus benötigen, können wir eine Kettenlänge von: 1 million × 30 = 30 Millionen haben . Es gibt 2610 (oder 1014) 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. Also 2 × 10 × 4 million = 76 MiB Daten.

Das Generieren der Tabelle durch Durchlaufen aller 10-stelligen Passwörter dauert lange: 30 Sekunden pro Kette, mal 4 Millionen Ketten sind 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.

Fazit

Regenbogentabellen können als Zeit-Speicher-Kompromiss betrachtet werden: Man speichert nur einen kleinen Teil der Tabelle und stellt sie durch zusätzliche Berechnung der 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 Rainbow-Tabelle 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 Rainbow-Tabelle 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 Rainbow-Tabelle wird dann AES anstelle einer Hash-Funktion verwendet.

Wenn Sie mit einem Kennwort umgehen (ein Geheimnis von unbekannter Stärke, und 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.

7
Luc