Merkle-Damgard Konstruktion
In der Kryptographie ist die Merkle-Damgård-Konstruktion oder die Merkle-Damgård-Hash-Funktion eine Methode zum Aufbau kollisionsresistenter kryptographischer Hash-Funktionen aus kollisionsresistenten Einwegkompressionsfunktionen. Diese Konstruktion wurde beim Entwurf vieler gängiger Hash-Algorithmen wie MD5, SHA1 und SHA2 verwendet.
Die Merkle-Damgård Konstruktion wurde in Ralph Merkle’s Ph.D. Diplomarbeit 1979. Ralph Merkle und Ivan Damgård bewiesen unabhängig voneinander, dass die Struktur solide ist: wenn also ein geeignetes Padding-Schema verwendet wird und die Kompressionsfunktion kollisionsresistent ist, dann ist die Hash-Funktion auch kollisionsresistent.
Die Merkle-Damgård-Hash-Funktion wendet zuerst eine MD-konforme Füllfunktion an, um einen Eingang zu erzeugen, dessen Größe ein Vielfaches einer festen Zahl ist (z. B. 512 oder 1024), da Komprimierungsfunktionen Eingaben beliebiger Größe nicht verarbeiten können. Die Hash-Funktion zerlegt dann das Ergebnis in Blöcke fester Größe und verarbeitet sie einzeln mit der Komprimierungsfunktion, wobei jedes Mal ein Block der Eingabe mit der Ausgabe der vorherigen Runde kombiniert wird.
- Multi-Kollisionen (viele Nachrichten mit dem gleichen Hash) können mit nur ein wenig mehr Arbeit als Kollisionen gefunden werden.
- Herding Angriff (auch bekannt als «Nostradamus-Angriff») der die kaskadierte Konstruktion für Multi-Kollisionen-Entdeckung (ähnlich wie oben) mit Kollisionen kombiniert, die für ein gegebenes Präfix gefunden wurden (Kollisionen mit ausgewählten Präfixen). Dies ermöglicht die Konstruktion hochspezifischer kollidierender Dokumente und kann für mehr Arbeit als das Auffinden einer Kollision durchgeführt werden, aber viel weniger, als dies für ein zufälliges Orakel zu erwarten wäre.
- Längenerweiterung: Wenn der Hash H (X) einer unbekannten Eingabe X gegeben ist, ist es leicht, den Wert von H zu finden (pad (X) || Y), wobei die Unterlage die Füllfunktion des Hash ist. Das heißt, es ist möglich, Hashwerte von Eingaben zu finden, die mit X in Beziehung stehen, obwohl X unbekannt bleibt. Length Extension Attack wurde tatsächlich verwendet, um eine Reihe von kommerziellen Web-Nachrichtenauthentifizierungsschemas anzugreifen, wie eines, das von Flickr verwendet wird.
Padding
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:
- m ist ein Anfangsstück von M, 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 |M| ein Vielfaches der Blockgröße ist:
- M = m || 0^k || |m|
Beispiel für das Padding der Länge
Um die Nachricht der Komprimierungsfunktion zuführen zu können, muss der letzte Block mit konstanten Daten (im Allgemeinen mit Nullen) zu einem vollständigen Block aufgefüllt werden.
Angenommen, die zu haschende Nachricht lautet „HashInput“ und die Blockgröße der Komprimierungsfunktion beträgt 8 Byte (64 Bit). Wir bekommen also zwei Blöcke, die so aussehen: Aber das ist nicht genug, da dies bedeuten würde, dass verschiedene Nachrichten, die mit denselben Daten beginnen und durch null oder mehr Bytes von den Daten der Auffüllkonstanten enden, in die Reduktionsfunktion unter Verwendung genau der gleichen Blöcke eingespeist werden, wobei dieselbe endgültige Hashsumme erzeugt wird.
In unserem Beispiel würde zum Beispiel die modifizierte Nachricht „HashInput00“ dieselben Blöcke erzeugen wie die ursprüngliche Nachricht „HashInput“. Um dies zu verhindern, muss das erste Bit der aufgefüllten Konstanten geändert werden. Da die konstante Auffüllung im Allgemeinen aus Nullen besteht, wird das erste Füllbit zwingend in „1“ geändert.
In unserem Beispiel erhalten wir so etwas: Um den Hash noch weiter zu härten, kann die Länge der Nachricht in einem zusätzlichen Block hinzugefügt werden.
In unserem Beispiel würden wir also drei Blöcke erhalten: Um Mehrdeutigkeiten zu vermeiden, muss der Nachrichtenlängenwert selbst gegen Angriffe mit Längenverlängerung resistent sein. Die häufigsten Implementierungen verwenden eine feste Bitgröße (im Allgemeinen 64 oder 128 Bits in modernen Algorithmen) und eine feste Position am Ende des letzten Blocks zum Codieren des Nachrichtenlängenwerts.
Nun, das ist ein wenig verschwenderisch, da es bedeutet, einen vollen zusätzlichen Block für den Längenwert zu hashen. Es gibt also eine leichte Geschwindigkeitsoptimierung, die die meisten Hash-Algorithmen verwenden. Wenn genug Platz unter den Nullen ist, die bis zum letzten Block aufgefüllt sind, kann stattdessen der Längenwert aufgefüllt werden.