Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / MD4, Extended MD4, meet-in-the-middle, preimage

Date: received 16 Nov 2010, last revised 16 Nov 2010

Contact author: jinminzhong at gmail com

Available formats: PDF | BibTeX Citation

Version: 20101118:034613 (All versions of this report)

Discussion forum: Show discussion | Start new discussion