Improved Collision Attack on MD4

Yusuke Naito; Yu Sasaki; Noboru Kunihiro; Kazuo Ohta

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2005/151

Improved Collision Attack on MD4

Yusuke Naito, Yu Sasaki, Noboru Kunihiro, and Kazuo Ohta

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].

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Collision Attack MD4 Hash Function Message Modification
Contact author(s): tolucky @ ice uec ac jp
History: 2005-05-26: received
Short URL: https://ia.cr/2005/151
License: CC BY

BibTeX

@misc{cryptoeprint:2005/151,
      author = {Yusuke Naito and Yu Sasaki and Noboru Kunihiro and Kazuo Ohta},
      title = {Improved Collision Attack on MD4},
      howpublished = {Cryptology ePrint Archive, Paper 2005/151},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/151}},
      url = {https://eprint.iacr.org/2005/151}
}