MD4 Algorithm

Description

MD4 is an hash algorithm (the four in series) created by Ronald Rivest in MIT at 1990. The hash has a length of 128 bits. The algorithm has influenced posterior design like MD5, SHA family and RIPEMD.

Algorithm

Based on RFC 1320.1)

Parameter: A message with length in bits ⇐ 264.
Output: The hash of the message with length in bits = 128.

  1. Padding of the message: Extend the message until the length in bits has to be congruent 448 mod 512. This always happen, even if the message already are congruent 448 mod 512. The padding occur in this manner: The bit 1 is added at the end of the message and then bits 0 are added until padding condition is meet.
  2. A representation of 64 bits of the length of the message(in bits) before the extension is added at the end of the message in format ”little endian”.
  3. A cycle is made ripping the message in parts of 16 words(length of word are 32 bits).
  4. For each part a compress function is applied.

Weakness

For evaluating the strength of a hash function 2 concepts are in use.

  1. Resistant to preimage attack: Given the hash obtain a message that has that hash .
  2. Resistant to collision attack: Obtain two message that has the same hash.

Since his born MD4 has been criticized for his security even by the same Ronald Rivest because MD4 has been design thinking in performance before all. In 1991 Den Boer y Bosselaers show that MD4 without the first round are collision-weak 2). In 1996 H. Dobbertin develop a collision attack with probability 2-22 3). Also show how find message with real meaning. In 1998 he show that MD4 without one round are preimage-weak4). Since 2004 until now a lot of collision attacks has been develop 5) 6) 7) 8) 9) 10) 11) finding collisions very efficient(even with manual calculation) 12).

Recently there are various preimage attacks. A Microsoft research group found preimage in reduced-MD4 (2 rounds and 7 steps) 13). Gaëtan Leurent show a preimage attack with complexity 2102 14).

All this show that MD4 are very weak and nobody could use it.

Sample Code

1) R. Rivest, April 1992 “RFC 1320 - The MD4 Message-Digest Algorithm”
2) Den Boer y Bosselaers, 15 October 1991, “An Attack on the Last Two Rounds of MD4”
3) H. Dobbertin, 23 October 1995 ,”Cryptanalysis of MD4”
4) H. Dobbertin, 21 March 1997, “The First Two Rounds of MD4 are Not One-Way”
5) Yusuke Naito, Yu Sasaki, Noboru Kunihiro, y Kazuo Ohta, 2005 “Improved Collision Attack on MD4”
6) Jongsung Kim, Alex Biryukov, Bart Preneel y Sangjin Lee, 2005, “On the Security of Encryption Modes of MD4, MD5 and Haval”
7) Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen1 y Xiuyuan Yu, 2004 “Cryptanalysis of the Hash Functions MD4 and RIPEMD”
8) Xiaoyun Wang and Hongbo Yu, 2005, “How to Break MD5 and Other Hash Functions”
9) Ilya Mironov and Lintao Zhang, 2006, “Applications of SAT Solvers to Cryptanalysis of Hash Functions”
10) Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen, 2007, “Automatic Search of Diferential Path in MD4”
11) Hongbo Yu and Xiaoyun Wang, 2007, “MultiCollision Attack on the Compression Functions of MD4 and 3-Pass HAVAL”
12) Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hongbo Yu , August 17, 2004 “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD”
13) Debapratim De, Abishek Kumarasubramanian and Ramarathnam Venkatesan, 2007, “Inversion Attacks on Secure Hash Functions using Sat solvers”
14) Gaëtan Leurent, 2008, “MD4 is Not One-Way”