Paper 2010/583

Improved Preimage Attack on One-block MD4

Jinmin Zhong and Xuejia Lai

Abstract

We propose an improved preimage attack on one-block MD4 with the time complexity $2^{94.98}$ MD4 compression function operations, as compared to $2^{107}$ in \cite{AokiS-sac08}. We research the attack procedure in \cite{AokiS-sac08} and formulate the complexity for computing a preimage attack on one-block MD4. We attain the result mainly through the following two aspects with the help of the complexity formula. First, we continue to compute two more steps backward to get two more chaining values for comparison during the meet-in-the-middle attack. Second, we search two more neutral words in one independent chunk, and then propose the multi-neutral-word partial-fixing technique to get more message freedom and skip ten steps for partial-fixing, as compared to previous four steps. We also use the initial structure technique and apply the same idea to improve the pseudo-preimage and preimage attacks on Extended MD4 with $2^{25.2}$ and $2^{12.6}$ improvement factor, as compared to previous attacks in \cite{SasakiA-acisp09}, respectively.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
MD4Extended MD4meet-in-the-middlepreimage
Contact author(s)
jinminzhong @ gmail com
History
2010-11-18: received
Short URL
https://ia.cr/2010/583
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/583,
      author = {Jinmin Zhong and Xuejia Lai},
      title = {Improved Preimage Attack on One-block MD4},
      howpublished = {Cryptology ePrint Archive, Paper 2010/583},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/583}},
      url = {https://eprint.iacr.org/2010/583}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.