Improved preimage attack on one-block MD4

MD4 is a hash function designed by Rivest in 1990. The design philosophy of many important hash functions, such as MD5, SHA-1 and SHA-2, originated from that of MD4. We propose an improved preimage attack on one-block MD4 with the time complexity 295 MD4 compression function operations, as compared to the 21071 complexity of the previous attack by Aoki et al. (SAC 2008). The attack is based on previous methods, but introduces new techniques. We also use the same techniques to improve the pseudo-preimage and preimage attacks on Extended MD4 with 225.2 and 212.6 improvement factor, as compared to previous attacks by Sasaki et al. (ACISP 2009).

► We show how to improve preimage attack on one-block MD4 using the three methods.
► We also improve preimage attack on Extended MD4.
► We introduce two propositions. The key idea of our improvements is from the two propositions.
► We present the multi-neutral-word partial-fixing technique.