MD4 - MD4

MD4
Allgemein
Designer Ronald Rivest
Erstmals veröffentlicht Oktober 1990
Serie MD2 , MD4, MD5 , MD6
Verschlüsselungsdetail
Digest-Größen 128 Bit
Blockgrößen 512 Bit
Runden 3
Beste öffentliche Kryptoanalyse
Ein 2007 veröffentlichter Kollisionsangriff kann Kollisionen für vollständige MD4 in weniger als 2 Hash-Operationen finden.

Der MD4 Message-Digest-Algorithmus ist eine kryptografische Hash-Funktion, die 1990 von Ronald Rivest entwickelt wurde. Die Digest-Länge beträgt 128 Bit. Der Algorithmus hat spätere Designs beeinflusst, wie zum Beispiel die MD5- , SHA-1- und RIPEMD- Algorithmen. Der Initialismus "MD" steht für "Message Digest".

Image
Eine MD4-Operation: MD4 besteht aus 48 dieser Operationen, gruppiert in drei Runden von 16 Operationen. F eine nichtlineare Funktion ist; in jeder Runde wird eine Funktion verwendet. M i bezeichnet einen 32-Bit-Block der Nachrichteneingabe, und K i bezeichnet eine 32-Bit-Konstante, die für jede Runde unterschiedlich ist.

Die Sicherheit von MD4 wurde stark kompromittiert. Der erste vollständige Kollisionsangriff gegen MD4 wurde 1995 veröffentlicht und seitdem wurden mehrere neuere Angriffe veröffentlicht. Ab 2007 kann ein Angriff Kollisionen in weniger als 2 MD4-Hash-Operationen erzeugen. Es existiert auch ein theoretischer Urbildangriff .

Eine Variante von MD4 wird im ed2k-URI-Schema verwendet , um eine eindeutige Kennung für eine Datei in den beliebten eDonkey2000 / eMule P2P-Netzwerken bereitzustellen. MD4 wurde auch vom rsync- Protokoll verwendet (vor Version 3.0.0.)

MD4 wird verwendet, um NTLM- Kennwort-abgeleitete Schlüsselauszüge unter Microsoft Windows NT, XP, Vista, 7, 8 und 10 zu berechnen .

Sicherheit

Schwächen in MD4 wurden von Den Boer und Bosselaers in einem 1991 veröffentlichten Papier aufgezeigt. Der erste vollständige MD4- Kollisionsangriff wurde 1995 von Hans Dobbertin gefunden , der damals nur Sekunden dauerte. Im August 2004 haben Wang et al. fanden neben Angriffen auf spätere Hash-Funktionsdesigns in der MD4/MD5/SHA-1/RIPEMD-Familie einen sehr effizienten Kollisionsangriff. Dieses Ergebnis wurde später von Sasaki et al. verbessert, und das Erzeugen einer Kollision ist jetzt so billig wie das Verifizieren (wenige Mikrosekunden).

2008 wurde die Urbildresistenz von MD4 auch von Gaëtan Leurent mit einem 2 102 Angriff gebrochen . 2010 veröffentlichten Guo et al. einen 2 99,7- Angriff.

Im Jahr 2011 stellte RFC 6150 fest, dass RFC 1320 (MD4) historisch (veraltet) ist.

MD4-Hashes

Die 128-Bit (16-Byte) MD4-Hashes (auch als Message Digests bezeichnet ) werden typischerweise als 32-stellige Hexadezimalzahlen dargestellt. Im Folgenden wird eine 43-Byte- ASCII- Eingabe und der entsprechende MD4-Hash gezeigt: 

MD4("The quick brown fox jumps over the lazy dog")
= 1bee69a46ba811185c194762abaeae90

Selbst eine kleine Änderung in der Nachricht wird (mit überwältigender Wahrscheinlichkeit) Ergebnis in einem völlig anderen Hash, zB Wechsel dzu c: 

MD4("The quick brown fox jumps over the lazy cog")
= b86e130ce7028da59e672d56ad0113df

Der Hash des Strings der Länge Null ist: 

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

MD4-Testvektoren

Die folgenden Testvektoren sind in RFC 1320 (The MD4 Message-Digest Algorithm) definiert. 

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536

MD4-Kollisionsbeispiel

Lassen: 

 k1 = 839c7a4d7a92cb5678a5d5b9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318edd45e51fe39708bf9427e9c3e8b9
 k2 = 839c7a4d7a92cbd678a5d529eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318edc45e51fe39708bf9427e9c3e8b9

k1 ≠ k2, aber MD4(k1) = MD4(k2) = 4d7e6a1defa93d2dde05b45d864c429b

Beachten Sie, dass zwei Hex-Ziffern von k1 und k2 ein Byte des Eingabestrings definieren, dessen Länge 64 Byte beträgt.

Siehe auch

Verweise

  • Bert den Boer, Antoon Bosselaers: Ein Angriff auf die letzten beiden Runden von MD4. Krypto 1991: 194–203
  • Hans Dobbertin: Kryptoanalyse von MD4. Schnelle Softwareverschlüsselung 1996: 53–69
  • Hans Dobbertin, 1998. Kryptoanalyse von MD4. J. Kryptologie 11(4): 253–271
  • Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu: Kryptoanalyse der Hashfunktionen MD4 und RIPEMD. Eurocrypt 2005: 1–18
  • Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro: Neuer Nachrichtenunterschied für MD4. Schnelle Softwareverschlüsselung 2007: 329–348

Externe Links

  • RFC  1320 - Beschreibung von MD4 von Ron Rivest
  • RFC  6150 - MD4 zum historischen Status
  • Rivest, Ronald (1991). „Der MD4 Message Digest-Algorithmus“. Fortschritte in der Kryptologie-CRYPT0' 90 . Skript zur Vorlesung Informatik. 537 . Springer Berlin/Heidelberg. S. 303–311. doi : 10.1007/3-540-38424-3_22 . ISBN 978-3-540-54508-8. Fehlt oder leer |title=( Hilfe )

Kollisionsangriffe