The Second-Preimage Attack on MD4

Abstract. In Eurocrypt’05, Wang et al. presented new techniques to find collisions of Hash function MD4. The techniques are not only effi-cient to search for collisions, but also applicable to explore the second-preimage of MD4. About the second-preimage attack, they showed that a random message was a weak message with probability 2−122 and it only needed a one-time MD4 computation to find the second-preimage corresponding to the weak message. A weak message means that there exits a more efficient attack than the brute force attack to find its second-preimage. In this paper, we find another new collision differential path which can be used to find the second-preimage for more weak messages. For any random message, it is a weak message with probability 2−56, and it can be converted into a weak message by message modification techniques with about 227 MD4 computations. Furthermore, the original message is close to the resulting message (weak message), i.e, the Ham-ming weight of the difference for two messages is about 44