Warum machen Salze Wörterbuchangriffe "unmöglich"?
Update: Bitte beachten Sie, ich bin nicht zu Fragen, was ein Salz ist, was eine rainbow-Tabelle ist, was ein Wörterbuch-Angriff ist, oder was der Zweck der ein Salz ist. Ich bin der Abfrage: Wenn Ihnen der Benutzer salt und hash, ist es nicht ganz einfach zu berechnen sein Passwort?
Verstehe ich den Prozess, und implementieren Sie mich in einige meiner Projekte.
s = random salt
storedPassword = sha1(password + s)
In der Datenbank speichern:
username | hashed_password | salt
Jeder Implementierung von Salzen, die ich gesehen habe, fügt das Salz entweder am Ende des Passwortes oder Beginn:
hashed_Password = sha1(s + password )
hashed_Password = sha1(password + s)
Darum, ein Wörterbuch-Angriff von einem hacker, der etwas taugt (ha ha) würde dazu führen, dass jedes keyword anhand der gespeicherten Salze, die in der gemeinsamen Kombinationen, die oben aufgeführt sind.
Sicherlich die Umsetzung, die oben beschrieben fügt einfach ein weiterer Schritt für die hacker, ohne tatsächlich die Lösung des zugrunde liegenden Problems? Welche alternativen gibt es zu Schritt, um dieses Problem, oder bin ich Missverständnis das problem?
Das einzige was ich mir vorstellen kann zu tun haben, ist ein Geheimnis-blending-Algorithmus, der die Schnürsenkel, das Salz und das Passwort zusammen in einem zufälligen Muster an, oder fügt weitere benutzerdefinierte Felder, um die hashing-Prozess, d.h. die hacker haben Zugang zu den Datenbank-UND code-zu-Spitzen Sie für ein Wörterbuch-Angriff, um sich als fruchtbar erweisen. (Update, wie bereits in den Kommentaren ist es am besten annehmen, dass die hacker Zugriff auf alle Ihre Informationen, so dass dies wahrscheinlich nicht am besten).
Lassen Sie mich ein Beispiel geben, wie ich schlage vor, ein hacker würde hack eine Benutzer-Datenbank mit einer Liste von Passwörtern und hashes:
Daten aus unserer Datenbank gehackt:
RawPassword (not stored) | Hashed | Salt
--------------------------------------------------------
letmein WEFLS... WEFOJFOFO...
Gemeinsame Passwort Wörterbuch:
Common Password
--------------
letmein
12345
...
Für jeden Benutzer Aufnahme, loop-die gemeinsame Passwörter und hash Sie:
for each user in hacked_DB
salt = users_salt
hashed_pw = users_hashed_password
for each common_password
testhash = sha1(common_password + salt)
if testhash = hashed_pw then
//Match! Users password = common_password
//Lets visit the webpage and login now.
end if
next
next
Ich hoffe das verdeutlicht meinen Standpunkt viel besser.
Gegeben 10,000 häufigsten Passwörter, und 10.000 Benutzer-Datensätze, die wir brauchen würden, zu berechnen 100,000,000 hashes zu entdecken, wie viele user Passwörter wie möglich. Es könnte ein paar Stunden dauern, aber es ist nicht wirklich ein Problem.
Update auf Risse Theorie
Nehmen wir an wir sind eine korrupte webhost, hat Zugriff auf eine Datenbank von SHA1-hashes und Salze, die zusammen mit Ihrem Algorithmus zu verschmelzen. Die Datenbank hat 10.000 Benutzer Datensätze.
Diese Website Ansprüche berechnen zu können 2,300,000,000 SHA1-hashes pro Sekunde, die mithilfe der GPU. (In der realen-Welt-situation wird wahrscheinlich langsamer sein, aber für jetzt verwenden wir, dass die zitierte Abbildung).
(((95^4)/2300000000)/2)*10000 = 177
Sekunden
Gegeben, eine vollständige Palette von 95 druckbaren ASCII-Zeichen mit einer maximalen Länge von 4 Zeichen, geteilt durch die rate der Berechnung (variable) geteilt durch 2 (vorausgesetzt, die Durchschnittliche Zeit, zu entdecken, Passwort wird im Durchschnitt benötigen 50% der Permutationen), für 10.000 Nutzer, die es dauern würde, 177 Sekunden, um alle Benutzer-Passwörter, wo die Länge ist <= 4.
Let ' s einstellen, ein bisschen Realismus.
(((36^7)/1000000000)/2)*10000 = 2 Tage
Vorausgesetzt, nicht die groß-und Kleinschreibung, mit einem Passwort der Länge <= 7, nur alphanumerische Zeichen, es dauerte 4 Tage zu lösen, für 10.000 Benutzer Datensätze, und ich habe Sie halbiert die Geschwindigkeit des Algorithmus zu reflektieren, overhead-und nicht idealen Umständen.
Ist es wichtig zu erkennen, dass dies eine lineare brute-force-Angriff, alle Berechnungen sind unabhängig voneinander, daher ist es eine perfekte Aufgabe für mehrere Systeme zu lösen. (ALSO einfach bis zu 2 Computer unter Angriff von verschiedenen enden, die würden die Hälfte der exectution Zeit).
In dem Fall rekursiv Hash ein Passwort 1.000 mal um diese Aufgabe rechnerisch teuer:
(((36^7) /1 000 000 000) /2) * 1000
Sekunden = 10.8839117 Stunden
Dies entspricht einer maximalen Länge von 7 alpha-numerische Zeichen, auf weniger als die Hälfte die Geschwindigkeit der Ausführung von zitierte Bild für ein Benutzer.
Rekursiv hashing-1000 mal blockiert effektiv eine Decke Angriff, sondern gezielte Angriffe auf Anwender-Daten sind immer noch anfällig.
InformationsquelleAutor der Frage Tom Gullen | 2010-08-25
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ja, Sie brauchen nur 3 Tage für den sha1-Hash(salt | password). Das ist der Grund, warum gute Passwort-Speicher-algorithmen verwenden die 1000-iteration hashing: Sie benötigen 8 Jahren.
InformationsquelleAutor der Antwort blaze
Es nicht stoppen Wörterbuch-Attacken.
Was es tut, ist halt jemand, der es schafft, erhalten Sie eine Kopie Ihrer Passwort-Datei aus der Verwendung einer rainbow-tableum herauszufinden, was sind die Passwörter aus den hashes.
Schließlich kann es sein, brute-gezwungen, obwohl. Die Antwort auf das Teil ist, um zu erzwingen Ihre Benutzer keine Wörter aus dem Lexikon als Passwort (Mindestanforderungen mindestens eine Zahl oder Sonderzeichen zum Beispiel).
Update:
Sollte ich dies oben erwähnt, aber einige (die meisten?) Passwort-Systeme verwenden einen anderen salt für jedes Passwort, wahrscheinlich gespeichert, mit dem Kennwort selbst. Dies macht eine einzelne rainbow-Tabelle nutzlos. Dies ist, wie die UNIX - Krypta Bibliothek arbeitet, und die modernen UNIX-artigen Betriebssysteme erweitert diese Bibliothek mit neuen hash-algorithmen.
Ich weiß, für eine Tatsache, dass die Unterstützung für SHA-256 und SHA-512 wurden Hinzugefügt, die in neueren Versionen von GNU crypt.
InformationsquelleAutor der Antwort Powerlord
Um genauer zu sein, ein Wörterbuch-AngriffD. H. einen Angriff, bei dem alle Wörter in eine erschöpfende Liste ist, sind versucht, wird nicht "unmöglich", aber es wird unpraktisch: jedes bisschen Salz verdoppelt die Menge an Speicher und erforderliche Berechnung.
Diese unterscheidet sich von pre-computed-dictionary-Angriffe wie Angriffe mit rainbow-Tabellen, in denen ist es egal, ob das Salz geheim ist oder nicht.
Beispiel: Mit einem 64-bit-salt - (d.h. 8 bytes) die Sie benötigen, um zu überprüfen, 264 zusätzliche Passwort-Kombinationen, die in Ihrem Wörterbuch-Angriff. Mit einem Wörterbuch mit 200.000 Wörter, die du machen musst
tests im schlimmsten Fall - anstelle von 200.000 tests ohne Salz.
Ein weiterer Vorteil der Verwendung von Salz ist, dass ein Angreifer nicht vorherberechnet werden die Passwort-hashes aus seinem Wörterbuch. Es würde einfach zu viel Zeit und/oder Raum.
Update
Update setzt Voraus, dass ein Angreifer schon weiß, das Salz (oder wurde gestohlen). Dies ist natürlich eine ganz andere situation. Noch immer ist es nicht möglich, die Angreifer verwenden eine vorberechnete rainbow-table. Was zählt hier eine Menge ist die Geschwindigkeit, mit der die Hash-Funktion. Um einen Angriff unmöglich wird, die Hash-Funktion muss langsam sein. MD5 oder SHA sind nicht gute Kandidaten sind hier, weil Sie sind entworfen, um die schnelle, bessere Kandidaten für hashing-algorithmen Blowfish oder einige Variationen davon.
Update 2
Einen guten read auf die Frage der Sicherung Ihrer Passwort-hashes im Allgemeinen (und das geht weit über die ursprüngliche Frage, aber trotzdem interessant):
Folge des Artikels: Verwenden gesalzene hashes erstellt mit bcrypt (basiert auf Blowfish) oder Eksblowfish , können Sie über ein konfigurierbares setup-Zeit zu machen hashing langsam.
InformationsquelleAutor der Antwort Dirk Vollmar
Einem Wörterbuch eine Struktur, wo die Werte sind indiziert von Tasten. Im Falle einer pre-computed-Wörterbuch-Angriff, jeder Schlüssel ist ein hash, und der entsprechende Wert ist ein Kennwort, dass die Ergebnisse in den hash. Mit einem pre-computed-Wörterbuch in der hand, kann ein Angreifer "sofort" lookup ein Passwort erzeugen werden die notwendigen hash einloggen.
Mit Salz, den erforderlichen Speicherplatz zum speichern der Wörterbuch wächst rasend schnell... so schnell, dass der Versuch, pre-compute-ein Passwort-Wörterbuch wird bald sinnlos.
Die besten Salze werden nach dem Zufallsprinzip ausgewählt aus einer cryptographic random number generator. Acht bytes ist eine praktische Größe, und mehr als 16 Byte dient keinem Zweck.
Salz ist weit mehr als nur "machen Sie ein Angreifer die Aufgabe mehr reizt." Es entfällt eine ganze Klasse von Angriff—die Verwendung von vordefinierten Wörterbüchern.
Einem anderen element ist notwendig, um vollständig sichere Passwörter, und das ist "key-Stärkung." Einer Runde von SHA-1 ist nicht gut genug: ein Sicheres Passwort-hashing-Algorithmus sehr langsam rechnerisch.
Viele Menschen nutzen PBKDF2, ein Schlüssel Ableitung Funktion, die Rückkopplung der Ergebnisse an die hash-Funktion Tausende mal. Die "bcrypt" - Algorithmus ist ähnlich, mit einem iterativen schlüsselableitung, die langsam ist.
Wenn der hashing-operation ist sehr langsam, eine vorausberechnete Tabelle wird mehr und mehr wünschenswert für einen Angreifer. Aber richtige Salz-Niederlagen Ansatz.
Kommentare
Unten sind die Kommentare, die ich auf die Frage.
Ohne Salz, ein Angreifer würde nicht verwenden Sie die Methode, nachgewiesen in "Update 2". Er würde einfach tun, eine Suche in einer vorausberechneten Tabelle und das Kennwort erhalten Sie in O(1) oder O(log n) - mal (n ist dabei die Anzahl der Kandidaten Passwörter). Salz ist das, was verhindert das und zwingt ihn zur Verwendung des O(n) dargestellte Ansatz in "Update 2".
Einmal reduziert, um eine O(n) - Angriff, wir haben zu überlegen, wie lange jeder Versuch dauert. Schlüssel-Stärkung verursachen können jedem Versuch, in die Schleife zu nehmen, eine Sekunde, was bedeutet, dass die benötigte Zeit, um zu testen, 10k Passwörter auf 10k Nutzer erstrecken sich von 3 Tagen bis 3 Jahren... und mit nur 10k Passwörter, die Sie wahrscheinlich zu knacken null Passwörter in dieser Zeit.
Ist zu beachten, dass ein Angreifer verwenden die schnellsten Werkzeuge, die er kann, nicht PHP, also Tausende von Iterationen, anstatt 100, wäre ein guter parameter für key-Stärkung. Es sollte ein großer Bruchteil einer Sekunde zu berechnen den hash für ein Passwort.
Schlüssel-Verstärkung ist Teil der standard-Schlüssel-Ableitung algorithmen PBKDF1 und PBKDF2, von PKCS #5, die großen Passwort Verschleierung algorithmen ("derived key" ist der "hash").
Viele Benutzer auf StackOverflow finden dieser Artikelweil es war eine Antwort auf Jeff Atwood Beitrag über die Gefahren von rainbow-Tabellen. Es ist nicht mein Lieblings-Artikel, sondern behandelt es, diese Konzepte im detail.
Natürlich übernimmt der Angreifer hat alles: Salz -, hash -, Benutzer-name. Angenommen der Angreifer ist eine korrupte hosting-Unternehmen, Mitarbeiter, warfen die user-Tabelle auf Ihre myprettypony.com fansite. Er versucht wieder diese Passwörter, weil er sich umdrehen und sehen, ob Ihre pony-fans das gleiche Kennwort auf Ihre citibank.com Konten.
Mit einem gut gestalteten Passwort-Schema, es werden unmöglich für diesen Typen ist das wiederherstellen von Passwörtern.
InformationsquelleAutor der Antwort erickson
Den Punkt von Salzen zu verhindern, dass die Abschreibungen auf den Angreifer bemühen.
Ohne Salz, eine einzelne Tabelle vorberechneter hash-Passwort-Einträge (z.B. MD5 aller 5 alphanumerische Zeichenfolgen, die leicht online zu finden) kann verwendet werden, auf jeden Benutzer in jeder Datenbank der Welt.
Mit einer ortsspezifischen Salz, den Angreifer zu berechnen, die Tabelle selbst und können dann auf alle Benutzer der Website.
Mit einer pro-Benutzer-Salz, der Angreifer aufwenden, um sich dieser Aufwand für jeden Benutzer separat.
Natürlich nicht viel tun, um zu schützen, wirklich schwache Passwörter direkt aus einem Wörterbuch, aber es schützt hinreichend starke Passwörter gegen diese Abschreibungen.
InformationsquelleAutor der Antwort Michael Borgwardt
Auch - eine weitere imporatant point über einen USER-spezifischen Salz verhindert die Erkennung der zwei Benutzer mit dem GLEICHEN Passwort - Ihre hashes übereinstimmen würde. Das ist, warum viele Male, wird der hash hash(salt + username + Passwort)
Wenn Sie versuchen, und halten Sie die hash-Geheimnis der Angreifer kann auch nicht überprüfen Sie die hashes.
Edit - gerade gemerkt-der wichtigste Punkt wurde in einem Kommentar oben.
InformationsquelleAutor der Antwort Dominik Weber
Salze umgesetzt werden, um zu verhindern, dass rainbow-table-Angriffe. Eine rainbow-Tabelle ist eine Liste von pre-hashes berechnet, wodurch die übersetzung von einem hash in den Satz viel einfacher. Sie müssen verstehen, dass das Salzen ist nicht wirksam, wie eine moderne Prävention zu knacken ein Passwort, es sei denn, wir haben eine moderne hashing algo.
So können sagen, wir arbeiten mit SHA1, unter Ausnutzung der jüngsten exploits entdeckt, die mit diesem algo, und können sagen, wir haben einen computer mit 1.000.000 hashes/Sekunde, es würde 5,3 Millionen Millionen Millionen Jahre eine Kollision zu findenalso das ist ja php arbeiten kann 300 eine zweite, big woop, spielt eigentlich keine Rolle. Der Grund, warum wir Salz ist, denn wenn jemand hat die Mühe zu generieren, die alle ein gemeinsames Wörterbuch Phrasen, (2^160 Leute, willkommen zu 2007 era-exploits).
So, hier ist eine aktuelle Datenbasis, mit 2 Benutzern, die ich zum testen verwenden und admin-Zwecke.
In der Tat, das Salzen Schema ist dein sha1(Registrierung Zeit + user-name). Gehen Sie voran, sagen Sie mir, mein Passwort, dies sind die echten Passwörter in der Produktion. Sie kann sogar dort sitzen und die Erarbeitung einer Wort-Liste in php. Go wild.
Ich bin nicht verrückt, ich weiß nur, dass diese sicher ist. Für Spaß Willen, test-Passwort ist
test.sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023Müssten Sie generieren eine komplette rainbow-table-perpended mit
27662aee8eee1cb5ab4917b09bdba31d091ab732für nur diesen Benutzer. Das heißt, ich kann tatsächlich zulassen, dass meine Passwörter nicht beeinträchtigt werden durch eine einzelne rainbow-Tabelle, die hacker zu generieren muss eine ganze rainbow-Tabelle für 27662aee8eee1cb5ab4917b09bdba31d091ab732 für test -, und wieder f3f7735311217529f2e020468004a2aa5b3dee7f für briang. Denken Sie zurück an die 5,3 Millionen Millionen Millionen Jahre für alle hashes. Denken Sie an die Größe von speichern nur die 2^80 hashes (das ist weit über 20 yottabytes), es wird nicht passieren.Nicht zu verwechseln mit Salzen als Mittel, um einen hash-etwas, das Sie nicht immer entschlüsseln, es ist ein Mittel der Prävention, rainbow-Tabelle übersetzt alle Ihre Benutzer-Passwörter. Es ist imposable auf dieser Ebene der Technologie.
InformationsquelleAutor der Antwort Incognito
Die Idee hinter Wörterbuch-Angriff ist, dass man einen hash und finden Sie das Kennwort, aus denen dieser hash berechnet wurde, und ohne hash-Berechnung. Jetzt tun Sie das gleiche mit gesalzenen Passwort - können Sie nicht.
Nicht mit einem Salz macht das Passwort-Suche so einfach wie die Suche in der Datenbank. Hinzufügen einer Salz Angreifer führen Sie die hash-Berechnung aller möglichen Passwörter (auch für Wörterbuch befestigen, dies erhöht deutlich die Zeit der Attacke).
InformationsquelleAutor der Antwort Eugene Mayevski 'Allied Bits
In einfachen Worten: ohne Salzen, jeder Kandidat Passwort muss nur zerlegt werden, einmal zu prüfen, es gegen jeden Benutzer, überall in der bekannten "Universum" (Sammlung von kompromittierten Datenbanken), deren Passwort gehasht ist über den gleichen Algorithmus. Mit Salzen, wenn die Anzahl der möglichen salt-Werte wesentlich höher als die Zahl der Nutzer in das "bekannte Universum", jeder Kandidat Passwort muss zerlegt werden für jeden Benutzer separat, gegen die Sie getestet werden.
InformationsquelleAutor der Antwort supercat
Setzen Sie einfach das Salzen nicht verhindern, dass ein hash aus einen Angriff (bruteforce-oder Wörterbuch -), es macht es nur schwieriger; die Angreifer müssen entweder finden die salting-Algorithmus (die, wenn richtig implementiert, nutzt mehr Iterationen) oder die bruteforce algo, es sei denn, sehr einfach, ist fast unmöglich. Salzen auch fast vollständig verwirft die Möglichkeit, rainbow-table-lookups...
InformationsquelleAutor der Antwort cyber-guard
Salz macht Rainbow-table Angriffe sehr viel schwieriger, da macht es einen Passwort-hash viel schwerer zu knacken. Stellen Sie sich vor Sie haben eine schreckliche Passwort nur die Nummer 1. Eine rainbow-table-Angriff brechen würde dies sofort.
Nun Stell dir vor, jedes Passwort in der db ist gesalzen, mit einem langen, zufälligen Wert viele zufällige Zeichen. Jetzt ist Ihre lausige Passwort von "1" gespeichert wird in der db als hash 1 plus ein paar zufällige Zeichen (salt), also in diesem Beispiel die rainbow-table haben muss, um die hash für so etwas: 1.
Also vorausgesetzt, Ihr Salz ist etwas sicherer und zufällig, und sagen ()%ISLDGHASKLU(%#%#, den hacker ' s rainbow-Tabelle muss auf einen Eintrag für 1*()%ISLDGHASKLU(*%#%#. Jetzt mit einem rainbow-table auf, auch dieses einfache Passwort ist nicht mehr praktikabel.
InformationsquelleAutor der Antwort Cory House