Frage:
Wie lange dauert es, um tatsächlich Regenbogentabellen zu erstellen?
stickman
2011-04-29 12:27:10 UTC
view on stackexchange narkive permalink

Ich habe über Regenbogentabellen 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 zu generieren einer? 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.

ABCEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890

Das klingt nach 26 + 26 + 10 = 62 Zeichen

Das bedeutet, dass ein Passwort mit einer Länge von 8 62 ^ 8 Kombinationen hat / p>

entspricht 218340105584896

Das allein klingt so, als würde die Generierung Ewigkeiten dauern. 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.

Die Antworten hier veranschaulichen deutlich, warum es nicht ausreicht, nur ein Passwort zu salzen. Sobald der Angreifer das Salz kennt, kann er in einer Stunde oder weniger genau dieses Passwort brutal erzwingen. Sie benötigen auch Iterationen (auch als Verstärkung, Dehnung bezeichnet), damit es lange dauert, jedes Passwort zu hashen. Siehe [wie man ein Passwort sicher speichert] (http://codahale.com/how-to-safely-store-a-password/). Dies alles ignoriert Software, die gut darin ist, Passwörter auszuwählen, die wahrscheinlicher sind, möglicherweise verschiedene Dinge, die über den Benutzer aus sozialen Netzwerken usw. bekannt sind.
Nicht so einfach: Sehen Sie [hier] (http://security.stackexchange.com/q/379/33), was Regenbogentabellen wirklich sind.
Vier antworten:
#1
+30
Thomas Pornin
2011-04-29 18:59:23 UTC
view on stackexchange narkive permalink

Eine Regenbogentabelle ist "nur" eine kompakte Darstellung einer Tabelle mit vorberechneten Hashwerten. Während des Aufbaus der Regenbogentabelle 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.

Grundsätzlich entsprechen die Kosten für die Erstellung einer Regenbogentabelle, die N -Kennwörter invertieren kann, in etwa den Kosten für das Ausprobieren dieser Kennwörter N Kennwörter über die Hash-Funktion - Der Punkt der Regenbogentabelle besteht darin, dass Sie sie einmal erstellen und dann mehrere Kennwörter auflösen können . (Um genau zu sein, aufgrund von Kettenkollisionen während der Tabellenkonstruktion liegen die Kosten tatsächlich näher bei 1,7 * N , aber lassen Sie uns dies im Moment ignorieren.)

Ich habe einmal machte einige Erfahrungen mit SHA-1. 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 Regenbogentabellen spielen keine Rolle) sind jedoch eine sehr parallele Aufgabe. Daher kann man die SSE2-Anweisungen verwenden, die 128-Bit-Register bieten und bei denen ein einzelner Opcode vier 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 zu ungefähr 48 Millionen gehashten Passwörtern pro Sekunde führt.

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 gehashte Passwörter pro Sekunde.

Mein PC und meine Grafikkarte stammen aus dem Frühjahr 2009 und sind nicht top-of-line. 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 etwa 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 demselben 2000-Faktor (so werden die "5 Tage" zu ungefähr 28 Jahre, buchstäblich "Alter", wie Sie es ausdrücken).

Ein Großteil der Hardware ging mir über den Kopf. Nur eine Frage, 28 Jahre für einen Computer - ich gehe davon aus, dass dies auf mehrere PCs aufgeteilt werden kann. Wenn Sie also sagen, 28 PCs, könnten Sie dies innerhalb eines Jahres tun? 28 PCs sind nicht viel, die meisten Unternehmen würden 28 PCs irgendwo herumliegen haben. Bedeutet das dann, dass jeder, der über ein paar tausend PCs verfügt, innerhalb weniger Tage ein Passwort knacken kann?
@stickman: ja, das bedeutet _parallel_: Wirf die doppelte Hardware ein und du gehst zweimal schneller. Und ja, jemand mit tausend PCs verfügt über eine hohe Fähigkeit zum Knacken von Passwörtern (insbesondere Studenten: Sie haben Freizeit, seltsame Vorstellungen darüber, wie diese Freizeit sinnvoll genutzt werden kann, und Zugang zu Universitätsmaschinen). Hash-Iterationen, die von guten Passwort-Hashing-Schemata verwendet werden, sind jedoch sehr effektiv.
Können wir irgendwo im Netz einen vorgefertigten Regenbogentisch finden?
@big-bird-from-middle-east: Eine einfache Google-Suche auf "Regenbogentabelle" zeigt auf http://project-rainbowcrack.com/table.htm, daher denke ich, dass die Antwort "Ja" lautet.
ich danke dir sehr!
Für ein Update: Zorinaqs [Whitepixel - GPU-beschleunigtes Passwort-Hash-Auditing] (http://whitepixel.zorinaq.com/) gilt als das schnellste in öffentlichen Benchmarks und leistet 33 Milliarden MD5 pro Sekunde auf einer 4 x AMD Radeon HD 5970 GPU ([Whitepixel v2] (http://blog.zorinaq.com/?e=43)), und er schätzte 10 Milliarden SHA-1 pro Sekunde, wenn er diese implementiert bekommt, und hat 1,1 Milliarden SHA-256 / s implementiert in unveröffentlichtem Code.
#2
+18
Jesper M
2011-04-30 12:47:19 UTC
view on stackexchange narkive permalink

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

Obwohl die obigen Antworten völlig korrekt 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-Spots aufspulen Instanzen für weniger als hundert Dollar. 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 Für einen bestimmten EC2-Server mit garantierter Verfügbarkeit ist der Preis 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, wenn das Überangebot dies zulässt In den freien Stunden können Sie es mit 40% -50% Rabatt erhalten.)

Das Erstellen von Regenbogentabellen kann parallel mit a erfolgen Die lineare Leistungssteigerung ist 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 dasselbe wie ein Server für 1.000 Stunden.

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

#3
+6
sarnold
2011-04-29 13:13:44 UTC
view on stackexchange narkive permalink

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

Ich könnte wahrscheinlich mein Programm verbessern, indem ich acht separate Programme ausführe , eine pro Hyperthread, um den Problembereich zu partitionieren. Wenn jedes Programm die Ausgabe auf seinem eigenen Laufwerk speichern würde, würde es nicht um die E / A-Bandbreite konkurrieren. Ich würde einen Faktor von vier bis sechs Beschleunigung im Vergleich zu meinem dummen Single-Thread-Programm für 4-6 Wochen Laufzeit erwarten. 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 wird ein 13 Byte langes C-Array, das zur Laufzeit modifiziert wurde, wahrscheinlich in viel weniger Speicher und natürlich ohne Speicherbereinigung ausgeführt als das Erstellen und Zerstören des Ruby-String-Objekte.)

Ich würde einen Nachmittag Arbeit erwarten und ein paar hundert Dollar neuer 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 Kennwörter. Skalieren Sie einfach meine Endergebnisse, um wie viel teurer Ihr Einweg-Hash ist als MD5. :)

"Niemand verwendet Single-Run-MD5 für Passwörter", wenn dies nur der Fall wäre.
LOL, es ist 2019 und ich schaue mir den Code an, der gerade im Jahr 2015 geschrieben wurde, so gut ... macht einen einzelnen MD5-Hash.Du wärest überrascht.
@AlexanderHiggins, Ich hoffe, Sie können im Rahmen Ihrer Arbeit auf argon2 oder ein ähnliches modernes Format umsteigen.(Aber hey, es könnte immer schlimmer sein, Sie könnten nach https://krebsonsecurity.com/2019/03/facebook-stored-hundreds-of-millions-of-user-passwords-in-plain-text- aufräumenjahrelang/ ).
Einverstanden.Ich bin zu diesem Link gekommen, um Hintergrundmaterial zu erhalten, das zeigt, warum Single MD5 schlecht ist.Übrigens, ich habe diesen Teil dieses Artikels geliebt. "Mein Facebook-Insider sagte, Zugriffsprotokolle zeigten, dass etwa 2.000 Ingenieure oder Entwickler ungefähr neun Millionen interne Abfragen für Datenelemente durchgeführt haben, die Klartext-Benutzerpasswörter enthielten."
@AlexanderHiggins, hoffentlich sind diese Hashcat-Timings für Sie nützlich: https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40 - 30 Milliarden Hash-Kandidaten pro Sekunde auf einer einzelnen Commodity-GPU.
#4
+1
nealmcb
2011-07-14 05:11:15 UTC
view on stackexchange narkive permalink

Siehe die Berechnungen der Hash-Rate meines Bitcoin-Mining-Netzwerks unter Wie werden Hash-Passwörter sicher gehasht? - IT-Sicherheit für das, was entschlossene Menschen mit moderneren GPU-Karten in Bezug auf Roh-Hashing erreichen können. Die Community läuft Anfang Juli 2011 mit 11 Thash / s (11 * 10 ^ 12 Hash / s) ....



Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...