Merkle-Damgard-Konstruktion

aus SecuPedia, der Plattform für Sicherheits-Informationen

Anzeige
Wechseln zu: Navigation, Suche

Die Merkle-Damgård-Konstruktion, Grundkonstruktion der meisten heute gebräuchlichen Krypto-Hash-Funktionen geht unabhängig voneinander auf die beiden Forscher Ralph Merkle und Ivan Damgård zurück. Passend zur ersten populären Merkle-Damgård-Hash-Funktion „Message Digest“ MD-4 sind die Initialen der beiden Erfindernamen „MD“.

Funktion

Bei der MD-Konstruktion wird die zu hashende Nachricht m in einzelne, gleich lange Blöcke m1, m2, ... mn unterteilt; dabei wird der letzte Block mittels Padding aufgefüllt. Die genaue Blocklänge und die Padding-Vorschrift sind Konstruktionsparameter der Hashfunktion. Diese einzelnen Nachrichtenblöcke werden nun mit einer Kompressionsfunktion f der Reihe nach abgearbeitet, so wie Pac-Man im gleichnamigen Videospiel die Punkte entlang seines Weges auffrisst. Die „Pac-Man-Funktion“ f ist dabei so definiert, dass sie einen internen Zustand xi–1 abhängig vom gerade behandelten Nachrichtenblock mi in den Nachfolgezustand xi abbildet, das heißt xi = f (xi–1 ,mi). Der Initialzustand x0 und ganz besonders der Aufbau von f sind wiederum Konstruktionsparameter, in denen sich die einzelnen MD-Hashfunktionen unterscheiden. Der ausgegebene Hashwert ist der interne Zustand nach dem letzten Nachrichtenblock: xn = f(f(...f(f(x0,mi),m2)...),mn–1),mn).


Angreifbarkeit

Die MD-Konstruktion ist grundsätzlich anfällig gegen sogenannte „Verlängerungsangriffe“: Jeder, der den MD-Hashwert x zu einer bestimmten Nachricht m kennt, kann, selbst wenn ihm Teile dieser Nachricht unbekannt sind, den korrekten Hashwert für die um ein frei gewähltes Endstück e verlängerte Nachricht m||e errechnen. Dazu genügt es, mit x als internem Zwischenzustand den MD-Hash über e einfach weiterzurechnen. Dies ist einer der Gründe, warum die „Keyed Hash Message Authentication Code (HMAC)“-Konstruktion zur Berechnung einer schlüsselabhängigen Integritäts-Prüfsumme zwei geschachtelte Aufrufe der Hashfunktion beinhaltet.

Quelle: Hans-Joachim Knobloch (Secorvo Security Consulting, Karlsruhe): „Schwamm drüber – Funktionsweise von SHA-3 (Keccak)“ in kes – Die Zeitschrift für Informationssicherheit“ 1/2013, S. 10 ff


Siehe übergeordnete Stichworte


Siehe auch



Diese Seite wurde zuletzt am 28. Februar 2013 um 15:17 Uhr von Peter Hohl geändert. Basierend auf der Arbeit von Oliver Wege.

Anzeigen