Merkles Meta-Verfahren

Methode zur Konstruktion von kryptographischen Hash-Funktionen

Merkles Meta-Verfahren (auch Merkle-Damgård-Konstruktion) ist eine Methode zur Konstruktion von kryptographischen Hash-Funktionen, die auf Arbeiten von Ralph Merkle und Ivan Damgård zurückgeht.

Gegeben ist eine Kompressionsfunktion , die eine Bit lange Eingabe auf eine Bit lange Ausgabe abbildet. Sie ist kollisionssicher, das heißt, es ist nicht mit realistischem Aufwand möglich, zwei verschiedene Eingaben zu finden, die auf die gleiche Ausgabe abgebildet werden. Durch die Anwendung von Merkles Meta-Verfahren ergibt sich daraus eine kollisionssichere Hash-Funktion , die beliebig lange Nachrichten auf einen Hashwert von Bit abbildet.

Vorgehensweise

Bearbeiten
 
Aus den Nachrichtenblöcken wird durch wiederholte Anwendung der Kompressionsfunktion der Hashwert erzeugt

Die Nachricht   wird zunächst mit einem Padding-Verfahren zu   erweitert, so dass die Länge von   ein Vielfaches der Blockgröße   ist. Dann wird   in   Blöcke der Länge   aufgeteilt:

  mit  .

Die Kompressionsfunktion   wird iterativ auf die   Bit lange Ausgabe der vorherigen Iteration und den nächsten Block   der erweiterten Nachricht angewandt, bis diese ganz verarbeitet ist. Bei der ersten Iteration besteht die Eingabe aus einem   Bit langen konstanten Initialisierungsvektor   und dem ersten Nachrichtenblock  .

 .

Der Hash-Wert wird dann aus der letzten Kompressionsausgabe durch eine Finalisierungsfunktion berechnet:  . Diese ist häufig die Identität oder eine Trunkierung.

 
Davies-Meyer-Kompressionsfunktion
 
Matyas–Meyer–Oseas-Kompressionsfunktion
 
Miyaguchi-Preneel-Kompressionsfunktion

Die Kompressionsfunktion wird oft aus einer Blockverschlüsselung konstruiert, wofür es hauptsächlich zwei Möglichkeiten gibt. Eine ist die Davies-Meyer-Kompressionsfunktion:  . Sie nutzt den Nachrichtenblock   als Schlüssel, um damit den Verkettungswert   zu verschlüsseln. Danach wird noch der so berechnete Schlüsseltext mit dem Klartext verknüpft, z. B. durch bitweises XOR. Dadurch wird die Eigenschaft einer Blockchiffre aufgehoben, den Klartext bijektiv auf den Schlüsseltext abzubilden, und die Abbildung von   auf   ähnelt wesentlich mehr einer Zufallsfunktion. Sonst wäre die Kompressionsfunktion auch nicht kollisionssicher, denn ein Angreifer könnte   vorgeben und mit verschiedenen   entschlüsseln.

Die zweite ist die Matyas–Meyer–Oseas-Kompressionsfunktion:   mit   oder  . Sie verschlüsselt den Nachrichtenblock mit dem Verkettungswert als Schlüssel. Auch hier werden Klar- und Schlüsseltext anschließend verknüpft. Die Funktion   erweitert oder komprimiert   zur Anpassung an die gegebene Schlüssellänge. Als Modifikation von Matyas–Meyer–Oseas gibt es noch die Miyaguchi-Preneel-Kompressionsfunktion, die sich nur dadurch unterscheidet, dass auch   mit dem Schlüsseltext verknüpft wird:  . Das ist vor allem dann von Nutzen, wenn die Funktion   den Verkettungswert komprimieren muss, denn so geht dessen gesamter Informationsgehalt in   ein.

Damit die Kollisionssicherheit der Kompressionsfunktion sich beweisbar auf die Hashfunktion überträgt, muss das Paddingverfahren bestimmte Bedingungen erfüllen. Folgende Bedingungen sind dafür hinreichend:[1]

  •   ist ein Anfangsstück von  , d. h., die Nachrichten werden nicht verändert, nur mit einem Endstück erweitert.
  • Zwei Nachrichten der gleichen Länge werden mit gleich langen Endstücken erweitert.
  • Zwei verschieden lange Nachrichten werden unterschiedlich erweitert, so dass sie sich im letzten Block, der in die letzte Kompressionsstufe eingegeben wird, unterscheiden.

Typischerweise wird beim Padden eine Codierung der Bitlänge   an die Nachricht angehängt, und dazwischen werden ggfs. Bits mit dem Wert 0 eingefügt, damit   ein Vielfaches der Blockgröße   ist:

 

Schwächen

Bearbeiten

Eine Schwäche ist ein möglicher Erweiterungs-Angriff (Extension-Attack): Wenn die Finalisierungsfunktion umkehrbar ist, dann kann man aus dem Hashwert   einer unbekannten Nachricht   leicht den Hashwert   einer Nachricht bestimmen, die aus der wie oben erweiterten Nachricht durch Anfügen einer Erweiterung   hervorgeht. Man kann also Hashwerte von Nachrichten bestimmen, die   als Anfangsstück haben, auch wenn man   nicht kennt.[2] Da ein Zufallsorakel diese Eigenschaft nicht hat, können sich daraus Angriffe auf Verfahren ergeben, die nur im Random-Oracle-Modell einen Sicherheitsbeweis haben.[3] Daraus folgt auch: wenn man einmal eine Kollision zweier Nachrichten mit gleicher Blockanzahl   gefunden hat, kann man durch Erweiterung leicht weitere Kollisionen bestimmen.

Mehrfachkollisionen zu finden, also mehrere Nachrichten, die alle den gleichen Hashwert haben, erfordert nur wenig mehr Aufwand als das Bestimmen einer einzelnen Kollision.[4]

Ein Herding-Angriff, also zu einem selbst gewählten Hashwert z und einem gegebenen Anfangsstück   einer Nachricht ein passendes Endstück zu finden, so dass die gesamte Nachricht zu z hasht, d. h., ein   mit   zu finden, erfordert zwar mehr Aufwand als das Finden einer Kollision, aber wesentlich weniger, als es für ein Zufallsorakel als Hashfunktion   der Fall sein sollte.[5]

Ein Angriff zur Bestimmung eines zweiten Urbildes (second preimage attack), bei dem man zu einer gegebenen Nachricht   eine zweite   mit demselben Hashwert   sucht, ist bei einer Nachricht der Länge von   Blöcken mit dem Zeitaufwand   möglich, und damit bei langen Nachrichten erheblich schneller als durch systematisches Probieren (brute force), was etwa   Schritte erfordert.[6]

Verbesserungen

Bearbeiten

Zur Überwindung dieser Schwächen hat Stefan Lucks die wide-pipe-hash-Konstruktion vorgeschlagen:[7] Um einen Hashwert von   Bit Länge zu berechnen, verwendet man eine Kompressionsfunktion  , deren Ausgabe länger als   ist, typischerweise doppelt so lang.   komprimiert also   Bit aus der vorherigen Iteration und einen   Bit langen Nachrichtenblock zu einer Ausgabe von   Bit. Nach der letzten Iteration wird die Ausgabe durch eine weitere Kompressionsfunktion von   auf   Bit verkürzt, im einfachsten Fall durch Trunkierung. Beispiele: SHA-512/256, Grøstl.

 
fast wide pipe hash

Nandi und Paul haben gezeigt, dass diese Konstruktion etwa doppelt so schnell gemacht werden kann (fast wide pipe hash), indem man nur   Bit aus den vorhergehenden Kompressionen in die nächste Kompression eingibt, zusammen mit einem   Bit langen Nachrichtenblock  . Die andere Hälfte der  -Kompressionsausgabe wird mit der darauf folgenden Eingabe XOR-verknüpft:[8]

 

In der letzten Stufe wird die Ausgabe der vorletzten komplett verarbeitet, und der Nachrichtenblock   ist dafür nur   Bit breit (falls man hier nicht eine andere Kompressionsfunktion mit größerer Eingabe verwendet):

 

  und   bedeuten dabei die erste bzw. die zweite Hälfte der Bitkette  .

Neben der wide-pipe-hash-Konstruktion gilt auch die HAIFA-Konstruktion als eine Weiterentwicklung des Merkle-Damgård Verfahrens. Ein Beispiel dafür ist BLAKE.

Einzelnachweise

Bearbeiten
  1. S. Goldwasser, M. Bellare: "Lecture Notes on Cryptography" (Memento des Originals vom 20. Mai 2012 auf WebCite)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/cseweb.ucsd.edu. Summer course on cryptography, MIT, 1996–2001.
  2. Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton: Salvaging Merkle–Damgård for Practical Applications. Preliminary version in Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, S. 371–388.
  3. J.S. Coron, Y. Dodis, C. Malinaud, P. Puniya: Merkle–Damgård Revisited: How to Construct a Hash Function. Advances in Cryptology – CRYPTO '05 Proceedings, Lecture Notes in Computer Science, Vol. 3621, Springer-Verlag, 2005, S. 21–39.
  4. Antoine Joux: Multicollisions in iterated hash functions. Application to cascaded construction. In: Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, M. Franklin, ed, Springer-Verlag, 2004, S. 306–316.
  5. John Kelsey, Tadayoshi Kohno: Herding Hash Functions and the Nostradamus Attack In Eurocrypt 2006, Lecture Notes in Computer Science, Vol. 4004, S. 183–200.
  6. John Kelsey, Bruce Schneier: Second preimages on n-bit hash functions for much less than 2n work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005; [1].
  7. S. Lucks: Design Principles for Iterated Hash Functions. In: Cryptology ePrint Archive, Report 2004/253, 2004.
  8. Mridul Nandi, Souradyuti Paul: Speeding Up the Widepipe: Secure and Fast Hashing. In Guang Gong and Kishan Gupta, editor, Indocrypt 2010, Springer, 2010.

Literatur

Bearbeiten
  • Hans Delfs, Helmut Knebl: Introduction to Cryptography. Springer 2002, ISBN 3-540-42278-1, S. 40.