Near-Collision Attacks on MD4: Applied to MD4-Based Protocols
The most widely used hash functions from MD4 family have been broken, which lead to a public competition on designing new hash functions held by NIST. This paper focuses on one concept called near-collision resistance: computationally difficult to find a pair of messages with hash values differing in only few bits, which new hash functions should satisfy. In this paper, we will give a model of near-collisions on MD4, and apply it to attack protocols including HMAC/NMAC-MD4 and MD4(Password parallel to Challenge). Our new outer-key recovery attacks on HMAC/NMAC-MD4 has a complexity of 2(72) online queries and 2(77) MD4 computations, while previous result was 2(88) online queries and 2(95) MD4 computations. Our attack on MD4(Password parallel to Challenge) can recover 16 password characters with a complexity of 2(37) online queries and 22, MD4 computations, which is the first approach to attack such protocols. key words: near-collision, MD4, HMAC/NMAC, challenge and response, Hash(Password parallel to Challenge)
near-collision md4 hmac/nmac challenge and response hash(fassword parallel to challenge)