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.