Frage an cryptography, hash-function, hash – Was sind die wichtigen Punkte bei kryptografischen Hash-Funktionen?

11

ich habe gelesendiese Frage auf MD5 Hash-Werte und die akzeptierte Antwort verwirrt mich. Eine der Haupteigenschaften einer kryptografischen Hash-Funktion besteht meines Wissens darin, dass es unmöglich ist, zwei verschiedene Nachrichten (Eingaben) mit demselben Hash-Wert zu finden.

Doch die Konsensantwort auf die FrageWarum sind MD5-Hashwerte nicht umkehrbar? istWeil eine unendliche Anzahl von Eingabezeichenfolgen dieselbe Ausgabe erzeugt. Dies scheint mir völlig widersprüchlich.

Was mich auch etwas verwirrt, ist die Tatsache, dass die Algorithmen öffentlich sind, die Hash-Werte aber immer noch irreversibel sind. Liegt dies daran, dass eine Hash-Funktion immer Datenverluste aufweist, sodass nicht festgestellt werden kann, welche Daten weggeworfen wurden?

Was passiert, wenn die Eingabedatengröße kleiner als die feste Ausgabedatengröße ist (z. B. Hashing eines Passworts "abc")?

BEARBEITEN:

OK, mal sehen, ob ich das gerade habe:

Es ist wirklich sehr schwer, den Input aus dem Hash abzuleitenweil es unendlich viele Eingabe-Strings gibt, die die gleiche Ausgabe erzeugen (irreversibles Vermögen).Jedoch,finden Selbst eine einzige Instanz mehrerer Eingabezeichenfolgen, die dieselbe Ausgabe erzeugen, ist sehr, sehr schwierig (kollisionsresistente Eigenschaft).
Ja, der "Konsens" in den Antworten auf dieFrage, die Sie verlinkt haben ist völlig falsch. Ich habe gerade eine weitere Antwort hinzugefügt, um dies zu korrigieren. Paŭlo Ebermann
Ich habe deine Bearbeitung nicht gesehen. Ich denke, Sie haben es in diesen beiden Aufzählungszeichen zusammengefasst. Alex Feinman
Der Grund für die Umkehrbarkeitseigenschaft ist nicht die "unendliche Anzahl von Eingabezeichenfolgen". Dies sollte auch der Fall sein, wenn Sie die Eingabe auf etwas Kleines beschränken (z. B. um die Ausgabegröße herum). Paŭlo Ebermann

Deine Antwort

6   die antwort
2

Ein Wort der Vorsicht, MD5 sollte wegen der darin gefundenen Schwachstellen nicht mehr verwendet werden. Überprüfen Sie den Abschnitt "Sicherheitslücken" und die externen Links, die diese Angriffe beschreiben.http://en.wikipedia.org/wiki/Md5 Sie können eine MD5-Kollision durchführen, indem Sie in einer Nachricht nur 128 Bit ändern.

SHA-1 ist sicher für einfaches Hashing, obwohl es einige Angriffe gibt, die es gegenüber gut finanzierten Unternehmen (Regierungen, große Unternehmen) schwächer machen würden.

SHA-256 ist ein sicherer Ausgangspunkt für die nächsten Jahrzehnte.

@ vg1890: Eigenschaften vonkryptografisch Hash-Funktionen. H (x) = x mod 2 ist keine kryptographische Hashfunktion. (Es könnte jedoch für eine Hash-Tabelle mit zwei Einträgen gut sein.) Paŭlo Ebermann
Nicht unbedingt. Die akzeptierte Antwort in der Frage, auf die ich verlinkt habe, verwendet ein Beispiel für eine Hash-Funktion H (x) = x mod 2. Diese Hash-Funktion weist die schwer umkehrbare Eigenschaft auf, jedoch nicht die kollisionsarme Eigenschaft. Rob Sobers
6

die Frage, die Sie zitieren ist verwirrend. Eine der Anforderungen für eine kryptografische Hash-Funktion ist, dass sie vor dem Bild geschützt ist. Das heißt, wenn Sie MD5 (x) kennen, aber nicht die Nachricht x, dann ist es schwierig, ein x '(entweder gleich x oder verschieden von x) zu finden, so dass MD5 (x') = MD5 (x).

Preimage-resistent zu sein ist eine andere Eigenschaft als reversibel zu sein. Eine Funktion ist reversibel, wenn bei y = f (x) genau ein x passt (ob das einfach ist oder nicht). Definiere zum Beispiel f (x) = x mod 10. Dann ist f nicht umkehrbar. Aus f (x) = 7 kann man nicht bestimmen, ob x 17, 27 oder etwas anderes war. F ist jedoch nicht vorab bildresistent, da Werte x 'mit f (x) = 7 leicht zu finden sind. x '= 17, 27, 12341237 usw. alle arbeiten.

Wenn Sie Kryptografie ausführen, benötigen Sie normalerweise Funktionen, die vor dem Bild geschützt sind (und andere Eigenschaften wie Kollisionssicherheit), und nicht nur etwas, das nicht umkehrbar ist.

18

Warnung: Lange Antwort

Ich denke, all diesen Antworten fehlt eine sehr wichtige Eigenschaft von kryptografischen Hash-Funktionen: Es ist nicht nur unmöglich, die ursprüngliche Nachricht zu berechnen, die gehasht wurde, um einen bestimmten Hash zu erhalten, sondern es ist auch unmöglich, sie zu berechnenirgendein Nachricht, die auf einen bestimmten Hash-Wert gehasht würde. Das nennt manPreimage-Widerstand.

(Mit "unmöglich" meine ich, dass niemand weiß, wie man es in kürzerer Zeit macht, als es nötig ist, jede mögliche Nachricht zu erraten, bis Sie die erraten, die in Ihren Hash gehackt wurde.)

(Trotz des weitverbreiteten Glaubens an die Unsicherheit von MD5 ist MD5 immer noch preimage-resistent. Wer mir nicht glaubt, kann mir alles geben, worauf es ankommt2aaddf751bff2121cc51dc709e866f19. Was MD5 nicht hat, istKollisionsfestigkeit, das ist was ganz anderes.)

Wenn der einzige Grund, warum Sie in einer kryptografischen Hash-Funktion nicht "rückwärts arbeiten" können, darin besteht, dass die Hash-Funktion Daten verwirft, um den Hash zu erstellen, ist dies keine Garantie für die Resistenz gegen Vorbilder: Sie können immer noch "rückwärts arbeiten" und nur einfügen Überall dort, wo die Hash-Funktion Daten verwirft und Sie nicht auf die ursprüngliche Nachricht gekommen wären, hätten Sie immer noch eine Nachricht gefunden, die den gewünschten Hash-Wert aufweist. Aber du kannst nicht.

Die Frage lautet also: Warum nicht? (Oder mit anderen Worten, wie macht man eine Funktion vor dem Bild widerstandsfähig?)

Die Antwort ist, dass kryptografische Hash-Funktionen chaotische Systeme simulieren. Sie nehmen Ihre Nachricht auf, teilen sie in Blöcke auf, mischen diese Blöcke um sich herum, lassen einige der Blöcke miteinander interagieren, mischen diese Blöcke um sich herum und wiederholen dies viele Male (nun, eine kryptografische Hash-Funktion macht das, andere haben ihre eigene Methoden). Da die Blöcke miteinander interagieren, muss Block C nicht nur mit Block D interagieren, um Block A zu erzeugen, sondern muss auch mit Block E interagieren, um Block B zu erzeugen. Nun können Sie sicher die Werte der Blöcke C, D, E würde die Blöcke A und B in Ihrem Hash-Wert erzeugen, aber wenn Sie weiter zurückgehen, benötigen Sie plötzlich einen Block F, der mit C interagiert, um D zu machen, und mit E, um B zu machen, und kein solcher Block kann beides bei die selbe Zeit! Sie müssen falsche Werte für C, D und E erraten haben.

Zwar sind nicht alle kryptografischen Hash-Funktionen genau so, wie sie oben für die Blockinteraktion beschrieben wurden, sie haben jedoch dieselbe Idee: Wenn Sie versuchen, "rückwärts" zu arbeiten, werden Sie eine ganze Menge Sackgassen und die Zeit davon haben Es dauert nicht viel länger, bis Sie genügend Werte ausprobiert haben, um ein Pre-Image zu generieren. Dies liegt in der Größenordnung von Hunderten bis Millionen von Jahren (abhängig von der Hash-Funktion).

0

Warum sind MD5-Hashwerte nicht umkehrbar?; ist, weil ;eine unendliche Anzahl von Eingabezeichenfolgen> dieselbe Ausgabe erzeugen wird;

Dies ist der Grund, warum es nicht möglich ist, die Hash-Funktion umzukehren (dieselbe Eingabe zu erhalten). kryptografische Hash-Funktionen sind kollisionssicher, das heißt, es ist auch schwierig, einen anderen Eingabewert zu finden, der derselben Ausgabe zugeordnet ist (wenn Ihre Hash-Funktion Mod 2 war: 134 Mod 2 = 0; jetzt können Sie die 134 nicht mehr aus dem zurückholen Ergebnis, aber wir können immer noch Nummer 2 mit dem gleichen Ausgabewert finden (134 und 2 kollidieren).

Wenn die Eingabe kleiner als die Blockgröße ist,Polsterung wird verwendet, um es an die Blockgröße anzupassen.

Das Umkehren der Funktion ist etwas anderes als das Auffinden einer Kollision. Im Idealfall besteht die einzige Möglichkeit, die Kollision zu finden, darin, eine Eingabe nach der anderen zu versuchen und das Ergebnis der Hash-Funktion mit dem Wert zu vergleichen, dessen Kollision Sie umkehren / finden möchten (das ist schwierig). Aber selbst wenn Sie das getan hätten, würden Sie nicht wissen, ob die Kollision, die Sie gefunden haben, die ursprüngliche war oder ob Sie gerade eine neue Zeichenfolge mit demselben Hashwert gefunden haben. cube
Es macht immer noch keinen Sinn, dass es schwierig ist, zwei Eingänge zu finden, die den gleichen Ausgang erzeugen. Die Tatsache, dass viele Eingänge den gleichen Ausgang haben, ist der Grund, warum der Hash irreversibel ist. Wie ist das kein Widerspruch? Rob Sobers
12

1: Der Hauptzweck eines Hashs besteht darin, einen sehr, sehr großen Raum einem kleineren, aber immer noch sehr großen Raum zuzuordnen (z.. MD5, das "alles" aufnimmt und in einen Raum der Größe 2 ^ 128 - big umwandelt , aber nicht annähernd so groß wie aleph-0.)

Neben anderen Funktionengut Hashes füllen den Zielraum homogen aus. Schlechte Hashes füllen den Raum auf eine klumpige Art und Weise und liefern denselben Hash für viele häufige Eingaben.

Stellen Sie sich die idiotische Hash-Funktion sum () vor, die nur alle Ziffern der eingegebenen Zahl addiert: Es gelingt ihr, eine Zuordnung nach unten vorzunehmen, aber es gibt eine Reihe von Kollisionen (Eingaben mit derselben Ausgabe wie 3 und 12 und 21) auf dem niedrigen Wert Ende des Ausgaberaums und das obere Ende des Raums ist fast leer. Infolgedessen nutzt es den Raum sehr schlecht aus, ist leicht zu knacken usw.

Ein guter Hash, der sogar den Zielbereich ausnutzt, macht es schwierig, zwei Eingaben mit derselben Ausgabe zu finden, nur durch die Quote: Wenn MD5 perfekt wäre, wäre die Quote, dass zwei Eingaben dieselbe Ausgabe haben würden, 2 ^ - 128. Das sind ziemlich gute Chancen: Daseste, was Sie tun können, ohne auf einen größeren Ausgaberaum zurückzugreifen. (In Wahrheit ist MD5 nicht perfekt, was eines der Dinge ist, die es anfällig machen.)

Aber es wird immer noch wahr sein, dass eine große Anzahl von Eingaben auf einen bestimmten Hash abgebildet wird, weil der Eingaberaum 'unendlich' ist und das Teilen von Unendlich durch 2 ^ 128 immer noch Unendlich ergibt.

2: Ja, Hashes verursachen immer Datenverlust, es sei denn, Ihr Ausgabebereich ist derselbe oder größer als Ihr Eingabebereich - und in diesem Fall mussten Sie wahrscheinlich kein Hashing durchführen!

3:ei kleineren Eingaben empfiehlt es sich, die Eingabe zu salzen. Tatsächlich ist dies eine gute Vorgehensweise für kryptografisches Hashing, da ein Angreifer Sie sonst mit bestimmten Eingaben versorgen und herausfinden kann, welchen Hash Sie verwenden. 'Salt' ist nur eine Reihe zusätzlicher Informationen, die Sie an Ihre Eingabe anhängen (oder voranstellen). Sie haben dann das Ergebnis gehasht.

bearbeiten: In der Kryptographie ist es auch wichtig, dass die Hash-Funktion gegenüber Preimage-Angriffen resistent ist, was intuitiv schwierig ist, die Eingabe für eine bestimmte Ausgabe zu erraten, selbst wenn viele andere Eingabe / Ausgabe-Paare bekannt sind. Die "Summen" -Funktion könnte wahrscheinlich ziemlich leicht erraten werden (da sie jedoch Daten zerstört, ist es möglicherweise nicht einfach, sie rückgängig zu machen).

+1, obwohl einige Details fehlen, denke ich, dass diese Antwort immer noch nützlich ist. laalto
Ich bin mir nicht sicher, wie ich es bearbeiten soll, ohne deine Antwort vollständig zu ändern. Zarels Antwort sieht jedoch ganz gut aus. Argumentieren Sie nicht so oft mit "Odds", da dies voraussetzt, dass der Angreifer nichts Besseres tun kann, als es zufällig zu versuchen. (Wenn die Hash - Funktion eine gute kryptografische Funktion ist, ist dies der Fall, aber Ihr Argument sagt nichts darüber aussimple_hash Funktioniere in meiner Antwort auf die andere Frage und überprüfe, welches deiner Argumente auch darauf zutrifft - das sind die falschen.) Paŭlo Ebermann
Ihr schlechtes Hash ist wie mein idiotisches Hash: Es hat eine schlechte Homogenität und eine schreckliche Kollisionsstrategie. Ich denke, ich werde es bearbeiten, um anzuzeigen, dass die von mir erwähnten Funktionen für eine kryptografisch starke Hash-Funktion notwendig, aber nicht ausreichend sind, da einige Punkte erklärt haben, dass die Antwort von Zarel überglättet ist. Alex Feinman
-1 Sie haben den Punkt übersehen, dass es rechenintensiv sein sollte, die Hash-Funktion umzukehren. Eine lineare Funktion kann die Hash-Werte sehr gut verteilen und dennoch für die Kryptographie ungeeignet sein. starblue
1

Warum sind MD5-Hashwerte nicht umkehrbar?" ist, weil "eine unendliche Anzahl von Eingabezeichenfolgen die gleiche Ausgabe erzeugen wird."

Dies gilt für jede Hash-Funktion, ist jedoch nicht die Essenz einer kryptografischen Hash-Funktion.

Für kurze Eingabezeichenfolgen wie Kennwörter ist es theoretisch möglich, eine kryptografische Hash-Funktion umzukehren, sie sollte jedoch rechnerisch nicht durchführbar sein. Das heißt Ihre Berechnung würde zu lange dauern, um nützlich zu sein.

Der Grund für diese Unmöglichkeit ist, dass die Eingabe im Hash-Wert so gründlich "gemischt" wird, dass es unmöglich wird, sie mit weniger Aufwand als dem Brute-Force-Angriff der Berechnung des Hash-Werts für alle Eingaben zu entwirren

Verwandte Fragen