Frage:
Können Sie herausfinden, wie groß die Änderungen sind, indem Sie zwei Hashes vergleichen?
Maria Ahmed
2020-02-19 16:45:39 UTC
view on stackexchange narkive permalink

Mir ist klar, dass eine Hash-Funktion eine Einwegfunktion ist und dass Änderungen im Hash uns mitteilen sollen, dass sich die Originaldaten geändert haben (dass sich der gesamte Hash selbst bei den geringsten Änderungen an Daten ändert).

Aber gibt es eine Möglichkeit herauszufinden, inwieweit sich die Originaldaten geändert haben, wenn zwei Hashes unterschiedlich sind?

Die Antworten, die Sie hier erhalten, gelten für kryptografische Hash-Funktionen.Beachten Sie, dass es andere Arten von Hash-Funktionen mit unterschiedlichen Eigenschaften gibt, z. B. Wahrnehmungs-Hashing für Bilder.
Das Definieren eines "differenzierbaren Digests" ist nicht trivial und anwendungsspezifisch - im Grunde fragen Sie nach einem äußerst verlustbehafteten Komprimierungsalgorithmus.Ein Beispiel ist ein Programm, das ein Foto oder Bild aufnimmt und es im Wesentlichen auf (zum Beispiel) 64 x 64 Pixel verkleinert (was eine „Hash-Größe“ von 12 KB ergibt).Dann hat ein anderes, aber visuell ähnliches Bild bei gleicher Behandlung eine sehr ähnliche 64 × 64 Pixel-Darstellung, und dann kann ein "Differenz" -Maß abgeleitet werden (z. B. Vergleichen von Pixelhistogrammen).Dies ist jedoch ein elementares Beispiel.Siehe auch https://stackoverflow.com/q/6499491/159145
Insbesondere wenn Salz verwendet wird, besteht keine Chance, den Unterschied zu finden.
[w-shingling] (https://en.wikipedia.org/wiki/W-shingling).MinHash und SimHash sind praktische Anwendungen.
Alle harten Negative hier stehen im Zusammenhang mit einer sicheren Hash-Funktion;Da es sich um eine InfoSec-Q & A-Site handelt, ist dies sinnvoll.Die Art der Konstruktion, nach der Sie fragen, gibt es jedoch in verschiedenen Formen und es gibt viele nützliche Anwendungen.Beispielsweise kann [lokalitätssensitives Hashing] (https://en.wikipedia.org/wiki/Locality-sensitive_hashing) verwendet werden, um probabilistisch zu bestimmen, wie ähnlich zwei Eingaben sind.
Vielleicht sind Hashes nicht der richtige Weg, um Unterschiede herauszufinden.Wenn Sie danach suchen, lesen Sie https://en.wikipedia.org/wiki/Levenshtein_distance
@Mark +1 bitte in einer Antwort näher erläutern?
Acht antworten:
#1
+93
MechMK1
2020-02-19 17:10:24 UTC
view on stackexchange narkive permalink

Nein, zumindest mit einer guten Hash-Funktion.

Sie können dies selbst testen, indem Sie einen Hash für einen bestimmten Datensatz und dann einen modifizierten Hash für einen anderen Datensatz erstellen. Sie werden sehen, dass jedes Bit der resultierenden Hash-Funktion eine Wahrscheinlichkeit von 50% zum Umdrehen hat.

Ich werde dies demonstrieren, indem ich den SHA-256-Hash der Zeichenfolge MechMK1 erstelle :

  $ echo -n "MechMK1" | sha256sum2c31be311a0deeab37245d9a98219521fb36edd8bcd305e9de8b31da76e1ddd9  

Wenn diese binären in Konvertieren Sie folgendes Ergebnis:

  00101100 00110001 10111110 00110001 00011010 00001101 11101110 1010101100110111 00100100 01011101 10011010 10011000 00100001 10010101 0010000111111011 00110110 11101101 11011000 10111100 11010011 00000101 1110100111011110 10001011 00110001 11011010 01110110 11100001 11011101 11011001  

Jetzt berechne ich den SHA-256-Hash der Zeichenfolge MechMK3 , der ein Bit von ändert Eingabe:

  $ echo -n "MechMK3" | sha256sum3797dec3453ee07e60f8cf343edb7643cecffcf0af847a73ff2a1912535433cd  

Wenn wieder in binären umgewandelt, Sie erhalten folgendes Ergebnis:

  00110111 10010111 11011110 11000011 01000101 00111110 11100000 0111111001100000 11111000 11001111 00110100 00111110 11011011 01110110 0100001111001110 11001111 11111100 11110000 10101111 10000100 01111010 0111001111111111 00101010 00011001 00010010 01010011 01010100 00110011 11001101  

Ich habe beide Ergebnisse verglichen und überprüft, wie oft sich ein Bit von beiden Hashes unterschied und genau 128 oder 50% aller Bits unterschieden . Wenn Sie selbst damit herumspielen und sehen möchten, welche Ergebnisse Sie erzielen, habe ich ein einfaches C-Programm erstellt, das genau das tut.

Mein Gedanke beim Lesen der Frage war "Gee, ich hoffe sicher nicht".
Technisch gesehen ist dies nur die Hälfte der Frage.Wenn beim Umdrehen eines Bits 50% aller Bits umgedreht werden, beim Umdrehen von zwei Bits jedoch 75% umgedreht werden (50% + .5 * 50%), können Sie den Unterschied anhand der Tatsache erkennen, dass größere Unterschiede mehr Änderungen verursachen.Ich weiß, dass dies nicht der Fall ist, aber ich denke, dass es in dieser ansonsten ausgezeichneten Antwort eine Erwähnung wert wäre.
@Bobson Ich denke, dass die anderen Antworten, die etwas mehr in die Theorie dahinter einfließen, so viel besser antworten als ich.Ich wollte nur eine praktische Demonstration geben und die Leute ermutigen, Dinge selbst auszuprobieren.
Mir wurde beigebracht, dass der Fachbegriff [Diffusion] ist (https://en.wikipedia.org/wiki/Confusion_and_diffusion).
@Bobson fehlerhaftes Denken dort - stellen Sie sich 100 Bit alle Nullen vor.Drehen Sie die Hälfte der Bits nach dem Zufallsprinzip um.Wir haben jetzt halb und halb, 50 0s und 50 1s.Drehen Sie nun die Hälfte aller Bits wieder nach dem Zufallsprinzip - die Hälfte (im Durchschnitt) von dem, was wir umdrehen, wird 0-> 1 sein, und die andere Hälfte wurde bereits umgedreht, sodass wir 1-> 0 erhalten.Wir bleiben immer noch bei ~ 50% 0s und 1s, nur die Verteilung der Bits mit einem 1-Wert ändert sich.
@Baldrickk - Deshalb habe ich gesagt, dass ich weiß, dass dies nicht der Fall ist.Mein Punkt war, dass die Antwort nicht von einem Bit auf mehrere Bits erweitert wurde, so dass ein Algorithmus nicht ausgeschlossen wurde, bei dem Änderungen von Bitflips tatsächlich korrelierten.Wahrscheinlich war ich jedoch übermäßig pedantisch.
@Bobson Ich habe meine [Antwort] (https://security.stackexchange.com/a/226118/86735) für mehrere Bitänderungen aktualisiert.Die Mathematik ist unter dem zufälligen Oracle-Modell einfach.
#2
+37
kelalaka
2020-02-19 19:01:17 UTC
view on stackexchange narkive permalink

TL: DR; In kryptografischen Hash-Funktionen; Die Hashes von zwei unterschiedlichen Nachrichten sollten statistisch unabhängig erscheinen. $ sup>


Mir ist klar, dass der Hash eine Einwegfunktion ist und dass der Änderungen am Hash sollen uns mitteilen, dass sich die ursprünglichen Daten geändert haben (dass sich der gesamte Hash selbst bei den geringsten Änderungen an den Daten ändert).

Lawinenkriterien stark> ist nicht nur einseitig, sondern auch das, was wir von guten kryptografischen Hash-Funktionen erwarten:

  • eine einzelne Bitänderung in Die Eingabe führt mit einer Wahrscheinlichkeit von 50% zu Änderungen in jedem der Ausgabebits.

  • Änderungen mehrerer Bits : Dies ist etwas schwierig, wenn wir Betrachten Sie die Archive der Hash-Funktionen, um eine Pseudozufallsfunktion gemäß dem zufälligen Orakelmodell zu modellieren. Dann können wir jede Änderung des Eingabebits im Durchschnitt mit 50% berücksichtigen, und das spielt keine Rolle, wie viel Bit geändert wird

    Man kann dies sehen, indem man ein Bit betrachtet und eine Münze wirft, wenn Head kommt Flip und wenn Schwanz kommt, drehen Sie nicht 50% des Flippens. Werfen Sie jetzt eine weitere Münze und machen Sie dasselbe. Das Ergebnis ist das gleiche (einfache Mathematik).

    Natürlich können wir das zufällige Orakelmodell nicht erreichen. Daher sind die Ausgangsbits nicht unabhängig voneinander. Sie scheinen so lange zu sein, wie man einen Unterscheidungsmerkmal finden kann, und das wäre ein kryptoanalytischer Angriff auf die Hash-Funktion. Sobald eine gute kryptografische Hash-Funktion gefunden wurde, wird sie in den Nachrichten angezeigt.

Der Nachweis, dass eine Hash-Funktion Lawinenkriterien hat, ist ein statistischer Prozess, den Sie testen müssen viele zufällige Eingabewerte. Nicht alle Eingaben und Bitkomplemente führen dazu, dass die Hälfte des Bits geändert wird, und dies ist nicht das erwartete Verhalten . Sie müssen auch zeigen, dass die Ausgabebits zufällig geändert werden.

Wenn diese Hash-Funktion nicht erfüllt ist, kann sie den Vorbildwiderstand, den Zweitvorbildwiderstand und den Kollisionswiderstand * sup> nicht erfüllen.

  • Vorbildwiderstand - Für im Wesentlichen alle vordefinierten Ausgaben ist es rechnerisch nicht möglich, eine Eingabe zu finden, die mit dieser Ausgabe hasht, dh ein Vorbild x ', so dass h (x') = y , wenn ein y angegeben wird, für das eine entsprechende Eingabe nicht bekannt ist.
  • 2. Vorbild Widerstand, schwache Kollision - Es ist rechnerisch nicht möglich, einen zweiten Eingang zu finden, der den gleichen Ausgang wie ein spezifizierter Eingang hat, dh x , um ein zweites Bild zu finden x '! = x , so dass h (x) = h (x') .
  • Kollisionsfestigkeit, starke Kollision - Es ist rechnerisch nicht möglich, zwei unterschiedliche Eingaben x , x ' zu finden, die auf dieselbe Ausgabe hashen, dh so, dass h (x) = h (x) ') .

Ein Ausfall kann zu Angriffen führen. Wenn dies erfolgreich ist, kann dies verheerende Folgen haben. Ein Beispiel; Angenommen, jemand findet eine zweite Nachricht zu Ihrer ursprünglichen Nachricht, die denselben Wert hat (oder den Hash der Linux-CD-ISO).

  Dies ist eine signierte Nachricht, die darstellt, dass die Zahlung 1,00 USD beträgt schöner TagIch zahle dir $ 1.000.000,00 einen schönen Tag  

Hoffentlich widersetzen sich sogar SHA-1 und MD5 diesem Angriff. Daher können Sie davon ausgehen, dass sich die Daten ändern, wenn sich der Hashwert ändert. Die Wahrscheinlichkeit, dass ein zufälliger Text denselben Hash mit Ihrem Wert hat, ist vernachlässigbar.

Aber gibt es eine Möglichkeit herauszufinden, inwieweit sich die Originaldaten geändert haben, wenn zwei Hashes unterschiedlich sind?

Hoffentlich nicht . Wenn es eine einzige Verzerrung gibt, die Informationen über die Änderungen enthält, die von cleveren Angreifern verwendet werden können.


* sup> Dies sind formale Definitionen, die aus dem wegweisenden Artikel von Rogaway und Shrimpton stammen. Grundlagen der kryptografischen Hash-Funktion: ... sup>

$ sup> Vielen Dank an FutureSecurity für die Vereinfachung sup>

Ist "Kollisionsresistenz" durch "Widerstand vor dem 2. Bild" impliziert oder verstehe ich falsch?
@Daniel Diese Definitionen stammen aus dem wegweisenden Artikel von Rogaway und Shrimpton [Grundlagen der kryptografischen Hash-Funktion] (https://web.cs.ucdavis.edu/~rogaway/papers/relates.pdf).Auf Seite 4 finden Sie eine einfache grafische Darstellung der Beziehungen.Kollisionsfestigkeit impliziert Widerstand vor dem 2. Bild.Wenn ein Angreifer nicht gegen das 2. Vorbild resistent ist, wählt er ein beliebiges m1 und berechnet ein zweites Vorbild m2, um eine Kollision zu erhalten.Beachten Sie, dass 2 => 1 besondere [Sorgfalt] erfordert (https://crypto.stackexchange.com/q/10602/18298).
#3
+30
Ilmari Karonen
2020-02-20 04:54:25 UTC
view on stackexchange narkive permalink

Wie die anderen Antworten bereits erwähnt haben, lautet die Antwort "Nein" für kryptografische Hash-Funktionen. Diese sind im Allgemeinen so konzipiert, dass sie sich so ähnlich wie eine vollkommen zufällige Funktion wie möglich verhalten, und jede erkennbare Ähnlichkeit in den für ähnliche Eingaben erzeugten Hash-Ausgaben würde es auch ermöglichen, den Hash von einer zufälligen Funktion zu unterscheiden. *

Jedoch gibt es andere andere Arten von Hash-Funktionen, wie z. B. lokalitätssensitive Hashes, für die die Antwort mindestens "Ja, manchmal" lauten kann.

Insbesondere weisen lokalitätsempfindliche Hashes typischerweise Eigenschaften auf, wie "zwei beliebige Eingaben, die sich gemäß einer Ähnlichkeitsmetrik um höchstens δ unterscheiden, mit der Wahrscheinlichkeit p > 0 haben Hashes, die sich um höchstens ε ( δ ) durch eine andere (möglicherweise dieselbe) Ähnlichkeitsmetrik unterscheiden. " Typischerweise kann die Abstandsmetrik für die Hashes so etwas wie Hamming-Abstand sein, während die entsprechende Metrik für die Eingaben z. Abstand bearbeiten. Die Auswahl einer geeigneten ortsabhängigen Hash-Funktion hängt hauptsächlich davon ab, an welcher bestimmten Entfernungsmetrik Sie interessiert sind.


*) Technisch gesehen erfordert die klassische Definition eines sicheren kryptografischen Hash nur Kollisionsbeständigkeit und erste und zweite Vorbildbeständigkeit. Ich sehe keinen offensichtlichen Weg, um zu beweisen, dass eine Hash-Funktion diese Eigenschaften nicht haben kann, während sie in gewisser Weise lokalitätsempfindlich ist, obwohl sie einige ziemlich signifikante Einschränkungen auferlegt. Insbesondere die Anzahl der Hash-Ausgaben innerhalb eines Abstands von ε ( δ ) von einer gegebenen Hash-Ausgabe H ( x ) müsste schneller wachsen als die Anzahl anderer Eingaben innerhalb des Abstands δ von der entsprechenden Eingabe x für alle vernünftigen Werte von δ , Andernfalls würde das einfache Testen einer Reihe ähnlicher Eingaben sehr wahrscheinlich zu einer Kollision führen. Auf jeden Fall sind mir keine ortsabhängigen Hash-Funktionen bekannt, die selbst dieser schwächeren Definition der kryptografischen Sicherheit entsprechen würden, und ich habe keine Ahnung, wie ein solcher Hash aussehen könnte, wenn er existiert. Sup>

#4
+17
schroeder
2020-02-19 16:54:26 UTC
view on stackexchange narkive permalink

Ich bin sicher, dass es einen Hash-Typ gibt, bei dem dies möglich sein könnte, aber der Sinn eines kryptografisch sicheren Hashs besteht darin, sicherzustellen, dass dies nicht geschieht. Man sollte nicht in der Lage sein, Vermutungen oder Schlussfolgerungen über Änderungen an der Nachricht aufgrund von Änderungen an der Ausgabe des Hashs zu ziehen.

Kryptografische Analysten messen dies am Avalanche-Effekt. Starke Hashes sollten große Änderungen an der Ausgabe vornehmen, selbst wenn kleine Änderungen an der Eingabe vorgenommen werden.

"Ich bin sicher, dass es einen Hash-Typ gibt, bei dem dies möglich sein könnte".Sicher!Dies existiert trivial.`base64 (Eingabe) .substring (0,10)` ist technisch eine Hash-Funktion.
@Cruncher Heck, es gab eine Zeit, in der die Standard-Hash-Funktionen (für Dinge wie Hash-Tabellen) für "string" Dinge wie "die ersten vier Bytes der Bytedarstellung des Strings nehmen und in int konvertieren" taten.Zumindest ist es ziemlich schnell: P.
@Cruncher technisch gesehen ist rot13 () eine Hash-Funktion.Ich gab dem OP den Vorteil des Zweifels.
@schroeder Da rot13 reversibel ist, bin ich mir nicht sicher, ob ich es als Hash-Funktion betrachten würde.Wir denken normalerweise, dass ein Hash für jede Eingabe dieselbe Größe hat, weshalb ich nicht einfach base64 ohne den Teilstring gesagt habe.Aber es ist trotzdem Semantik
@Cruncher gemäß der technischen Definition müssen Hashes nicht einseitig sein.Einweg-Hashes müssen Einweg-Hashes sein
@schroeder `Eine Hash-Funktion ist eine beliebige Funktion, mit der Daten beliebiger Größe auf Werte fester Größe abgebildet werden können.` Dies ist die erste Zeile im Wikipedia-Artikel für Hash-Funktion.Das Zuordnen von Daten beliebiger Größe zu Werten fester Größe ist * immer * eine Möglichkeit (Pigeonhole Principal)
@Cruncher und das ist eine Überverallgemeinerung von kryptografischen Hashes.Es gibt Hashes, die variable und beliebige Längen bereitstellen.Ausgaben mit fester Länge sind für einen Hash nicht erforderlich.Die meisten akzeptierten kryptografischen Hashes haben eine feste Länge.
@Cruncher [Fips 202] (https://dx.doi.org/10.6028/NIST.FIPS.202): * Die erweiterbare Ausgabefunktion SHAKE256 ist eine Funktion, die eine Bitfolge beliebiger Länge einer Zeichenfolge mit unendlich vielen Bits zuordnet *.Man kann immer noch davon ausgehen, dass sie in dem Sinne fixiert sind, dass die erste Ausgabe und die nächsten Ausgaben eine feste Größe haben, wenn wir SHAKE betrachten.Die Notwendigkeit ist RSA-PSS und dies erfordert eine nicht standardmäßige Hash-Funktion.Wenn XOFs zum Entwurfszeitpunkt verfügbar wären, wäre der Sicherheitsnachweis von RSA-PSS viel einfacher.
#5
+10
solumnant
2020-02-20 22:48:32 UTC
view on stackexchange narkive permalink

Ja, aber nur für Fuzzy-Hashes wie ssdeep https://ssdeep-project.github.io/ssdeep/index.html, die speziell zur Messung der Ähnlichkeit zwischen Dateien entwickelt wurden, und Hashes, die Decken Sie nur bestimmte Teile der Datei ab, die keine Änderungen enthalten, z. B. imphash https://www.fireeye.com/blog/threat-research/2014/01/tracking-malware-import-hashing.html. Es gibt andere Arten von Hashes, die in den Kommentaren zu der Frage erwähnt wurden, aber da ich mit ihnen, ihren Eigenschaften und ihrer Verwendung nicht vertraut bin, werde ich hier nicht darauf eingehen. Fühlen Sie sich frei, dieser Antwort etwas hinzuzufügen, wenn Sie andere Arten von Hashes haben, die ich nicht nur behandelt habe.

Außerhalb spezialisierter Hashes, die entweder darauf ausgelegt sind, Ähnlichkeiten zu verfolgen, oder die nicht die gesamte Eingabe abdecken Die Antwort wäre nein gemäß den Antworten von Kelalaka oder MechMK1 auf diesen Beitrag. Es ist möglich, dass meine beschriebenen Funktionen keine echten Hash-Funktionen sind, aber sie werden in meiner Community als Hash-Funktionen bezeichnet.

#6
+4
James Kirkby
2020-02-20 15:34:14 UTC
view on stackexchange narkive permalink

Eine starke Hash-Funktion sollte mit einer kleinen Änderung zu einem großen Unterschied im Ausgabe-Hash führen. Wenn Sie also den Unterschied zwischen zwei Werten überprüfen möchten, können Sie einen Hamming-Distanz-Algorithmus verwenden.

https://en.wikipedia.org/wiki/Hamming_distance

#7
+1
Graham
2020-02-21 17:16:55 UTC
view on stackexchange narkive permalink

Sie können, aber dann ist es keine reine Hash-Funktion.

Fehlerkorrekturcodes sind eine Art von Hash-Funktion, die nicht nur einige Änderungen an einer Nachricht zulässt erkannt werden, aber auch ermöglichen, dass diese Änderungen korrigiert werden. Änderungen können natürlich nur für einen gewissen Fehler korrigiert werden. Je größer der Fehlerkorrekturcode im Verhältnis zur Nachricht ist, desto mehr Änderungen können im Allgemeinen erkannt und korrigiert werden.

Fehlerkorrekturcodes sind für diese Fähigkeit zur Korrektur von Änderungen optimiert. Dies bedeutet jedoch, dass sie möglicherweise nicht optimal darin sind, Änderungen an einer Nachricht zu erkennen, bei denen die Änderung nicht korrigiert werden kann. Sie sind in erster Linie als Hash für Nachrichten gedacht, bei denen eine erneute Übertragung nicht einfach möglich ist und daher die Wiederherstellung der ursprünglichen Nachricht Priorität hat. Sie gehen auch davon aus, dass absichtliche Angriffe auf die Nachricht nicht stattfinden.

Kryptografische Hashes oder sogar weniger sichere Hashes wie CRC funktionieren in der Regel anders. Im Allgemeinen werden diese entweder in Situationen verwendet, in denen eine erneute Übertragung einer fehlerhaften Nachricht angefordert werden kann oder in denen das Risiko eines absichtlichen Angriffs besteht und fehlerhafte Nachrichten zuverlässig erkannt und zurückgewiesen werden müssen. Dies sind immer Einwegfunktionen, und der Grad, in dem sie "Einweg" sind, zeigt an, wie robust sie sind. Wie bereits in früheren Antworten erwähnt, liefert ein guter kryptografischer Hash keine Informationen über die ursprüngliche Nachricht.

"oder noch weniger sichere Hashes wie CRC funktionieren normalerweise anders (als ECC)" - nein.Ein CRC hat die gleiche Struktur wie ein Fehlerkorrekturcode.Normalerweise wird der Fehler selbst unter einer Einschränkung wie "Einzelbitfehler" nicht eindeutig identifiziert, aber es eignet sich sehr gut, um * eine * "Korrektur" durchzuführen und eine Nachricht zu finden, die mit der CRC übereinstimmt.
#8
  0
cmm
2020-02-22 21:03:11 UTC
view on stackexchange narkive permalink

Hash bedeutet nicht immer kryptografischer Hash

Sie können eine für den Zweck spezifische Hash-Funktion erstellen.

Ziehen Sie in Betracht, die Dateien byteweise zu vergleichen und den Hash für jede Differenz zu erhöhen. Fügen Sie den Längenunterschied hinzu. Es ist eine Hash-Funktion, die eine Einwegberechnung liefert, die sich direkt auf den Grad der Differenz bezieht.

Wenn Sie eine intelligentere Hash-Funktion wünschen, versuchen Sie "diff file1 file2 | wc -l".



Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 4.0-Lizenz, unter der er vertrieben wird.
Loading...