Wie kommt es, dass MD5-Hashwerte nicht umkehrbar sind?

Ein Konzept, über das ich mich immer gewundert habe, ist die Verwendung kryptografischer Hash-Funktionen und -Werte. Ich verstehe, dass diese Funktionen einen Hashwert erzeugen können, der einzigartig und praktisch unmöglich umzukehren ist, aber ich habe mich immer gefragt:

Wenn auf meinem Server, in PHP produziere ich:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Wenn Sie dieselbe Zeichenfolge über eine MD5-Funktion ausführen, erhalten Sie bei Ihrer PHP-Installation dasselbe Ergebnis. Ein Prozess wird verwendet, um einen Wert aus einem Startwert zu erzeugen.

Bedeutet dies nicht, dass es eine Möglichkeit gibt, das Geschehen zu dekonstruieren und den Hash-Wert umzukehren?

Was ist mit diesen Funktionen, das es unmöglich macht, die resultierenden Zeichenfolgen zurückzuverfolgen?

Das Eingabematerial kann eine unendliche Länge haben, wobei die Ausgabe immer 128 Bit lang ist. Dies bedeutet, dass eine unendliche Anzahl von Eingabezeichenfolgen dieselbe Ausgabe generiert.

Wenn Sie eine Zufallszahl auswählen und durch 2 teilen, aber nur den Rest aufschreiben, erhalten Sie entweder eine 0 oder eine 1 - gerade oder ungerade. Ist es möglich, diese 0 oder 1 zu nehmen und die ursprüngliche Nummer zu erhalten?

Wenn Hash-Funktionen wie MD5 reversibel wären, wäre dies ein Wendepunkt in der Geschichte der Datenkomprimierungsalgorithmen gewesen! Es ist leicht zu erkennen, dass, wenn MD5 reversibel wäre, beliebige Datenblöcke beliebiger Größe durch bloße 128 Bit ohne Informationsverlust dargestellt werden könnten. Auf diese Weise hätten Sie die ursprüngliche Nachricht unabhängig von der Größe der ursprünglichen Nachricht aus einer 128-Bit-Zahl rekonstruieren können.

Im Gegensatz zu dem, was die meist upvoted Antworten hier betonen, das nicht-injectivity (dh , dass es mehrere Saiten auf den gleichen Wert Hashing) durch die Differenz zwischen großer (potentiell unendlichen) Eingangsgröße und fester Ausgangsgröße einer verschlüsselten Hash - Funktion verursacht ist nicht Der wichtige Punkt - eigentlich bevorzugen wir Hash-Funktionen, bei denen diese Kollisionen so selten wie möglich auftreten.

Betrachten Sie diese Funktion (in PHP-Notation als Frage):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Dies fügt einige Leerzeichen an, wenn die Zeichenfolge zu kurz ist, nimmt dann die ersten 16 Bytes der Zeichenfolge und codiert sie dann als hexadezimal. Es hat die gleiche Ausgabegröße wie ein MD5-Hash (32 hexadezimale Zeichen oder 16 Byte, wenn der bin2hex-Teil weggelassen wird).

print simple_hash("stackoverflow.com");

Dies wird Folgendes ausgeben:

737461636b6f766572666c6f772e636f6d

Diese Funktion hat auch die gleiche Nicht-Injektivitätseigenschaft wie in Codys Antwort für MD5 hervorgehoben: Wir können Zeichenfolgen beliebiger Größe übergeben (solange sie in unseren Computer passen) und es werden nur 32 hexadezimale Ziffern ausgegeben. Natürlich kann es nicht injektiv sein.

In diesem Fall ist es jedoch trivial, eine Zeichenfolge zu finden, die demselben Hash zugeordnet ist (wenden hex2binSie sie einfach auf Ihren Hash an, und Sie haben sie). Wenn Ihre ursprüngliche Zeichenfolge die Länge 16 hatte (als unser Beispiel), erhalten Sie sogar diese ursprüngliche Zeichenfolge. Für MD5 sollte nichts dergleichen möglich sein, selbst wenn Sie wissen, dass die Länge der Eingabe ziemlich kurz war (außer indem Sie alle möglichen Eingaben ausprobieren, bis wir eine passende finden, z. B. einen Brute-Force-Angriff).

Die wichtigen Annahmen für eine kryptografische Hash-Funktion sind:

• Es ist schwer, eine Zeichenfolge zu finden, die einen bestimmten Hash erzeugt (Vorbildwiderstand).
• Es ist schwierig, eine andere Zeichenfolge zu finden, die denselben Hash wie eine bestimmte Zeichenfolge erzeugt (zweiter Vorbildwiderstand).
• Es ist schwierig, ein Saitenpaar mit demselben Hash zu finden (Kollisionsbeständigkeit).

Offensichtlich meine simple_hash erfüllt Funktion keine dieser Bedingungen. (Wenn wir den Eingaberaum auf "16-Byte-Strings" beschränken, wird meine Funktion injektiv und ist somit sogar nachweisbar resistent gegen Zweitvorbilder und kollisionssicher.)

Es gibt jetzt Kollisionsangriffe gegen MD5 (z. B. ist es möglich, ein Paar von Zeichenfolgen zu erzeugen, selbst mit einem bestimmten Präfix, die denselben Hash haben, mit ziemlich viel Arbeit, aber nicht unmöglich viel Arbeit), daher sollten Sie diese nicht verwenden MD5 für alles Kritische. Es gibt noch keinen Preimage-Angriff, aber die Angriffe werden besser.

Um die eigentliche Frage zu beantworten:

Was ist mit diesen Funktionen, das es unmöglich macht, die resultierenden Zeichenfolgen zurückzuverfolgen?

MD5 (und andere Hash-Funktionen, die auf der Merkle-Damgard-Konstruktion aufbauen) wenden effektiv einen Verschlüsselungsalgorithmus mit der Nachricht als Schlüssel und einem festen Wert als "Klartext" an, wobei der resultierende Chiffretext als Hash verwendet wird. (Vorher wird die Eingabe aufgefüllt und in Blöcke aufgeteilt. Jeder dieser Blöcke wird verwendet, um die Ausgabe des vorherigen Blocks zu verschlüsseln. XORed mit seiner Eingabe, um umgekehrte Berechnungen zu verhindern.)

Moderne Verschlüsselungsalgorithmen (einschließlich der in Hash-Funktionen verwendeten) sind so konzipiert, dass es schwierig ist, den Schlüssel wiederherzustellen, selbst wenn sowohl Klartext als auch Chiffretext vorliegen (oder selbst wenn der Gegner einen von ihnen auswählt). Sie tun dies im Allgemeinen, indem sie viele Bit-Shuffling-Operationen so ausführen, dass jedes Ausgangsbit durch jedes Schlüsselbit (mehrmals) und auch jedes Eingangsbit bestimmt wird. Auf diese Weise können Sie nur dann leicht nachvollziehen, was im Inneren passiert, wenn Sie den vollständigen Schlüssel und entweder die Eingabe oder die Ausgabe kennen.

Für MD5-ähnliche Hash-Funktionen und einen Preimage-Angriff (zur Vereinfachung mit einem Single-Block-Hash-String) haben Sie nur die Eingabe und Ausgabe Ihrer Verschlüsselungsfunktion, nicht jedoch den Schlüssel (dies ist das, wonach Sie suchen).

Die Antwort von Cody Brocious ist die richtige. Genau genommen können Sie eine Hash-Funktion nicht "invertieren", da viele Strings demselben Hash zugeordnet sind. Beachten Sie jedoch, dass entweder das Finden einer Zeichenfolge, die einem bestimmten Hash zugeordnet wird, oder das Finden von zwei Zeichenfolgen, die demselben Hash zugeordnet werden (dh eine Kollision ), ein wichtiger Durchbruch für einen Kryptoanalytiker wäre. Die große Schwierigkeit dieser beiden Probleme ist der Grund, warum gute Hash-Funktionen in der Kryptographie nützlich sind.

MD5 erstellt keinen eindeutigen Hashwert. Das Ziel von MD5 ist es, schnell einen Wert zu erzeugen, der sich aufgrund einer geringfügigen Änderung der Quelle erheblich ändert.

Z.B,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Offensichtlich ist das keine tatsächliche MD5-Verschlüsselung)

Die meisten Hashes (wenn nicht alle) sind ebenfalls nicht eindeutig. Vielmehr sind sie einzigartig genug , sodass eine Kollision höchst unwahrscheinlich, aber dennoch möglich ist.

Eine gute Möglichkeit, sich einen Hash-Algorithmus vorzustellen, besteht darin, die Größe eines Bildes in Photoshop zu ändern. Angenommen, Sie haben ein Bild mit einer Größe von 5000 x 5000 Pixel und ändern dann die Größe auf nur 32 x 32 Pixel. Was Sie haben, ist immer noch eine Darstellung des Originalbildes, aber es ist viel viel kleiner und hat bestimmte Teile der Bilddaten effektiv "weggeworfen", damit es in die kleinere Größe passt. Wenn Sie also die Größe dieses 32x32-Bilds auf 5000x5000 zurücksetzen, erhalten Sie nur ein verschwommenes Durcheinander. Da ein 32x32-Bild jedoch nicht so groß ist, wäre es theoretisch denkbar, dass ein anderes Bild verkleinert wird, um genau die gleichen Pixel zu erzeugen!

Das ist nur eine Analogie, aber es hilft zu verstehen, was ein Hash tut.

Eine Hash-Kollision ist viel wahrscheinlicher als Sie denken. Schauen Sie sich das Geburtstagsparadox an, um besser zu verstehen, warum das so ist.

Da die Anzahl der möglichen Eingabedateien größer ist als die Anzahl der 128-Bit-Ausgänge, ist es unmöglich, jedem möglichen einen MD5-Hash eindeutig zuzuweisen.

Kryptografische Hash-Funktionen werden zum Überprüfen der Datenintegrität oder digitaler Signaturen verwendet (der Hash wird aus Effizienzgründen signiert). Das Ändern des Originaldokuments sollte daher bedeuten, dass der Originaldash nicht mit dem geänderten Dokument übereinstimmt.

Diese Kriterien werden manchmal verwendet:

1. Vorbildwiderstand: Für eine bestimmte Hash-Funktion und einen bestimmten Hash sollte es schwierig sein, eine Eingabe zu finden, die den angegebenen Hash für diese Funktion enthält.
2. Zweiter Vorbildwiderstand: Für eine bestimmte Hash-Funktion und Eingabe sollte es schwierig sein, eine zweite, andere Eingabe mit demselben Hash zu finden.
3. Kollisionswiderstand: Für eine gegebene Funktion sollte es schwierig sein, zwei verschiedene Eingaben mit demselben Hash zu finden.

Diese Kriterien werden ausgewählt, um es schwierig zu machen, ein Dokument zu finden, das einem bestimmten Hash entspricht. Andernfalls wäre es möglich, Dokumente zu fälschen, indem das Original durch ein Dokument ersetzt wird, das mit einem Hash übereinstimmt. (Selbst wenn der Ersatz Kauderwelsch ist, kann der bloße Austausch des Originals zu Störungen führen.)

Nummer 3 impliziert Nummer 2.

Insbesondere bei MD5 hat sich gezeigt, dass es fehlerhaft ist: Wie man MD5 und andere Hash-Funktionen unterbricht .

Aber hier kommen Regenbogentische ins Spiel. Grundsätzlich handelt es sich nur um eine große Anzahl von Werten, die separat gehasht wurden, und das Ergebnis wird dann auf der Festplatte gespeichert. Dann ist das Umkehrbit "nur", um eine Suche in einer sehr großen Tabelle durchzuführen.

Dies ist natürlich nur für eine Teilmenge aller möglichen Eingabewerte möglich, aber wenn Sie die Grenzen des Eingabewerts kennen, ist es möglicherweise möglich, ihn zu berechnen.

Chinesische Wissenschaftler haben einen Weg gefunden, der als "Kollisionen mit ausgewählten Präfixen" bezeichnet wird, um einen Konflikt zwischen zwei verschiedenen Zeichenfolgen herzustellen.

Hier ein Beispiel: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Der Quellcode: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0. 5_source.zip

Wie die meisten bereits gesagt haben, wurde MD5 für Datenströme variabler Länge entwickelt, die auf einen Datenblock fester Länge gehasht werden sollen, sodass ein einzelner Hash von vielen Eingabedatenströmen gemeinsam genutzt wird.

Wenn Sie jedoch jemals die Originaldaten aus der Prüfsumme herausfinden mussten, z. B. wenn Sie den Hash eines Passworts haben und das Originalpasswort herausfinden müssen, ist es oft schneller, nur den Hash zu googeln (oder einen beliebigen Sucher, den Sie bevorzugen) für die Antwort als es brutal zu erzwingen. Ich habe mit dieser Methode einige Passwörter erfolgreich herausgefunden.

Der beste Weg, um zu verstehen, was die am häufigsten bewerteten Antworten bedeuten, besteht darin, tatsächlich zu versuchen, den MD5-Algorithmus zurückzusetzen. Ich erinnere mich, dass ich versucht habe, die MD5-Verschlüsselung einigen Jahren Algorithmus zurückzusetzen, nicht die ursprüngliche Nachricht wiederherzustellen, da dies eindeutig unmöglich ist, sondern nur eine Nachricht zu generieren, die denselben Hash wie der ursprüngliche Hash erzeugt. Dies würde mir zumindest theoretisch die Möglichkeit bieten, mich bei einem Linux-Gerät anzumelden, auf dem der Benutzer gespeichert ist: Kennwort in der Datei / etc / passwd unter Verwendung der generierten Nachricht (Kennwort) anstelle der ursprünglichen Nachricht. Da beide Nachrichten denselben resultierenden Hash haben würden, würde das System mein Passwort (das aus dem ursprünglichen Hash generiert wurde) als gültig erkennen. Das hat überhaupt nicht funktioniert. Nach einigen Wochen, wenn ich mich richtig erinnere, die Verwendung von Salzin der ersten Nachricht hat mich getötet. Ich musste nicht nur eine gültige Anfangsnachricht erstellen, sondern auch eine gesalzene gültige Anfangsnachricht, was ich nie konnte. Aber das Wissen, das ich aus diesem Experiment erhielt, war nett.

per definitionem Hash (kryptografische Hash) -Funktion: sollte nicht invertierbar sein; sollte keine Kollisionen haben (am wenigsten möglich).

regd Ihre Frage: Es ist ein Weg Hash. Die Eingabe (unabhängig von der Länge) generiert eine Ausgabe mit fester Größe (sie wird basierend auf algo aufgefüllt (512-Bit-Grenze für MD5)). Die Informationen sind komprimiert (verloren) und können aus Rücktransformationen praktisch nicht generiert werden.

Zusätzliche Informationen zu MD5: Es ist anfällig für Kollisionen. diesen Artikel kürzlich durchgesehen, http://www.win.tue.nl/hashclash/Nostradamus/

Der geöffnete Quellcode für Krypto-Hash-Implementierungen (MD5 und SHA) finden Sie unter Mozilla-Code. (freebl Bibliothek).

Jetzt werden ein Tag MD5-Hashes oder andere Hashes für alle möglichen Zeichenfolgen vorberechnet und für einen einfachen Zugriff gespeichert. Obwohl MD5 theoretisch nicht umkehrbar ist, können Sie mithilfe solcher Datenbanken herausfinden, welcher Text zu einem bestimmten Hashwert geführt hat.

Versuchen Sie beispielsweise den folgenden Hash-Code unter http://gdataonline.com/seekhash.php , um herauszufinden, welchen Text ich zur Berechnung des Hash verwendet habe

aea23489ce3aa9b6406ebb28e0cda430

f (x) = 1 ist irreversibel. Hash-Funktionen sind nicht irreversibel.

Dies ist tatsächlich erforderlich, damit sie ihre Funktion erfüllen können, festzustellen, ob jemand eine unverfälschte Kopie der Hash-Daten besitzt. Dies erhöht die Anfälligkeit für Brute-Force-Angriffe, die heutzutage sehr mächtig sind, insbesondere gegen MD5.

Es gibt auch hier und anderswo Verwirrung unter Menschen, die mathematische Kenntnisse haben, aber nur wenig Wissen über Chiffren. Mehrere Chiffren XOR die Daten einfach mit dem Schlüsselstrom, und so könnte man sagen, dass ein Chiffretext allen Klartexten dieser Länge entspricht, da Sie jeden Schlüsselstrom hätten verwenden können.

Dies ignoriert jedoch, dass ein vernünftiger Klartext, der aus dem Samen erzeugt passwordwird, viel, viel wahrscheinlicher ist als ein anderer, der aus dem Samen erzeugt wird Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o, insofern, als jeder, der behauptet, der zweite sei eine Möglichkeit, ausgelacht würde.

In gleicher Weise, wenn Sie zwischen den beiden potenziellen Passwörter zu entscheiden , sind versuchen passwordund Wsg5Nm^bkI4EgxUO, ist es nicht so schwer zu tun , wie einige Mathematiker Sie glauben machen wollen.

Ich mag all die verschiedenen Argumente. Es ist offensichtlich, dass der wahre Wert von Hash-Werten einfach darin besteht, nicht lesbare Platzhalter für Zeichenfolgen wie Kennwörter bereitzustellen. Es gibt keinen spezifischen erweiterten Sicherheitsvorteil. Angenommen, ein Angreifer hat Zugriff auf eine Tabelle mit gehashten Passwörtern erhalten, kann er / sie:

• Hash ein Passwort seiner / ihrer eigenen Wahl und platzieren Sie die Ergebnisse in der Passworttabelle, wenn er / sie Schreib- / Bearbeitungsrechte für die Tabelle hat.
• Generieren Sie Hash-Werte für allgemeine Kennwörter und testen Sie das Vorhandensein ähnlicher Hash-Werte in der Kennworttabelle.

In diesem Fall können schwache Passwörter nicht allein durch die Tatsache geschützt werden, dass sie gehasht sind.