Merkle–Damgård-Konstruktion

Die Merkle–Damgård-Konstruktion, kurz (MD-Konstruktion) ist Basis fast aller moderner kryptografischer Hash-Funktionen. Der Name geht auf die Kryptologen Ralph Merkle und Ivan Damgård zurück, die dieses Konstrukt erfunden haben.

Eine Merkle–Damgård-Konstruktionv erarbeitet die Klartextnachrichten in Blöcken gleicher und festgelegter Länge. Ggf. muss der Klartext mittels sogenanntem Padding mit einem festgelegten Bitmuster (z. B. Nullbytes) aufgefüllt werden, um dem gerecht zu werden.

Ausgehend von einem Initialisierungvektor (IV), mit dem der Zustand zu Anfang gefüllt wird, werden nach festgelegten Regeln die Klartextnachrichtenblöcke auf einen internen Zustand angewendet. Dieser Zustand ändert sich mit mit der Verarbeitung jedes weiteren Blocks. Die Zustandmanipulation pro Block geschieht in einer festgelegten Anzahl von "Runden", also Wiederholungen, in denen eine gewisse Anzahl von Rechenoperationen oder logischen Operationen angewendet werden. Diese sind nach Performance und Sicherheits-Gesichtspunkten optimiert.

Sind alle Klartextnachrichtenblöcke verarbeitet, kann der interne Zustand als Hash-Wert abgerufen werden. Manchmal ist davor aus designtechnischen Gründen noch eine Finalisierung nötig.

MD-Konstruktionen sind grundsätzlich anfällig für "Verlängerungsangriffe", wenn der gesamte interne Zustand als Hash-Wert ausgegeben wird, was meist der Fall ist. So kann ein Angreifer den Zustand der MD-Funktion für eine Verlängerung der Nachricht reinitialisieren und weiterrechnen und erhält so einen gültigen Hash für eine verlängerte Nachricht, obwohl ihm die Ursprungsnachricht gänzlich unbekannt ist.

Merkle–Damgård-Konstruktionen werden z. B. angewendet in: