Zusammenfassung

  • RFC 1186 meldete für MD4 1.450.000 Byte pro Sekunde auf einem Sun SPARC, ungefähr 70.000 auf einem DEC MicroVAX II und ungefähr 32.000 auf einem 80286 mit 20 MHz. Der Aufwand für eine Kollision blieb eine Vermutung.
  • RFC 1320 ersetzte das Dokument 1992 mit portablerem Referenzcode. RFC 6150 stufte MD4 2011 nach dokumentierten Angriffen als Historic ein.

Ein Sun SPARC saß auf dem Prüfstand. Der Angreifer, der die Abkürzung im Algorithmus suchen würde, fehlte noch. In RFC 1186 vom Oktober 1990 beschrieb Ronald Rivest MD4 als Verfahren, das Nachrichten beliebiger Länge zu einem 128-Bit-Digest verdichtet. Eine große Datei sollte sich damit unter anderem für eine RSA-Signatur vorbereiten lassen. Die Laufzeit dieses Vorgangs konnte Rivest messen.

Auf einem Sun SPARC waren es 1.450.000 Byte pro Sekunde, auf einem DEC MicroVAX II ungefähr 70.000, auf einem 20-MHz-80286 ungefähr 32.000. Große Substitutionstabellen brauchte das Verfahren laut RFC nicht. Der Anhang enthielt Schnittstelle, C-Implementierung, Testtreiber und Beispielausgabe. Wortbreite, 512-Bit-Blöcke, Auffüllung und die codierte ursprüngliche Nachrichtenlänge waren festgelegt. Wer programmieren oder prüfen wollte, hatte einen präzisen Gegenstand.

Der zweite Wert auf dem Papier war keine Stoppuhrzeit. RFC 1186 vermutete ungefähr 2^64 Operationen, um zwei verschiedene Nachrichten mit demselben Digest zu finden; für eine Nachricht zu einem vorgegebenen Digest nannte es 2^128. Rivest bezeichnete die Schätzung ausdrücklich als Vermutung und forderte mehr Analyse. Ein schneller Durchlauf sagt, was die Maschine kann. Er sagt nichts darüber, welchen Trick ein Gegner morgen findet.

MD4 ging zur Prüfung und möglichen Standardisierung in die Public Domain; der RFC selbst war informativ. Dieser Schritt machte gemeinsame Implementierungen und gemeinsame Angriffsversuche möglich. Im April 1992 ersetzte RFC 1320 den frühen Text. Als Hauptänderung bezeichnete er eine portablere Referenzimplementierung. Dazu kam eine Algorithmuskennung für OSI-Anwendungen. Die Hürde für eine Übernahme sank, während die kryptografische Hypothese weiter geprüft wurde.

Der Befund im RFC 6150 vom März 2011 war deutlich. Das Dokument verzeichnete einen praktischen Kollisionsangriff von 1996 mit einem Aufwand von etwa 2^20 MD4-Berechnungen und ein Ergebnis von 2004 mit etwa 2^8. Die ursprüngliche Schätzung von 2^64 hielt diesem Vergleich nicht stand. Die IETF verschob RFC 1320 in den Status Historic und empfahl vorhandene Alternativen wie SHA-256.

Die Ausmusterung war keine Aufräumaktion mit einem einzigen Schalter. RFC 6150 nannte verbliebene Nutzungen, darunter einen Microsoft-Kompatibilitätspfad, und beschrieb den langen Abzug bereits eingesetzter Kryptografie. Der Standardstatus lässt sich an einem Datum ändern. Bibliotheken, Protokolle und Gegenstellen tragen die alte Entscheidung weiter, bis jemand sie tatsächlich ersetzt.

Quellen