it-swarm-eu.dev

Wie lange dauert es, um tatsächlich Rainbow-Tabellen zu generieren?

Ich habe über Rainbow-Tische gelesen, da ich denke, dass sie ziemlich interessant sind, weil sie eigentlich ein ziemlich einfaches Konzept sind.

Wie auch immer, ich habe mich gefragt, war jemand daran beteiligt, tatsächlich einen zu generieren? Wie wird es möglicherweise gemacht? Ich sehe nur nicht ein, wie es tatsächlich möglich ist, jede Kombination jedes Charakters zu erzeugen.

Wenn wir Sonderzeichen ausschließen, gibt es diese Anzahl von Zeichen.

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890

Das klingt nach 26 + 26 + 10 = 62 Zeichen

Das bedeutet, dass ein Passwort der Länge 8 62 ^ 8 Kombinationen hat.

das ist gleich 218340105584896

Das allein klingt so, als würde es ewig dauern, es zu generieren. Was ist, wenn wir die Anzahl der Zeichen auf 12 erhöhen und die Sonderzeichen hinzufügen (sagen wir, es gibt weitere 10 davon, wenn Sie sich nur die Zeichen ansehen, die Sie durch Drücken der Umschaltnummer erhalten)?

Wir würden 72 ^ 12 = 19408409961765342806016 erhalten

das ist eine Zahl, die groß genug ist, um Jahre zu bekommen.

27
stickman

Eine Rainbow-Tabelle ist "nur" eine kompakte Darstellung einer Tabelle mit vorberechneten Hash-Werten. Während der Erstellung der Rainbow-Tabelle werden viele mögliche Eingaben versucht und gehasht. Jede Eingabe, die während der Tabellenerstellung festgestellt wurde, wird mit dieser und keiner anderen Tabelle erfolgreich angegriffen. Die Hash-Bewertung konzentriert den größten Teil der Kosten für die Tabellenerstellung.

Im Grunde genommen entsprechen die Kosten für das Erstellen einer Rainbow-Tabelle, die [~ # ~] n [~ # ~] Passwörter invertieren kann, in etwa den Kosten für das Ausprobieren dieser [~ # ~] n [~ # ~] Passwörter durch die Hash-Funktion - der Punkt der Rainbow-Tabelle ist, dass Sie sie erstellen einmal und dann verwenden können, um = zu brechen mehrere Passwörter. (Um genau zu sein, aufgrund von Kettenkollisionen während der Tischkonstruktion liegen die Kosten tatsächlich näher bei 1,7 * N, aber lassen Sie uns dies für den Moment ignorieren.)

Ich habe einmal einige Erfahrungen mit SHA-1 gemacht. Ein einfacher Passwort-Hash mit SHA-1 hat die Kosten für die Verarbeitung eines einzelnen "Blocks" (SHA-1 verarbeitet wie MD5 Daten in 64-Byte-Blöcken), für den etwa 900 logische oder arithmetische 32-Bit-Operationen erforderlich sind. Eine optimierte Implementierung auf einem Intel Core2 x86-Prozessor kann dies in etwa 500 Taktzyklen tun. Kennwortangriffe (ob direkt oder für die Erstellung von Rainbow-Tabellen, es spielt keine Rolle) sind jedoch eine sehr parallele Aufgabe, sodass man die SSE2-Anweisungen verwenden kann, die 128-Bit-Register bieten und bei denen ein einzelner Opcode vier ausführen kann 32-Bit-Operationen gleichzeitig. SSE2 verfügt über weniger Arten von Operationen (insbesondere bietet es keine Rotationen, sondern nur Verschiebungen), sodass die Anzahl der Operationen auf etwa 1200 steigt. Unter bestimmten Umständen führt die SSE2-Einheit jedoch mehrere Opcodes gleichzeitig aus. Wir haben also 800 Taktzyklen für vier SHA-1-Instanzen parallel. Fazit: Mein PC ist ein Intel Core2 Q6600 mit vier Kernen und 2,4 GHz. Jeder Kern kann meine SSE2-Implementierung ausführen, was ungefähr 48 Millionen Hash-Passwörter pro Sekunde ergibt.

Ich habe auch eine nicht zu kleine Nvidia-Grafikkarte, und die GPU kann beliebigen Code über CUDA ausführen. Dies ist eine 9800 GTX + mit 128 Kernen bei 1,84 GHz. Jeder Kern kann eine 32-Bit-Operation pro Zyklus ausführen (es gibt eine hohe Latenz, aber dank der hohen Parallelisierung kann dieser Durchsatz von einem Befehl pro Zyklus beibehalten werden). Die Kerne kennen keine Rotationen, daher verwendet jeder Code 1200 Taktzyklen pro Hash-Passwort. Die Gesamtleistung beträgt 160 Millionen Hash-Passwörter pro Sekunde.

Mein PC und meine Grafikkarte stammen aus dem Frühjahr 2009 und sind nicht top. Man kann heutzutage für ein paar hundert Dollar eine GPU finden, die Passwörter ungefähr dreimal schneller hasht als meine 9800 GTX +. Nehmen wir also an, dass ein Angreifer mit einem gemeinsamen PC (der weniger als 1000 US-Dollar kostet) eine halbe Milliarde Passwörter pro Sekunde hashen kann.

Bei dieser Geschwindigkeit werden alle Passwörter mit 8 alphanumerischen Zeichen (Groß- und Kleinbuchstaben sowie Ziffern) in ca. 5 Tagen durchlaufen. Mit einem 1000 $ PC. Wenn Sie MD5 verwenden, sind die Dinge ungefähr 30% schneller (MD5 verwendet etwas weniger Operationen als SHA-1). Gute Passwort-Hashing-Schemata verwenden jedoch keinen einfachen Hash-Aufruf: Sie verwenden iteriertes Hashing mit beispielsweise 2000 verschachtelten Hash-Aufrufen: Dies multipliziert die Kosten für den Angreifer mit dem gleichen 2000-Faktor (sodass die "5 Tage" in etwa 28 umgewandelt werden) Jahre, buchstäblich "Alter", wie Sie es ausdrücken).

30
Thomas Pornin

Wie lange dauert es, eine Rainbow-Tabelle für einen sehr einfachen Hash mit nur einer einzigen Iteration zu generieren? Es dauert eine Stunde! Oder weniger, wenn Sie möchten.

Während die obigen Antworten völlig richtig sind, gibt es eine wichtige Entwicklung, die sie nicht erwähnen. Amazon EC2 und andere Cloud-Computing-Serveranbieter.

Heute kann jeder mit einer Kreditkarte zu aws.Amazon.com gehen und eine Handvoll EC2-Spot-Instanzen für weniger als hundert Dollar aufspulen. Wenn Sie einen guten CUDA-Code zur Verfügung haben, können Sie 50 der teureren "Cluster GPU" -Instanzen von Amazon mit zwei NVIDIA Tesla M2050-Grafikprozessoren mieten.

(Ähnlich wie bei den Fluggesellschaften hat Amazon differenzierte Preise. Wenn Sie einen bestimmten EC2-Server mit garantierter Verfügbarkeit benötigen, sind die Preise höher. Beispielsweise können Sie eine "Hi-CPU Large" -Instanz mit 8 virtuellen CPU-Kernen für 0,68 USD pro Stunde erwerben Wenn Sie bereit sind, dieselbe Instanz zu kaufen, die in den Öffnungszeiten als Überangebot zulässig ist, können Sie sie erhalten mit 40% -50% Rabatt .)

Das Erstellen von Rainbow-Tabellen kann parallel mit einer linearen Leistungssteigerung erfolgen, d. H. Wenn 100 Computer arbeiten, ist dies 100-mal schneller als bei einem einzelnen Computer.

Amazon berechnet Ihnen keine Gebühren pro Instanz, Gebühren pro Instanzstunde. Das Ausführen von 1.000 Servern für eine Stunde kostet also das gleiche wie ein Server für 1.000 Stunden.

Die Parallelität der Erstellung von Rainbow-Tabellen in Verbindung mit Diensten wie Amazon EC2 bedeutet, dass es keine Frage mehr gibt, wie lange es dauert. Es gibt ein "Wie viel sind Sie bereit zu zahlen, um es zu bekommen schnell, anstatt weniger zu bezahlen und es in ein paar Tagen zu bekommen?". Der Unterschied in Kosten und Zeit ergibt sich hauptsächlich aus der Preisdifferenzierung von Amazon zwischen "regulären" EC2-Instanzen und den billigeren "Spot-Instanzen".

18
Jesper M

Mit einem einfachen 26 ^ 5-Testlauf konnte ich eine ascii hex-Tabelle in Ruby] generieren, die 228488 MD5-Ausgaben pro Sekunde generierte. Alle 11881376-Einträge dauerten 52 Sekunden auf meinem 1,5 Jahre alten Core i7. Wenn ich mein Programm nicht verbessert hätte, würde ich erwarten, dass es 26 Wochen lang läuft, um Ihre 62 ^ 8-Liste zu erstellen.

Ich könnte wahrscheinlich Verbesserungen an meinem Programm vornehmen, indem ich acht separate Programme ausführe, eines pro Hyperthread, um den Problembereich zu partitionieren. Wenn jedes Programm die Ausgabe auf seinem eigenen Laufwerk speichern würde, würden sie nicht um IO Bandbreite) konkurrieren. Ich würde einen Faktor von vier bis sechs beschleunigen, verglichen mit meinem dummen Single-Thread-Programm für 4-6 Wochen Laufzeit. Wenn ich in C neu schreiben würde, könnte ich einen weiteren Beschleunigungsfaktor von 1,5 erwarten. (Vielleicht mehr? Einerseits ist es ein einfaches Programm, andererseits ein 13 Byte langes C-Array, das zur Laufzeit modifiziert wird. wird wahrscheinlich in viel weniger Speicher und natürlich ohne Speicherbereinigung ausgeführt, verglichen mit dem Erstellen und Zerstören der Ruby String-Objekte.)

Ich würde einen Nachmittag Arbeit erwarten und ein paar hundert Dollar neue Ausrüstung würden es mir ermöglichen, die 62 ^ 8 Tische zwei Wochen mit Standardhardware fertigzustellen.

Und sicher, niemand verwendet Single-Run-MD5 für Passwörter. Skalieren Sie einfach meine Endergebnisse, um wie viel teurer Ihr One-Way-Hash ist als MD5. :) :)

6
sarnold

Weitere Informationen zu den Hash-Raten-Berechnungen meines Bitcoin-Mining-Netzwerks finden Sie unter Wie werden Passwörter sicher gehasht? - IT-Sicherheit , was bestimmte Personen mit moderneren GPU-Karten in Bezug auf Raw-Hashing leisten können. Die Community läuft Anfang Juli 2011 mit 11 Thash/s (11 * 10 ^ 12 Hash/s) ....

1
nealmcb