Wie kommt es MD5-Hash-Werte nicht reversibel sind?

StackOverflow https://stackoverflow.com/questions/330207

Frage

Ein Konzept, das ich über immer gefragt habe, ist die Verwendung von verschlüsselten Hash-Funktionen und Werten. Ich verstehe, dass diese Funktionen einen Hash-Wert erzeugen, die einzigartig und praktisch unmöglich ist, rückgängig zu machen, aber hier ist, was ich habe mich immer gefragt:

Wenn auf meinem Server, in PHP ich produzieren: 

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

Wenn Sie ausführen, die gleiche Zeichenfolge durch eine MD5-Funktion, Sie das gleiche Ergebnis auf Ihrer PHP-Installation. Ein Prozess verwendet wird einen Wert zu erzeugen, von einem Startwert.

Bedeutet das nicht, dass es irgendeine Art und Weise zu dekonstruieren, was den Hash-Wert geschieht, und umgekehrt?

Was ist es über diese Funktionen, die die resultierenden Strings unmöglich macht zurückzuverfolgen?

War es hilfreich?

Lösung

Das Eingangsmaterial kann eine unendliche Länge sein, wobei der Ausgang immer 128 Bits lang ist. Dies bedeutet, dass eine unendliche Anzahl von Eingabezeichenfolgen wird die gleiche Leistung erzeugen.

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

Andere Tipps

Wenn Hash-Funktionen wie MD5 reversibel waren, dann wäre es ein Wendepunkt in der Geschichte der Datenkompressionsalgorithmen haben! Es ist einfach zu sehen, dass, wenn MD5 waren reversibel dann beliebige Datenblocks beliebiger Größe könnte durch einen bloßen 128 Bits ohne Informationsverlust dargestellt werden. So würden Sie in der Lage, die ursprüngliche Nachricht aus einer 128-Bit-Zahl unabhängig von der Größe der ursprünglichen Nachricht zu rekonstruieren.

Im Gegensatz zu dem, was die meist upvoted Antworten hier betonen, die Nicht-injectivity (dh, dass es mehrere Saiten auf den gleichen Wert Hashing) eine verschlüsselten Hash-Funktion durch den Unterschied zwischen großes verursacht (potentiell unendlich) Eingangsgröße und feste Ausgangsgröße ist nicht der entscheidende Punkt -. eigentlich bevorzugen wir Hash-Funktionen, wo diese Kollisionen so selten wie möglich passieren

Betrachten Sie diese Funktion (in PHP-Notation, wie die Frage): 

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

Dieses anhängt einige Räume, wenn die Zeichenfolge zu kurz ist, und nimmt dann die ersten 16 Bytes der Zeichenfolge, dann codiert sie als hexadezimal. Es hat die gleiche Ausgangsgröße als MD5-Hash (32 hexadezimalen Zeichen oder 16 Bytes, wenn wir den bin2hex Teil weglassen). 

print simple_hash("stackoverflow.com");

Dies wird ausgegeben: 

737461636b6f766572666c6f772e636f6d

Diese Funktion hat auch die gleiche nicht-injectivity Eigenschaft als von Codys Antwort für MD5 hervorgehoben: Wir in Strings jede Größe passieren können (solange sie in unseren Computer passen), und es wird nur ausgegeben, 32 Hex-Ziffern. Natürlich kann es nicht injektiv sein.

Aber in diesem Fall ist es trivial, eine Zeichenfolge zu finden, die auf den gleichen Hash-Karten (gilt nur hex2bin auf Hash, und Sie haben es). Wenn Ihre ursprüngliche Zeichenfolge die Länge 16 (als Beispiel) hat, werden Sie auch diese ursprüngliche Zeichenfolge erhalten. Nichts von dieser Art sollte möglich sein, für MD5, auch wenn Sie die Länge des Eingangs wissen recht kurz war (anders als durch alle möglichen Eingaben versuchen, bis wir einen finden, der paßt, zum Beispiel eines Brute-Force-Angriff).

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

  • es ist schwer, eine beliebige Zeichenfolge finden eine bestimmte Hash (Urbild Widerstand)
    • Herstellung
  • es ist schwer, eine andere Zeichenfolge zu finden, den gleichen Hash als ein String (zweiter Urbild Widerstand)
    • Herstellung
  • es ist schwer, jedes Paar von Strings mit dem gleichen Hash (Kollisionsresistenz)
    • zu finden

Offensichtlich meine simple_hash Funktion keine dieser Bedingungen erfüllt. (Eigentlich, wenn wir den Eingangsraum auf „16-Byte-Strings“ beschränken, dann meine Funktion wird injektiv, und somit ist auch beweisbar zweite Urbild fest und resistent gegen Kollisionen).

Es gibt jetzt Kollision Angriffe auf MD5 (zB ist es möglich, ein Paar von Strings zu erzeugen, auch mit einem gleichen Präfix gegeben, die den gleichen Hash haben, mit einigen ziemlich Arbeit, aber nicht unmöglich, viel Arbeit), so shouldn Sie ‚t MD5 entscheidend für alles verwenden. Es ist noch nicht ein Urbild Angriff, aber Angriffe besser werden.

die eigentliche Frage zu beantworten:

  

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

Was MD5 (und andere Hash-Funktionen auf der Merkle-Damgard Konstruktion bauen) wirksam mit der Nachricht als Schlüssel und etwas festen Wert als „Klartext“ ein Verschlüsselungsalgorithmus Sie bewirbt, den resultierenden Chiffretext als Hash verwendet wird. (Vor, dass der Eingang ist gepolstert und aufgeteilt in Blöcken, wobei jeder dieser Blöcke verwendet wird, um den Ausgang des vorhergehenden Blockes zu verschlüsseln, XOR-verknüpft mit seinem Eingang Umkehr Berechnungen zu verhindern.)

Moderne Verschlüsselungsalgorithmen (einschließlich der in Hash-Funktionen verwendet wurde) in einer Art und Weise gemacht werden, um es schwer, den Schlüssel zu erholen, auch gegeben sowohl Klar- und Geheimtext (oder sogar, wenn der Gegner wählt eine von ihnen). Sie tun dies in der Regel durch viele Bit-schlurfenden Operationen in eine Art und Weise zu tun, dass jeder Ausgang-Bit von jedem Schlüsselbart (mehrmals) und auch jedes Eingangsbit bestimmt wird. Auf diese Weise kann man nur leicht nachvollziehen, was im Innern passiert, wenn Sie den vollständigen Schlüssel kennen und als Eingang oder Ausgang.

Für MD5-ähnliche Hash-Funktionen und einen Urbild Angriff (mit einem Single-Block gehasht String, Dinge einfacher zu machen), haben Sie nur Eingang und Ausgang Ihrer Verschlüsselungsfunktion, aber nicht den Schlüssel (das ist, was Sie suchen für).

Cody Brocious Antwort ist die richtige. Streng genommen kann man nicht „invertieren“, um eine Hash-Funktion, weil viele Saiten auf den gleichen Hash-abgebildet werden. Beachten Sie jedoch, dass entweder die Suche nach einem Zeichenfolge, die zu einem bestimmten Hash-abgebildet wird, oder die Suche nach zwei Strings, die auf den gleichen Hash zugeordnet bekommen (dh einen Kollision ), würde für ein Kryptanalytiker großer Durchbruch sein. Die große Schwierigkeit dieser beiden Probleme ist der Grund, warum gute Hash-Funktionen, die in der Kryptographie sind.

MD5 erzeugt keinen eindeutigen Hash-Wert; das Ziel von MD5 ist, um schnell einen Wert zu erzeugen, der auf einer kleinen Änderung an der Quelle deutlich Basis ändert.

z. B. 

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

(Natürlich, das ist nicht unbedingt die MD5-Verschlüsselung)

Die meisten Hashes (wenn nicht alle) sind auch nicht eindeutig; sondern sie sind einzigartig genug , so dass eine Kollision sehr unwahrscheinlich ist, aber immer noch möglich.

Eine gute Möglichkeit, einen Hash-Algorithmus zu denken ist, ein Bild in Photoshop denken Ändern der Größe ... sagen Sie ein Bild, die 5000x5000 Pixel ist und Sie dann die Größe nur 32x32 an. Was Sie haben, ist immer noch eine Darstellung des ursprünglichen Bildes, aber es ist viel viel kleiner und effektiv „weggeworfen“ bestimmte Teile der Bilddaten, um es in der kleineren Größe passen zu machen. Also, wenn Sie, dass 32x32 Bild, um die Größe sind wieder bis zu 5000x5000 alles, was Sie bekommen würden, ist ein verschwommenes Chaos. Doch weil ein 32x32 Bild nicht so groß ist, wäre es theoretisch denkbar, dass ein anderes Bild verkleinert werden könnte genau die gleichen Pixel zu produzieren!

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

Eine Hash-Kollision ist viel wahrscheinlicher, als Sie denken. Werfen Sie einen Blick auf die Geburtstagsparadox ein besseres Verständnis dafür zu bekommen, 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, eindeutig zu jedem möglichen einem MD5-Hash zuweisen.

kryptographische Hash-Funktionen werden zur Überprüfung der Datenintegrität oder digitale Signaturen (der Hash wird signiert zur Wirkungsgrad) eingesetzt. das Originaldokument ändern sollte somit die ursprüngliche Hash nicht das geänderte Dokument überein.

Diese Kriterien manchmal verwendet:

  1. Urbild Widerstand:. Für eine bestimmte Hash-Funktion und bestimmte Hash sollte es schwierig sein, einen Eingang zu finden, die den angegebenen Hash für diese Funktion hat
  2. Zweiter Urbild Widerstand: für eine bestimmte Hash-Funktion und Eingabe sollte es schwierig sein, einen zweiten, anderen Eingang mit dem gleichen Hash zu finden
    3. .
  3. Kollisionswiderstand: für eine bestimmte Funktion hat, sollte es schwierig sein, zwei verschiedene Eingänge mit dem gleichen Hash zu finden.

Diese criterial sind so gewählt, was es schwierig macht, ein Dokument zu finden, die einen bestimmten Hash übereinstimmt, sonst wäre es möglich, Dokumente zu fälschen, indem das Original mit einem ersetzt, die durch Hash abgestimmt. (Auch wenn der Ersatz Kauderwelsch ist, der bloße Austausch des Originals kann Störungen verursachen.)

Number 3 bedeutet, die Nummer 2.

Wie für MD5 insbesondere hat es sich als fehlerhaft dargestellt: Wie brechen MD5 und andere Hash-Funktionen .

Aber das ist, wo Rainbow-Tabellen ins Spiel kommen. Im Grunde ist es nur eine große Menge von Werten separetely gehasht und dann wird das Ergebnis auf der Festplatte gespeichert. Dann wird das Umkehr-Bit „nur“ eine Suche in einer sehr großen Tabelle zu tun.

Natürlich ist dies nur möglich, für eine Teilmenge aller möglicher Eingabewerte, aber wenn Sie die Grenzen des Eingangswertes wissen könnte es möglich sein, sie zu berechnen.

Chinesische Wissenschaftler haben einen Weg gefunden „gewählt-Präfix Kollisionen“ bezeichnet einen Konflikt zwischen zwei verschiedenen Saiten zu machen.

Hier ist 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

Da die meisten haben bereits gesagt, MD5 für Daten mit variabler Länge Strom ausgelegt wurde auf eine festgelegte Länge Chunk von Daten gehasht werden, so dass ein einzelner Hash wird geteilt von vielen Eingangsdatenströmen.

Wenn Sie jedoch immer die Originaldaten aus der Prüfsumme herauszufinden haben müssen, wenn Sie zum Beispiel den Hash eines Passworts haben und müssen das Original-Passwort, um herauszufinden, ist es oft schneller, nur Google (oder was auch immer Sucher Sie bevorzugen der Hash) für die Antwort als auf rohe Gewalt es. Ich habe erfolgreich ein paar Passwörter mit dieser Methode herausgefunden hat.

Der beste Weg, um zu verstehen, was all die meisten Stimmen Antworten ist gemeint, um zu versuchen, tatsächlich den MD5-Algorithmus zurückzukehren. Ich erinnere mich, ich versuchte, die md5crypt Algorithmus vor einigen Jahren zurückzukehren, nicht die ursprüngliche Nachricht zu erholen, weil es offensichtlich unmöglich ist, sondern nur eine Nachricht zu erzeugen, die den gleichen Hash wie der ursprüngliche Hash erzeugen würde. Dies ist zumindest theoretisch würde mir bietet eine Möglichkeit, zu einem Linux-Gerät anmelden, die den Benutzer gespeichert: Passwort in der Datei / etc / passwd die erzeugte Nachricht mit (Passwort), statt das Original zu verwenden. Da beide Meldungen die gleiche resultierende Hash haben würde, würde das System mein Passwort erkennen (aus dem ursprünglichen Hash generiert) als gültig. Das ist nicht bei allen. Nach einigen Wochen, wenn ich mich richtig erinnere, hat mich getötet die Verwendung von Salz in der Anfangsnachricht. Ich musste nicht nur eine gültige Anfangsnachricht erzeugen, sondern eine gesalzene gültige erste Nachricht, die ich nie in der Lage war zu tun. Aber das Wissen, dass ich aus diesem Experiment bekamen, war schön.

per Definition Hash (verschlüsselte Hash) Funktion:. Sollte nicht umkehrbar sein, sollte nicht Kollisionen hat (am wenigsten möglich)

regd Ihre Frage: es ist ein Weg-Hash. Eingang (unabhängig von der Länge) wird eine feste Größe Ausgabe erzeugen. (es wird basierend auf Algo (512 Bit-Grenze für MD5) aufgefüllt werden). Die Informationen werden komprimiert (verloren) und praktisch nicht möglich, von Umkehrtransformationen zu erzeugen.

weitere Informationen über MD5: es ist anfällig für Kollisionen. gegangen kürzlich durch diesen Artikel, http://www.win.tue.nl/hashclash/Nostradamus/

öffnet Quellcode für Krypto Hash-Implementierungen (MD5 und SHA) an Mozilla Code. (Freebl Bibliothek).

Nun wird ein Tag MD5-Hashes oder andere Hashes für diese Angelegenheit vorge berechnet für alle möglichen Strings und für den einfachen Zugriff gespeichert. Obwohl in der Theorie MD5 nicht reversibel ist, aber mit solchen Datenbanken können Sie herausfinden, welcher Text in einem bestimmten Hash-Wert geführt.

Zum Beispiel versuchen, den folgenden Hash-Code unter http://gdataonline.com/seekhash.php herauszufinden, welchen Text ich die Hash-Berechnung verwendet, um 

aea23489ce3aa9b6406ebb28e0cda430

f (x) = 1 ist irreversibel. Hash-Funktionen sind nicht rückgängig gemacht werden.

Dies ist eigentlich erforderlich , damit sie ihre Funktion erfüllen zu bestimmen, ob jemand eine unbeschädigte Kopie der Hash-Daten besitzt. Dies bringt die Anfälligkeit für Brute-Force-Angriffe, die sehr mächtig in diesen Tagen, vor allem gegen MD5.

Es gibt auch hier Verwirrung und anderswo unter Menschen, die mathematischen Kenntnisse, aber wenig cipherbreaking Wissen. Mehrere Chiffren die Daten XOR einfach mit dem Schlüsselstrom, und so könnte man sagen, dass ein Geheimtext für alle Klartexte dieser Länge entspricht, da Sie jede Keystream verwendet haben könnten.

Allerdings ignoriert dies, dass eine vernünftige Klar aus dem Samen password produziert viel, viel wahrscheinlicher als ein anderer von der Saatgut Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o in dem Maße erzeugt, dass jemand behauptet, dass die zweite Möglichkeit gelacht würde war.

In der gleichen Weise, wenn Sie zwischen den beiden potenziellen Passwörter password und Wsg5Nm^bkI4EgxUO zu entscheiden, sind versucht, es ist nicht so schwer zu tun, wie einige Mathematiker haben würden Sie glauben.

Ich mag alle die verschiedenen Argumente. Es ist offensichtlich, dass der reale Wert der Hash-Werte einfach ist wie Passwörter Menschen unlesbar Platzhalter für Zeichenketten zu liefern. Es hat keine besondere verbesserte Sicherheit profitieren. Unter der Annahme, dass ein Angreifer sich Zugang zu einer Tabelle mit Hash-Passwörtern, kann er / sie:

  • Hash ein Passwort seiner / ihrer eigenen Wahl und die Ergebnisse in der Kennwort-Tabelle platzieren, wenn er / sie schriftlich bearbeiten / Rechte an der Tabelle hat.
  • Generieren Hash-Werte von gemeinsamen Passwörtern und testen Sie die Existenz ähnlicher Hash-Werte in der Kennwort-Tabelle.

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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top