it-swarm-eu.dev

Warum sind Hash-Funktionen in eine Richtung? Wenn ich den Algorithmus kenne, warum kann ich die Eingabe daraus nicht berechnen?

Warum kann ein Passwort-Hash nicht rückentwickelt werden?

Ich habe mich vor langer Zeit damit befasst und viel darüber gelesen, aber ich kann keine Erklärung dafür finden, warum dies nicht möglich ist. Ein Beispiel wird es einfacher machen, meine Frage zu verstehen und die Dinge einfach zu halten. Wir werden sie auf einem Hashing-Algorithmus basieren, der kein Salz verwendet ( LanMan ).

Angenommen, mein Passwort lautet "Passwort". LanMan wird dies hashen und in der Datenbank speichern. Cracking-Programme können diese brutal erzwingen, indem sie die von Ihnen angegebenen Kennwortschätzungen hashen. Anschließend wird der generierte Hash mit dem Hash in der Datenbank verglichen. Wenn es eine Übereinstimmung gibt, wird das Passwort ermittelt.

Warum, wenn der Passwort-Cracker den Algorithmus kennt, um ein Klartext-Passwort in einen Hash umzuwandeln, kann er den Vorgang zum Berechnen des Passworts aus dem Hash nicht einfach umkehren?

Diese Frage war IT-Sicherheitsfrage der Woche.
Lesen Sie den 24. Februar 2012 Blogeintrag für weitere Details oder eigene einreichen Frage der Woche.

231
Mucker

Lassen Sie mich einen einfachen "Passwort-Hashing-Algorithmus" erfinden, der Ihnen zeigt, wie es funktioniert. Im Gegensatz zu den anderen Beispielen in diesem Thread ist dieses tatsächlich realisierbar, wenn Sie mit ein paar bizarren Passwortbeschränkungen leben können. Ihr Passwort besteht aus zwei großen Primzahlen, x und y. Zum Beispiel:

x = 48112959837082048697
y = 54673257461630679457

Sie können leicht ein Computerprogramm schreiben, um xy in O ( [~ # ~] n [~ # ~] ^ 2) Zeit zu berechnen, wobei [~ # ~] n [~ # ~] ist die Anzahl der Ziffern in x und y. (Grundsätzlich bedeutet das dass es viermal so lange dauert, wenn die Zahlen doppelt so lang sind. Es gibt schnellere Algorithmen, aber das ist irrelevant.) Speichern Sie xy in der Passwortdatenbank.

x*y = 2630492240413883318777134293253671517529

Ein Kind in der fünften Klasse, das genügend Rubbelpapier hat, könnte diese Antwort herausfinden. Aber wie kehren Sie es um? Es gibt viele Algorithmen, die entwickelt wurden, um große Zahlen zu berücksichtigen, aber selbst die besten Algorithmen sind langsam im Vergleich dazu, wie schnell Sie x mit y. multiplizieren können. Und keine von diesen Algorithmen könnte von einem Fünftklässler durchgeführt werden, es sei denn, die Zahlen waren sehr klein (z. B. x = 3, y = 5).

Das ist die Schlüsseleigenschaft : Die Berechnung ist viel einfacher vorwärts als rückwärts. Für viele Probleme müssen Sie einen völlig neuen Algorithmus erfinden, um eine Berechnung umzukehren.

Dies hat nichts mit injektiven oder bijektiven Funktionen zu tun. Wenn Sie ein Passwort knacken, spielt es oft keine Rolle, ob Sie dasselbe Passwort oder ein anderes Passwort mit demselben Hash erhalten. Die Hash-Funktion ist so konzipiert, dass es schwierig ist, sie umzukehren und überhaupt eine Antwort sogar ein anderes Passwort mit demselben Hash zu erhalten. In Crypto-Speak: Eine Hash-Funktion, die für einen Preimage-Angriff anfällig ist, ist absolut wertlos. (Der obige Passwort-Hashing-Algorithmus ist injektiv, wenn Sie eine Regel haben, die x < y.)

Was machen Kryptographie-Experten? Manchmal versuchen sie, neue Algorithmen zu finden, um eine Hash-Funktion umzukehren (Pre-Image). Sie tun genau das, was Sie sagen: Analysieren Sie den Algorithmus und versuchen Sie, ihn umzukehren. Einige Algorithmen wurden zuvor umgekehrt, andere nicht.

Übung für den Leser : Angenommen, die Passwortdatenbank enthält den folgenden Eintrag:

3521851118865011044136429217528930691441965435121409905222808922963363310303627

Wie lautet das Passwort? (Dieser ist eigentlich nicht zu schwierig für einen Computer.)

Fußnote : Aufgrund der geringen Anzahl von Passwörtern, die in der Praxis ausgewählt werden, ist es nicht nur schwierig, einen guten Passwort-Hash rückwärts zu berechnen, sondern auch zeitaufwändig, vorwärts zu berechnen und Wörterbuchangriffe zu verlangsamen. Als weitere Schutzschicht verhindert randomisiertes Salz die Verwendung vorberechneter Angriffstabellen (z. B. "Regenbogentabellen").

Fußnote 2 : Woher wissen wir, dass es schwierig ist, eine Hash-Funktion umzukehren? Leider nicht. Wir kennen einfach keine einfachen Möglichkeiten, um Hash-Funktionen umzukehren. Eine Hash-Funktion zu erstellen, die nachweislich schwer umzukehren ist, ist der heilige Gral des Hash-Funktionsdesigns und wurde noch nicht erreicht (vielleicht wird es nie passieren).

235
Dietrich Epp

Der erste Schritt zur Beantwortung besteht darin, Beispiele wie das Nizza von @Dietrich für Funktionen zu sehen, die in einer Richtung viel schwieriger auszuführen sind als in die umgekehrte und sich vielen Versuchen widersetzt haben, einen Geschwindigkeitsdurchbruch zu finden. Aber das Problem ist komplex, also werde ich versuchen, es noch weiter zu konkretisieren.

Viele Leute scheinen in die Falle zu tappen (heh) zu denken, dass Hash-Funktionen eigentlich irgendwie magisch sind - dass sie wirklich absolute "Einwegfunktionen" sind, die mathematisch nicht rückwärts ausgeführt werden können überhaupt, nur weil sie Hashes genannt werden. Dies ist keine gesunde Art, in einem Sicherheitsforum darüber nachzudenken. In der Praxis ist das oft falsch. Und es ist theoretisch immer falsch, wenn man die grundlegende mathematische Definition einer Funktion als Abbildung von einer Domäne auf ein Bild betrachtet.

Grundsätzlich können alle Hashes umgekehrt werden. Es mag chaotisch und brutal sein (wie bei Brute-Force), es kann mit der heutigen Hardware unpraktisch lange dauern und es kann sogar auf lange Sicht halten, aber mathematisch ist es einfach eine Frage der Zeit. Wie @mucker feststellte, sind alle Informationen vorhanden, um das ursprüngliche Passwort (oder zumindest ein funktionierendes Passwort) zu finden. Wenn wir das vergessen, vergessen wir die Gefahr kluger Heuristiken für die Auswahl wahrscheinlicher Passwörter, die regelmäßig in den Nachrichten erscheinen. Hashing ist ein technisches Problem und die größte Herausforderung ist die Effizienz - wie man es teuer macht, das Passwort mit dem Hash zu finden. Eines der Hauptergebnisse dieser Art des Denkens ist die Wichtigkeit, Passwort-Hashes langsam zu machen

Und die Wissenschaft und Mathematik des Hashings wird nur langsam besser. Es gibt wirklich keine Beweise dafür, dass Hashes wirklich hart sind. @ Dietrichs Antwort ist eine gute Möglichkeit zu veranschaulichen, wie ideale Hash-Funktionen könnte möglich sein. Aber schauen Sie sich nur die echten Experten an, die beschreiben, dass wir keine Beweise für einen der besten Krypto-Algorithmen haben: Was ist das mathematische Modell hinter den Sicherheitsansprüchen von symmetrischen Chiffren und Digest-Algorithmen?

Die Tatsache, dass LanMan in der Frage zitiert wurde, ist ein weiterer Beweis dafür, dass wir es vermeiden müssen, Hashes zu idealisieren. LanMan ist alles andere als eine ideale Hash-Funktion, die leicht durch eine Kombination aus ein bisschen Analyse und ein bisschen Brute Forcing besiegt werden kann. Ein weiteres beliebtes Beispiel für eine schreckliche Hash-Funktion finden Sie unter MySQL OLD_PASSWORD-Kryptoanalyse? .

Also raus aus der Falle - hineinfallen muss keine Einbahnstraße sein. Erkennen Sie, dass Hashes reversibel sind, und halten Sie diese vertrauenswürdige Sicherheitsmentalität aktiv, wenn Sie nach dem besten Weg suchen, sie umzukehren. Das ist oft der beste Weg, um diejenigen zu finden, die wirklich schwer rückgängig zu machen sind. Ich versuche nicht, die besten Praktiken wie bcrypt oder PBKDF2 oder scrypt in Betracht zu ziehen. Aber die Beweise sind klar, dass selbst gute Programmierer dieses Zeug allzu oft falsch verstehen. Seien Sie also vorsichtig mit Ihrer Verwendung und versuchen Sie nicht, Ihre eigenen zu erfinden.

17
nealmcb

Da kryptografische Hash-Funktionen so funktionieren, handelt es sich um mathematische Einwegfunktionen (von einfach bis Hash). Algorithmen werden speziell entwickelt und getestet, um dies zu vermeiden und um Kollisionen zu vermeiden (2 verschiedene Klartexte erzeugen denselben Hash).

Sie können mehr lesen auf Wikipedia , aber der Hauptpunkt des Artikels ist:

Die ideale kryptografische Hash-Funktion hat vier Haupt- oder signifikante Eigenschaften:

  • es ist einfach (aber nicht unbedingt schnell), den Hash-Wert für eine bestimmte Nachricht zu berechnen
  • es ist nicht möglich, eine Nachricht mit einem bestimmten Hash zu generieren
  • es ist nicht möglich, eine Nachricht zu ändern, ohne den Hash zu ändern
  • es ist nicht möglich, zwei verschiedene Nachrichten mit demselben Hash zu finden

Die meisten Angriffe auf Hash-Funktionen basieren darauf, Kollisionen zu finden (2 verschiedene einfache Texte stimmen mit demselben Hash überein) oder Millionen von Hashes vorab zu generieren und zu vergleichen, bis Sie die Ebene finden, die sie generiert hat.

Lange Geschichte kurz: Wenn ein Hash-Algorithmus rückentwickelbar ist oder auf diese Weise angegriffen werden kann, ist er kein guter Hash-Algorithmus.

Für Passwörter, die mit BCrypt recherchieren, enthält dieser Beitrag viele Informationen.

12
coredump

Stellen Sie sich eine Hash-Funktion vor, die ein einzelnes Bit für den Hash verwendet. Ihr Hash kann also entweder 0 oder 1 sein.

Angenommen, die Hash-Funktion addiert jedes Datenbyte und wenn die Daten gerade waren, ist der Hash-Wert 0. Wenn die Daten ungerade waren, ist der Hash 1.

Sehen Sie, warum Sie Ihre Daten nicht durch Reverse Engineering dieser Hash-Funktion wiederherstellen konnten?

Dies gilt auch für tatsächliche Hash-Algorithmen. Nur die Formeln sind deutlich besser als die gerade beschriebene Funktion.

Ihre Schwierigkeit kann sein, dass Sie Hash in Bezug auf die Verwendung für Passwörter in Betracht ziehen. Es ist nicht offensichtlich, warum Sie ein 8-stelliges Passwort nicht aus einem 128-Bit-Hash wiederherstellen können. Diese Hash-Funktion, die Sie für Kennwörter verwenden, kann jedoch auch verwendet werden, um den Hash eines ganzen Terabytes an Daten zu berechnen, und der Hash nimmt immer noch nur 128 Bit Daten auf. Offensichtlich können Sie diesen 128-Bit-Hash nicht zurückentwickeln und Ihr Terabyte an Daten wiederherstellen.

Angenommen, Sie hätten jede mögliche Permutation eines einzelnen Terabytes an Daten, würde es eine große Menge verschiedener Daten geben, die denselben Hash generieren. Wenn Sie mehr als 2 ^ 127 verschiedene Datenpermutationen haben, werden Sie wahrscheinlich auf zwei verschiedene Daten stoßen, die denselben Hash haben.

8
user1068775

Es gibt Algorithmen, die von Natur aus nicht reversibel sind. Sie wandeln einen Eingang A so in einen Ausgang B um, dass Sie A nicht aus B wiederherstellen können, selbst wenn Sie die genauen Schritte des Algorithmus kennen.

Ein sehr einfaches Beispiel: Konvertieren Sie jedes Zeichen im Kennwort in seinen Wert ASCII) und addieren Sie alle Werte. Es gibt keine Möglichkeit, das ursprüngliche Kennwort aus dem Ergebnis wiederherzustellen.

4
Massimo

Es gibt einen Aspekt des Problems, den Menschen in den vorherigen Antworten vermissen. Das ist die Eins-zu-Eins-Natur von Hash-Funktionen. Da (die meisten) Hash-Funktionen eine Ausgabe mit fester Länge sind (z. B. 256 Bit), gibt es technisch unendlich viele Zeichenfolgen, die alle den gleichen Wert haben.

Zum Beispiel, wenn Sie alle 512-Bit-Zeichenfolgen nehmen (von denen es 2 ^ 512 gibt). Es gibt nur 2 ^ 256 Ausgänge der Hash-Funktion. Somit gibt es für jede Ausgabe der Hash-Funktion ungefähr 2 ^ 256 512 Bit-Strings, die auf diesen Wert hashen. Ich sage grob, weil wir nicht wissen, ob die Hash-Funktion tatsächlich eine Zufallsfunktion ist, sie könnte leichte Verzerrungen haben.

Bei einem Digest gibt es also viele Zeichenfolgen, die denselben Wert haben. Wenn Sie also "Umkehren einer Hash-Funktion" als Ausgabe des Benutzerkennworts definieren, wie wird Ihre Umkehrfunktion mit der möglicherweise unendlichen Anzahl von Zeichenfolgen umgehen, die zu dem angegebenen Digest führen?

2
mikeazo

Sie fragen: "Warum ist es wichtig, dass Hash-Funktionen in eine Richtung funktionieren?" Es ist eine Sicherheitseigenschaft.

Es gibt heute zwei Arten von "Hash" (oder "Message Digest", wie sie genannt werden), die allgemein verwendet werden. Eine davon ist eine einfache Nachrichtenübersicht, mit der Sie möglicherweise als Prüfsummenalgorithmus wie CRC32 vertraut sind. Der Algorithmus ist so konzipiert, dass eine einzelne Bitänderung in der Eingabe einen anderen Digest-Wert ergibt. Der Hauptzweck ist es, sicherzustellen, dass eine Nachricht nicht versehentlich beschädigt wird. CRC32-Prüfsummen sind in jedem TCP/IP-Paket vorhanden, und eine Fehlanpassung führt zu einer erneuten Übertragung, um den Fehler zu korrigieren.

Nachrichtenübersichten werden in der Kryptografie häufig als Teil des "Signierens" einer Nachricht verwendet. Die Nachricht wird vom Absender mit seinem privaten Schlüssel verschlüsselt, und jeder kann den öffentlichen Schlüssel verwenden, um zu überprüfen, ob sie nur vom Absender verschlüsselt wurde. Die RSA-Kryptografie mit öffentlichem Schlüssel kann jedoch nur Nachrichten verschlüsseln, die kleiner als die Schlüsselgröße (256 Byte) sind und viel kürzer als die meisten nützlichen Nachrichten sind. Message Digest-Algorithmen erzeugen Werte, die kleiner als RSA-Schlüssel sind. Durch Verschlüsseln des Digests anstelle der Nachricht können RSA-Signaturen für Nachrichten beliebiger Größe verwendet werden.

Ein gewöhnlicher Message Digest ist jedoch gegen einen Angreifer nicht sicher. Stellen Sie sich eine sehr einfache Prüfsumme vor, die nur die Werte der Zeichen summiert. Wenn Sie eine solche Prüfsumme unterschreiben würden, könnte ich jede andere Nachricht austauschen, die dieselbe Prüfsumme ergibt, und die Unterschriften würden übereinstimmen, was das Opfer täuscht.

Eine weitere häufige Verwendung für Nachrichtenübersichten ist der Kennwortschutz während der Speicherung. Wenn Sie die Kennwörter verschlüsseln, bevor Sie sie im System speichern, kann ein Systemadministrator, der den Schlüssel kennt, sie alle entschlüsseln. (Möglicherweise haben Sie dieses Problem kürzlich bemerkt, als einige Websites gehackt wurden.)

Um diese Probleme zu vermeiden, wird eine andere Art von Hash benötigt, die "kryptografisch sicher" ist. Ein sicherer Hash-Algorithmus hat zwei zusätzliche Eigenschaften: Kollisionsbeständigkeit und Nichtreversibilität.

Kollisionsresistenz bedeutet, dass ich keine Nachricht finden sollte, die den gleichen Digest erzeugt. Auf diese Weise kann ich meine böse Botschaft nicht gegen Ihre gute Botschaft austauschen.

Nicht umkehrbare Eigenschaft bedeutet, dass ich einen Digest nicht wieder in Klartext umwandeln kann, sodass ich die ursprüngliche Nachricht wie das Kennwort des Benutzers nicht entschlüsseln kann.

Das Erstellen eines Digests ist insofern ein sehr ähnliches Problem wie das Verschlüsseln, als Sie die Daten so verschlüsseln müssen, dass keine Informationen über die Originaldaten verloren gehen. Es ist noch schwieriger, weil dieselbe Mathematik keine Hinweise darauf geben muss, wie eine Kollision erfolgreich erstellt werden kann.

1
John Deters

Ich denke, es gibt viele Gründe, aber einer ist offensichtlich: Ein Digest, der von einer Hash-Funktion erzeugt wird, kann niemals unendliche Informationen enthalten, da der Digest endliche Bits enthält. Die Hash-Funktion kann jedoch verwendet werden, um Eingaben von unendlichen Informationen zu hashen. Die Eingabe kann eigentlich alles sein.

Die Schwierigkeit, eine Kollision herauszufinden, ist nicht die Antwort. Die wirkliche Schwierigkeit besteht darin, zu beweisen, dass Ihre Originaldaten tatsächlich die einzig mögliche Eingabe sind, die einer bestimmten Übersicht entspricht. Ich denke, Sie können niemals eine Eingabe berechnen und behaupten, dass dies die einzige Antwort auf die Zusammenfassung ist.

0

Andere haben erklärt, warum gute kryptografische Hash-Funktionen schwer umzukehren sind - aber laut dieser Wikipedia-Artikel ist LanMan schlecht gestaltet und kann relativ leicht rückgängig gemacht werden:

Obwohl es auf DES basiert, einer gut untersuchten Blockverschlüsselung, ist der LM-Hash keine echte Einwegfunktion, da das Passwort aufgrund mehrerer Schwachstellen in seiner Implementierung aus dem Hash ermittelt werden kann ... Durch das Bereitstellen eines Brute-Force-Angriffs Auf jeder Hälfte einzeln können moderne Desktop-Computer in wenigen Stunden alphanumerische LM-Hashes knacken ... 2003 wurde Ophcrack, eine Implementierung der Rainbow-Tabellentechnik, veröffentlicht. Es zielt speziell auf die Schwachstellen der LM-Verschlüsselung ab und enthält vorberechnete Daten, die ausreichen, um praktisch alle alphanumerischen LM-Hashes in wenigen Sekunden zu knacken.

0
James