Warum enthält die Auffüllung in Merkle-Damgård-Hash-Funktionen wie MD5 die Nachrichtenlänge?

  • Ich verstehe die Notwendigkeit des Auffüllens in MD5. Aber warum hängen wir die Nachrichtenlänge an die Auffüllung an?

    Ich habe gehört, dass es den Hash verstärkt, aber wie?

    Bitte geben Sie ein an Beispiel, wenn möglich und wie es für dieses Zitat gilt:

    Durch die Einbeziehung des Längenblocks werden alle Nachrichten effektiv verschlüsselt, so dass keine | das Ende einer anderen codierten Eingabe.

    Warum ist eine Nachricht, die das Ende einer anderen Nachricht ist, fehlerhaft (falls vorhanden)?

    03 September 2014
    CodesInChaosgrieve
3 answers
  • MD5 verwendet wie andere Hash-Funktionen die Merkle-Damgard Konstruktion. Sie nehmen die Nachricht und teilen sie in Blöcke mit fester Größe auf. Sie beginnen mit einem Initialisierungsvektor (IV), den Sie zusammen mit dem ersten Block in eine Kompressionsfunktion einspeisen. Nehmen Sie die Ausgabe (sie hat die gleiche Länge wie die IV) und fügt sie zusammen mit dem zweiten Nachrichtenblock der Komprimierungsfunktion hinzu usw.

    Rufen Sie die Komprimierungsfunktion auf $ c $ und die Hash-Funktion "raw" (unpadded) $ h $, wir haben $$ \ begin {align *} h (ZABCD) & amp; = c (h (ZABC), D) \\ & amp; = c ( c (h (ZAB), C), D) / c = c (c (c (h (ZA), B), C), D) \ c = c (c (c (c (h (Z), A), B), C), D) \ c = c (c (c (c (c (I, Z)), A), B), C), D) \ end {ausrichten *} $$ mit einem festen Initialisierungsvektor $ I $ (jeder Buchstabe steht für einen Block).

    Verschiedene Hash-Funktionen verwenden unterschiedliche Komprimierungsfunktionen. Das Ziel ist zu beweisen, dass wir eine Kollision in der Hash-Funktion nur finden können, wenn wir eine Kollision in der Komprimierungsfunktion finden können (der nächste Schritt wäre zu argumentieren, dass das Finden einer Kollision in der Komprimierungsfunktion äußerst schwierig ist).

    Wie würde dieses Argument funktionieren? Wir könnten unser Ziel folgendermaßen formulieren:

    Wenn Sie mir zwei Meldungen geben, die eine Kollision in der Hash-Funktion verursachen, kann ich zwei Eingangspaare für die Komprimierungsfunktion finden das verursacht eine Kollision.

    So erreiche ich dieses Ziel: Ich nehme die beiden Nachrichten, die Sie mir geben, und spalte sie auf Blöcke. Dann finde ich den Block ganz rechts, den die beiden Nachrichten nicht gemeinsam haben. Wenn beispielsweise die erste Nachricht (nach dem Auffüllen) Blöcke $ ZABCD $ und die zweite Blöcke $ XKCD $ enthält, unterscheidet sich der dritte Block von rechts ($ B $ vs. $ K $).

    Da $ h (ZABCD) = h (XKCD) $ ist, überprüfe ich, ob $ h (ZABC) = h (XKC) $ ist. Wenn nicht, habe ich meine Kollision:

    $$ h (ZABCD) = c (h (ZABC), D) = c (h (XKC), D) = h ( XKCD). $$

    11 December 2011
    Otto
  • Die Merkle-Damgård-Hash-Konstruktion Füllt die Nachricht $ M $ normalerweise mit einem auf 1 gesetzten Bit, einer minimalen Anzahl von Bits, die auf 0 gesetzt ist, und der Darstellung der Länge der Nachricht binär über eine festgelegte Anzahl von Bits auf. Die aufgefüllte Nachricht wird dann aus einer Anzahl von Blöcken $ B_i $ gebildet. Der Hash wird durch wiederholtes Anwenden einer Kompressionsfunktion $ C $: $ (X, B) \ rightarrow C (X, B) $ berechnet, wodurch $$ H (M) = C (C (.. C (C (IV, B_0), B_1) .. B_ {k-2}), B_ {k-1}) $$

    Die Frage ist: Warum mit der Länge auffüllen? Ist das nicht mit den zuvor hinzugefügten Bits überflüssig?

    Die Länge in der Auffüllung ermöglicht einen einfachen Sicherheitsbeweis : volle Hashkollision zwischen zwei Bekannte eindeutige Meldungen ermöglichen das Anzeigen einer Kollision in der zugrunde liegenden Komprimierungsfunktion $ C $, dh $ X, B, X ', B' $ mit $ C (X, B) = C (X ', B') $ und $ (X, B) \ ne (X ', B') $.

    Die Beweisskizze lautet:

    1. Wenn die verschiedenen kollidierenden Nachrichten eine unterschiedliche Länge haben, tritt im letzten Block eine Kollision in $ C $ auf: Wir wissen, dass $ B_ {k-1}, B '_ {k-1} $ verschieden sind, da sie enthalten die Länge;
    2. Wenn die verschiedenen kollidierenden Nachrichten dieselbe Länge haben, gibt es einen gut definierten Block ganz rechts, in dem sich die aufgefüllten Nachrichten unterscheiden und wenn in $ C $ nach einer Kollision gesucht wird Rechts von der aufgefüllten Nachricht bis zu diesem Block zeigen wir eine Kollision.

    Ohne die Länge in der Auffüllung können wir immer noch haben ein Sicherheitsbeweis, aber mit einer stärkeren Hypothese zu $ ​​C $ : Eine vollständige Hashkollision zwischen zwei bekannten unterschiedlichen Meldungen ermöglicht entweder eine Kollision in $ C $ wie oben oder ein Vorbild für die $ IV $ -Konstante, die in der Definition des Hashes angegeben ist, dh $ X, B $ mit $ C (X, B) = IV $. Der Beweis ist komplexer: Wir müssen Fall 1 unterteilen, je nachdem, ob die Nachrichten die gleiche aufgefüllte Länge haben

    24 August 2015
    Justin Cave
  • Es gibt eine schöne Charakterisierung für die kollisionserhaltende Polsterungsregel einer beliebigen Merkle-Damgård-Konstruktion: Die Polsterungsregel sollte ohne Suffix sein. Weitere Informationen finden Sie in der Veröffentlichung von Charakterisierung der Auffüllregeln von MD-Hash-Funktionen unter Beibehaltung der Kollisionssicherheit .

    Die Länge der Nachricht ist, wie sich herausstellt, die einfachste Form der Auffüllung, die kein Suffix enthält. Der Proof in der Zeitung ist in sich geschlossen und sehr leicht zu verstehen, daher stelle ich die Skizze des Proofs nicht vor.

    13 December 2011
    JeremyBoris Horvat