MD4 is Not One Way

MD4 is Not One-Way Gaëtan Leurent École Normale Supérieure – Département d'Informatique, 45 rue d'Ulm, 75230 Paris Cedex 05, France Abstract. MD4 is a hash function introduced by Rivest in 1990. It is still used in some contexts, and the most commonly used hash function (MD5, SHA-1, SHA-2) are based on the design principles of MD4. MD4 has been extensively studied and very efficient collision attacks are known, but it is still believed to be a one-way function. In this paper we show a partial pseudo-preimage attack on the compression function of MD4, using some ideas from previous cryptanalysis of MD4. We can choose 64 bits of the output for the cost of 232 compression function computations (the remaining bits are randomly chosen by the preimage algorithm). This gives a preimage attack on the compression function of MD4 with complexity 296, and we extend it to an attack on the full MD4 with complexity 2102. As far as we know this is the first preimage attack on a member of the MD4 family. Key words: MD4, hash function, cryptanalysis, preimage, one-way. 1 Introduction Hash functions are fundamental cryptographic primitives used in many constructions and protocols. A hash function takes a bitstring of arbitrary length as input, and outputs a digest, a small bitstring of fixed length n.

• compression function


• collision attacks


• preimage attack


• collision attack


• practice very few


• efficient collision


• hash function