View source for MD4

{{Short description|Cryptographic hash function}}
{{Infobox cryptographic hash function
| name = MD4
| image =
| caption =
<!-- General -->
| designers = [[Ronald Rivest]]
| publish date = October 1990<ref>{{cite web|url=http://tools.ietf.org/html/rfc1186 |title=The MD4 Message Digest Algorithm |publisher=Network Working Group |date=October 1990 |access-date=2011-04-29 |last1=Rivest |first1=Ronald L. }}</ref>
| series = [[MD2 (cryptography)|MD2]], MD4, [[MD5]], [[MD6]]
| derived from =
| derived to =
| related to =
| certification =
<!-- Detail -->
| digest size = 128 bits
| block size = 512 bits
| structure =
| rounds = 3
| cryptanalysis =
A collision attack published in 2007 can find collisions for full MD4 in less than two hash operations.<ref name=sasaki-2007 />
}}

The '''MD4 Message-Digest Algorithm''' is a [[cryptographic hash function]] developed by [[Ronald Rivest]] in 1990.<ref name="drt">{{cite web |url=http://www.rsa.com/rsalabs/node.asp?id=2253 |title=What are MD2, MD4, and MD5? |access-date=2011-04-29 |publisher=RSA Laboratories |work=Public-Key Cryptography Standards (PKCS): PKCS #7: Cryptographic Message Syntax Standard: 3.6 Other Cryptographic Techniques: 3.6.6 What are MD2, MD4, and MD5? |url-status=dead |archive-url=https://web.archive.org/web/20110901034903/http://www.rsa.com/rsalabs/node.asp?id=2253 |archive-date=2011-09-01 }}</ref> The digest length is 128 bits. The algorithm has influenced later designs, such as the [[MD5]], [[SHA-1]] and [[RIPEMD]] algorithms. The initialism "MD" stands for "Message Digest".

[[Image:MD4.svg|right|thumbnail|300px|One MD4 operation. MD4 consists of 48 of these operations, grouped in three rounds of 16 operations. ''F'' is a nonlinear function; one function is used in each round. ''M<sub>i</sub>'' denotes a 32-bit block of the message input, and ''K<sub>i</sub>'' denotes a 32-bit constant, different for each round.]]

The security of MD4 has been severely compromised. The first full [[collision attack]] against MD4 was published in 1995, and several newer attacks have been published since then. As of 2007, an attack can generate collisions in less than two MD4 hash operations.<ref name=sasaki-2007>{{cite journal |author=Yu Sasaki|year=2007 |title=New message difference for MD4 |url=https://www.iacr.org/archive/fse2007/45930331/45930331.pdf|display-authors=etal}}</ref> A theoretical [[preimage attack]] also exists.

A variant of MD4 is used in the [[Ed2k: URI scheme|ed2k URI scheme]] to provide a unique identifier for a file in the popular eDonkey2000 / eMule P2P networks. MD4 was also used by the [[rsync]] protocol (prior to version 3.0.0).

MD4 is used to compute [[NTLM]] password-derived key digests on Microsoft Windows NT, XP, Vista, 7, 8, 10 and 11.<ref name="ntlm">{{cite web |url=http://msdn.microsoft.com/en-us/library/cc236715(v=PROT.10).aspx |title=5.1 Security Considerations for Implementors |access-date=2011-07-21 |quote=Deriving a key from a password is as specified in [RFC1320] and [FIPS46-2].}}</ref>

==Security==
Weaknesses in MD4 were demonstrated by Den Boer and Bosselaers in a paper published in 1991.<ref>{{cite journal |author=Bert den Boer, Antoon Bosselaers |year=1991 |title=An Attack on the Last Two Rounds of MD4 |url=http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C91/194.PDF |url-status=dead |archive-url=https://web.archive.org/web/20030523231212/http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C91/194.PDF |archive-date=2003-05-23 }}</ref> The first full-round MD4 [[collision attack]] was found by [[Hans Dobbertin]] in 1995, which took only seconds to carry out at that time.<ref>{{cite journal |author=Hans Dobbertin |date=1995-10-23 |title=Cryptanalysis of MD4 |journal=Journal of Cryptology |volume=11 |issue=4 |pages=253–271 |doi=10.1007/s001459900047 |s2cid=7462235 |doi-access=free }}</ref> In August 2004, [[Wang Xiaoyun|Wang]] et al. found a very efficient collision attack, alongside attacks on later hash function designs in the MD4/MD5/SHA-1/RIPEMD family. This result was improved later by Sasaki et al., and generating a collision is now as cheap as verifying it (a few microseconds).<ref name=sasaki-2007 />

In 2008, the [[preimage resistance]] of MD4 was also broken by Gaëtan Leurent, with a 2<sup>102</sup> attack.<ref>{{cite book |author=Gaëtan Leurent |title=Fast Software Encryption |chapter=MD4 is Not One-Way |date=2008-02-10 |journal=Fast Software Encryption, 15th International Workshop, FSE 2008 |volume=5086 |pages=412–428 |series=Lecture Notes in Computer Science |publisher=Springer |doi=10.1007/978-3-540-71039-4_26 |isbn=978-3-540-71038-7 |chapter-url=https://iacr.org/archive/fse2008/50860419/50860419.pdf |archive-url=https://web.archive.org/web/20110611225208/https://www.di.ens.fr/~leurent/files/MD4_FSE08.pdf |archive-date=2011-06-11 }}</ref> In 2010 Guo et al published a 2<sup>99.7</sup> attack.<ref>{{Cite book|chapter-url=https://www.academia.edu/20987202|pages=56–75|last1=Guo|first1=Jian|last2=Ling|first2=San|last3=Rechberger|first3=Christian|last4=Wang|first4=Huaxiong|title=Advances in Cryptology - ASIACRYPT 2010 |chapter=Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2 |series=Lecture Notes in Computer Science |year=2010 |volume=6477 |doi=10.1007/978-3-642-17373-8_4 |isbn=978-3-642-17372-1 |doi-access=free|hdl=10356/94168|hdl-access=free}}</ref>

In 2011, RFC 6150 stated that RFC 1320 (MD4) is '''historic''' (obsolete).

==MD4 hashes==
The 128-bit (16-byte) MD4 hashes (also termed ''message digests'') are typically represented as 32-digit [[hexadecimal]] numbers. The following demonstrates a 43-byte [[ASCII]] input and the corresponding MD4 hash:

 MD4("The quick brown fox jumps over the lazy {{Background color|#87CEEB|d}}og")
 = 1bee69a46ba811185c194762abaeae90

Even a small change in the message will (with overwhelming probability) result in a completely different hash, e.g. changing <code>d</code> to <code>c</code>:

 MD4("The quick brown fox jumps over the lazy {{Background color|#87CEEB|c}}og")
 = b86e130ce7028da59e672d56ad0113df

The hash of the zero-length string is:

 MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

==MD4 test vectors==
The following test vectors are defined in RFC 1320 (The MD4 Message-Digest Algorithm)

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

==MD4 collision example==
Let:
  k1 = 839c7a4d7a92cb{{red|5}}678a5d5{{red|b}}9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed{{red|d}}45e51fe39708bf9427e9c3e8b9
  k2 = 839c7a4d7a92cb{{red|d}}678a5d5{{red|2}}9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed{{red|c}}45e51fe39708bf9427e9c3e8b9

 MD4(k1) = MD4(k2) = 4d7e6a1defa93d2dde05b45d864c429b

Note that two hex-digits of k1 and k2 define one byte of the input string, whose length is 64 bytes .

==See also==
* [[Hash function security summary]]
* [[Comparison of cryptographic hash functions]]
* [[MD2 (cryptography)|MD2]]
* [[MD5]]
* [[MD6]]

==References==
* Bert den Boer, Antoon Bosselaers: An Attack on the Last Two Rounds of MD4. Crypto 1991: 194–203
* Hans Dobbertin: Cryptanalysis of MD4. Fast Software Encryption 1996: 53–69
* Hans Dobbertin, 1998. Cryptanalysis of MD4. J. Cryptology 11(4): 253–271
* Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu: Cryptanalysis of the Hash Functions MD4 and RIPEMD. Eurocrypt 2005: 1–18
* Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro: New Message Difference for MD4. Fast Software Encryption 2007: 329–348

{{Reflist}}

==External links==
{{Wikifunctions|Z10136}}
* {{IETF RFC|1320|link=no}} - Description of MD4 by Ron Rivest
* {{IETF RFC|6150|link=no}} - MD4 to Historic Status
* {{cite book |doi=10.1007/3-540-38424-3_22 |chapter=The MD4 Message Digest Algorithm |publisher=Springer Berlin / Heidelberg |volume=537 |pages=303–311 |author=Rivest, Ronald |title=Advances in Cryptology-CRYPT0' 90 |year=1991|series=Lecture Notes in Computer Science |isbn=978-3-540-54508-8 }}

===Collision attacks===
* [http://citeseer.ist.psu.edu/denboer91attack.html An Attack on the Last Two Rounds of MD4]
* [http://eprint.iacr.org/2005/151 Improved Collision Attack on MD4]

{{Cryptography navbox | hash}}

[[Category:Broken hash functions]]