International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improved Collision Attack on MD4

Authors:
Yusuke Naito
Yu Sasaki
Noboru Kunihiro
Kazuo Ohta
Download:
URL: http://eprint.iacr.org/2005/151
Search ePrint
Search Google
Abstract: In this paper, we propose an attack method to find collisions of MD4 hash function. This attack is the improved version of the attack which was invented by Xiaoyun Wang et al [1]. We were able to find collisions with probability almost 1, and the average complexity to find a collision is upper bounded by three times of MD4 hash operations. This result is improved compared to the original result of [1] where the probability were from $2^{-6}$ to $2^{-2}$, and the average complexity to find a collision was upper bounded by $2^8$ MD4 hash operations. We also point out the lack of sufficient conditions and imprecise modifications for the original attack in [1].
BibTeX
@misc{eprint-2005-12487,
  title={Improved Collision Attack on MD4},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Collision Attack, MD4, Hash Function, Message Modification},
  url={http://eprint.iacr.org/2005/151},
  note={ tolucky@ice.uec.ac.jp 12923 received 20 May 2005},
  author={Yusuke Naito and Yu Sasaki and Noboru Kunihiro and Kazuo Ohta},
  year=2005
}