Near-Collision Attacks on MD4: Applied to MD4-Based Protocols

Kazuo OHTA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A    No.1    pp.76-86
Publication Date: 2009/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.76
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Hash Function
near-collision,  MD4,  HMAC/NMAC,  challenge and response,  Hash(Password||Challenge),  

Full Text: PDF(287.3KB)>>
Buy this Article

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||Challenge). Our new outer-key recovery attacks on HMAC/NMAC-MD4 has a complexity of 272 online queries and 277 MD4 computations, while previous result was 288 online queries and 295 MD4 computations. Our attack on MD4(Password||Challenge) can recover 16 password characters with a complexity of 237 online queries and 221 MD4 computations, which is the first approach to attack such protocols.