Nehmen wir an, sie haben zufällig alphanumerisch (A-Za-z0-9 keine Symbole) für Salt und Passwort ausgewählt. B. ist der Probenraum (62) ^ M mögliche Salze und (62) ^ N Passwörter.

Angenommen, sie verfügen über eine Million GPUs in einer Farm, die jeweils eine Milliarde Hashes pro Sekunde generieren können (vorausgesetzt, einfache Hashes vom Typ MD5 oder SHA - bcrypt- oder PBKDF-basierte Hashes sind viel langsamer). Für ein bestimmtes Salz können sie also ein 8-stelliges Passwort in 0,2 Sekunden (200 000 GPU-Sekunden), ein 10-stelliges Passwort in 14 Minuten (26 GPU-Jahre) und ein 12-stelliges Passwort in 37 Tagen (100 000 GPU) knacken -Jahre), ein 16-stelliges Passwort in 1,5 Millionen Jahren (1,5 Billionen GPU-Jahre).

Oder eine andere Art, darüber nachzudenken; Eine typische GPU, die eine Milliarde Hashes pro Sekunde erzeugt, verbraucht ~ 200 W. Wenn Strom also 0,10 USD pro kWh kostet und die Startkosten vernachlässigt werden, kostet eine GPU-Stunde 0,02 USD. Ein 8-stelliges Passwort kostet also ~ 1 USD, 10-stellige 4600 USD, 12-stellige 18 Millionen USD, 16 Zeichen - 260 Billionen USD (die weltweite Geldmenge liegt in der Größenordnung von 10 Billionen USD). (Und dies vernachlässigt die Kosten für den Kauf / die Wartung einer Million GPUs - nur Strom).

Wie bei einem Regenbogentisch muss er irgendwann gebaut werden. Sie möchten also eine vollständige Regenbogentabelle für alle 4 Zeichenpräfixe. Wenn Sie alle Passwörter mit bis zu 8 Zeichen (z. B. insgesamt 12 Zeichen) abdecken möchten, dauert dies 100 000 GPU-Jahre (37 Tage mit einer Million GPUs) und kostet etwa 18 Millionen US-Dollar an Stromrechnung.

Wenn M + N> ~ 12 für zufällige alphanumerische Zeichen ist, wird es grundsätzlich nicht mehr durchführbar (z. B. bei M + N = 16 nicht durchführbar). Beispiel: 8 A-Za-z0-9 bedeutet 8 Großbuchstaben + Kleinbuchstaben + numerisches Passwort.
Ebenfalls enthalten ist ein google-anwendungsspezifisches Passwort (16 zufällige Kleinbuchstaben), obwohl offensichtlich Google-Typ Das Kennwort muss normalerweise online angegriffen werden (nicht wie ein Offline-Hash, der von einer GPU-Farm angegriffen wird).

  PW Länge | Anzahl der PW | PW Entropie | GPU-Zeit | Stromkosten bei 0,10 USD / kWh ------------------------------------------ --------------------------------------------- 8 A-Za-z0-9 | 2x10 ^ 14 | 47,6 Bit | 60 Stunden | $ 110 A-Za-z0-9 | 8x10 ^ 17 | 59,5 Bit | 26 Jahre | $ 4 60012 A-Za-z0-9 | 3x10 ^ 21 | 71,4 Bit | 100 000 Jahre | 18 000 000 USD (18 Mio. USD) 14 A-Za-z0-9 | 1x10 ^ 25 | 83,4 Bit | 390 Millionen Jahre | 69 000 000 000 USD (69 Mrd. USD) 16 A-Za-z0-9 | 5x10 ^ 28 | 95,2 Bit | 1500 Milliarden Jahre | 260 000 000 000 000 (260 Billionen US-Dollar) ---------------------------------- -------------------------------------------------- ------- 16 az | 4x10 ^ 22 | 75,2 Bit | 1,4 Millionen Jahre | 242 000 000 USD (242 Mio. USD)  

Ich entschuldige mich im Voraus, da diese Antwort keine direkte Antwort auf Ihre Frage ist, aber ich wollte sie veröffentlichen, damit die Leute wissen, dass die Frage, die Sie stellen, wirklich nur eine akademische ist. Die eigentliche Antwort auf diese Frage lautet: Verwenden Sie nicht sha1, sondern bcrypt. Die sha1 und md5 der Welt wurden so konzipiert, dass sie schnell und schnell sind. Dies ist keine gute Qualität für das Hashing von Passwörtern. Bcrypt ermöglicht die Konfiguration der Zeit, die zum Hashing eines Kennworts benötigt wird, sodass Sie den Hashing-Prozess so weit verlangsamen können, dass Benutzer den Unterschied nicht bemerken, ein Angreifer jedoch um Größenordnungen mehr Zeit benötigt Generieren Sie eine Regenbogentabelle oder erzwingen Sie ein Passwort. Weitere Informationen zu bcrypt und warum Sie es verwenden sollten, finden Sie in dieser Frage.

Zusätzlich zu all dem enthält bcrypt auch ein Salting-Schema. Aus den oben genannten Gründen können Sie ziemlich sicher sein, dass die von woliveirajr erwähnten 20-Byte-Salze auch in Zukunft lebensfähig sein werden.

Es gibt Regenbogentabellen und es gibt rohe Gewalt ... das sind zwei verschiedene Dinge.

Eine Regenbogentabelle ist ein Sonderfall einer großen vorberechneten Tabelle mit Hash Passwörter. Als solches kann eine Regenbogentabelle einen Hash "invertieren", d. H. Ein passendes Passwort wiederherstellen, nur wenn zu einem bestimmten Zeitpunkt während der Tabellenkonstruktion dieses Passwort berücksichtigt und gehasht wurde. Wenn ein Passwort mit einer Regenbogentabelle gefunden werden kann, könnte es dementsprechend mit einem einfachen Wörterbuchangriff gefunden worden sein, der nicht mehr als die Tabellenerstellung gekostet hätte. Der "Regenbogen" ändert daran nichts; Tatsächlich macht das Regenbogen-Ding das Erstellen der Tabelle teurer um einen Faktor von etwa 1,7 (das liegt daran, dass die Tabellenkonstruktion dazu neigt, mehrmals dieselben Passwörter zu berücksichtigen und zu hashen, und das ist ziemlich unvermeidlich).

Eine Konsequenz ist, dass kein Regenbogentisch die Mühe wert ist, es sei denn, er kann mindestens zweimal angewendet werden. Wir verwenden Salze genau, um dies zu verhindern. Das Salz kann als eine Variante der Hash-Funktion angesehen werden, wobei jedes neue Salz eine neue Variante impliziert. Eine vorberechnete Tabelle ist nur dann etwas wert, wenn sie mit derselben Variante (demselben Salz) vorberechnet wurde als der Hash-Wert, der angegriffen werden soll. Wenn kein Salzwert mehr als einmal verwendet wird, verschwendet der intelligente Angreifer keine Zeit damit, Kleenex-Regenbogentische zu bauen. Er wird nur einen Wörterbuchangriff ausführen.

Wir sind der Ansicht, dass der Angreifer das Salz kennt. Warum ? Weil der Server es weiß und das Angriffsmodell ist, dass der Angreifer einen Speicherauszug der Serverdatenbank erhalten könnte. Was auch immer der Server weiß, der Angreifer weiß es auch. Wenn Sie also ein Hash-Passwort angreifen, spielt die Salzlänge oder der Inhalt keine Rolle (der Angreifer muss den Salzwert in seine Berechnungen einbeziehen, aber keine Salzlänge macht seine Aufgabe einfacher oder schwieriger).

Wir haben also nur das Passwort als Verteidigungslinie. Wenn wir wissen wollen, wie viel der Angriff kostet, wird dies zu einer wirtschaftlichen Angelegenheit, und als solche entsteht eine gewisse Komplexität. Insbesondere möchten wir wissen, ob es sich um einen Angreifer handelt, der nach einem sehr wertvollen Passwort sucht (z. B. dem Passwort, das den Hauptcomputer vor der außerirdischen Kraft schützt, die die Erde auslöschen soll). oder ein Angreifer, der davon lebt, viele Passwörter zu knacken. Im letzteren Fall werden die Hardwarekosten im Hinblick auf den Stromverbrauch vernachlässigbar.

Wenn wir die Schätzungen von @ jimbob berücksichtigen, verbraucht Hardware, die 10 ^{9 sup> Hashes pro Sekunde berechnet, Strom im Wert von 200 W. und die Leistung beträgt 0,1 USD pro kWh (beachten Sie, dass die Stromkosten die Kühlung beinhalten: Jedes Watt, das für die Berechnung ausgegeben wird, wird auch zu Wärme, die irgendwie abgeführt werden muss). Dies ergibt 1,8 * 10 14 sup> Hash-Werte pro Dollar. Daraus ergibt sich Folgendes:}

• Mit $ 10K kann ein Angreifer 1,8 * 10 ^{18 sup> Hash-Werte ausprobieren, was mehr oder weniger der Zahl entspricht von möglichen Passwörtern mit 10 alphanumerischen Zeichen (Groß-, Klein- und Ziffern).}

• Mit 683,7 Milliarden Dollar (das ist das Gesamtbudget des US-Militärs im Jahr 2010 ) könnte ein Angreifer ungefähr 1,23 * 10 sup> 26 sup> Hash-Werte versuchen, was ungefähr 14,5 alphanumerischen Zeichen entspricht. Lassen Sie mich hinzufügen, dass diese Zahl der Jahresleistung von etwa hundert Kernkraftwerken entspricht, so dass der Cracking-Aufwand kaum unauffällig wäre.

Fazit: Mit 15 zufälligen alphanumerischen Zeichen widerstehen Ihre Passwörter sogar unplausiblen Feinden, selbst wenn Sie das Hashing mit einem einzigen Aufruf von SHA-1 völlig verpfuscht haben, anstatt bcrypt zu verwenden oder PBKDF2 mit einer hohen Iterationszahl, wie Sie es tun sollten . Beachten Sie, dass dies nur für zufällige Zeichen gilt, überhaupt nicht für die Art von Zeichen, die Sie möglicherweise in der Privatsphäre Ihres Gehirns finden. Das menschliche Gehirn ist zufällig überhaupt nicht gut.

Rainbow-Tabellen stellen einen Kompromiss zwischen CPU-Zeit und Speicher dar, sodass die Antwort auf diese Frage theoretisch nicht bekannt ist. Es hängt davon ab, welche Seite des Kompromisses Ihr Angreifer bevorzugt: Wenn ihm viel CPU-Zeit zur Verfügung steht, kann der Angreifer bei Auftreten eines neuen Salzwerts mit der Berechnung einer neuen Tabelle beginnen, sodass diese praktisch wertlos ist (dieses Extrem entspricht Der Angreifer kann einen Schlüssel brutal erzwingen, ohne vorberechnete Tabellen zu verwenden. Wenn sie viel Speicher haben, können sie Tabellen für jeden Wert des Salzes vorberechnen, aber es wird lange dauern, je größer desto besser.

Natürlich Dinge, die dies nicht tun theoretische Arbeit funktioniert in der Praxis oft sehr gut. Die reale Welt injiziert sich an diesem Punkt und sagt uns, dass für viele Angreifer sowohl die Speicher- als auch die CPU-Zeit begrenzt sind. Je länger das Salz, desto mehr Angreifer verfügen nicht über die Ressourcen, um einen erfolgreichen Angriff durchzuführen. Wenn Sie diese Beziehung akzeptieren, gibt es eine Ungleichung, die eine Obergrenze für Ihre Wahl der Salzgröße darstellt:

Die Gesamtressourcen auf Ihrer Seite, die für die Arbeit mit den gesalzenen Hashes erforderlich sind, müssen geringer sein als die Ressourcen, die erforderlich sind, um Ihre zu befriedigen andere Anforderungen der Anwendung.

Dies ist mein Verständnis, ich entschuldige mich, wenn dies sowieso falsch ist.

Die Verwendung eines Salzes mit Passwörtern macht Regenbogentabellen in den meisten Fällen für Angriffe fast unbrauchbar. Mit der Passwortlänge P und einer Salzlänge von S benötigen Sie Platz P * S mit naiven Brute-Force-Lookups (Hinzufügen eines zufälligen Salzes, das Sie verwenden müssen für jedes Passwort S -Tabellen erstellen). Regenbogentabellen reduzieren den Speicherplatz, der zum Speichern der Suchvorgänge für das Kennwort erforderlich ist, beseitigen jedoch nicht die Multiplikation mit S (meine Uni-Mathematik ist nicht gut genug, um Ihnen die richtige Big O-Notation zu geben; das kann eine Übung für den Leser sein: P).

Die Berechnung kann dann als die Länge Ihres akzeptierten Zeichensatzes ( c ) angesehen werden hoch der Kennwortlänge ( p ) multipliziert mit der Anzahl der möglichen Salze ( s ).

  (c ^ p) * s  

Es genügt zu sagen, dass dies sehr schnell zu einer sehr großen Zahl werden kann.

Szenario 1

Könnte eine Regierung eine System geeignet groß, um ein Passwort + Salz-Schema mit Regenbogentabellen zu brechen? Dies hängt von der Größe der Passwörter, dem verfügbaren Zeichensatz und der Salzgröße ab. Ab einer bestimmten Größe stoßen Sie an physikalische Grenzen (können Sie tatsächlich alle Permutationen auf einem Gerät mit der vorhandenen Materie / Energie codieren?). Regierungen verfügen oft über größere Ressourcen als die meisten Institutionen, aber selbst sie können diese physischen Grenzen nicht ausschöpfen.

Der einzige Weg, dies zu umgehen, besteht darin, Intuition oder Vorkenntnisse zu verwenden Reduzieren Sie den Suchraum. Bei einem häufig verwendeten System liegen die Passwörter der Benutzer unter einer bestimmten Länge. Überprüfen Sie diese nur. Sie werden wahrscheinlich auch nur eine Teilmenge des verfügbaren Zeichensatzes verwenden. Sie können diese verwenden, um zu konzentrieren, welche Hashes zum Auffüllen Ihrer Regenbogentabelle verwendet werden ( p und c ). Sie werden jedoch immer gegen die Tatsache stoßen, dass Sie mit dem zufälligen Salz ( s ) multiplizieren.

Sie haben ein zufälliges Salz, nicht wahr? !? Hier machen sich die Leute Sorgen um die Entropie von Zufallszahlen. Es ist ziemlich schwer auszunutzen, wenn nicht zufällige Daten verwendet werden, wenn echte zufällige Daten benötigt werden, aber dies ist eine der Situationen, in denen sie ins Spiel kommen. Betrachten Sie das vorherige Problem, bei dem Sie es geschafft haben, das (p ^ c) zu reduzieren, indem Sie sich ein Bild von der Art des Kennworts gemacht haben. Wenn wir etwas darüber wissen, wie zufällig die Salze sind (oder sie auf irgendeine Weise beeinflussen können), können wir beginnen, die Größe von s zu reduzieren. Wir können wissen (oder beeinflussen), dass die s zwischen einem bestimmten Satz von Werten liegen, und daher die Permutationen in den Regenbogentabellen drastisch reduzieren. Wenn ein Angreifer dies unter vernünftige physische Grenzen bringen kann, könnte eine Regierung (die so geneigt war) Regenbogentabellen verwenden, um die Passwörter zu knacken.

(Ich hoffe, dies hat auch Ihre verwandte Frage beantwortet)

Szenario 2

Auf dem aktuellen Stand von 2012 würde ich sagen, dass die Wahrscheinlichkeit, dass Sie Passwort + Salt-Hashes knacken (technische Schwachstellen in Ihrer Implementierung ignorieren), unglaublich ist, wenn Sie nicht unglaublich viel Glück haben schlank. Dies setzt voraus, dass Sie angemessene Längen für p , c und s verwenden.

Siehe http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html und http://www.codinghorror.com/blog/2007/09/rainbow-hash-cracking.html für eine interessante Lektüre zu diesem Thema (die ich mit ziemlicher Sicherheit verwendet habe und falsch missbraucht).