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

Lei WANG  Kazuo OHTA  Noboru KUNIHIRO 

Publication
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
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Hash Function
Keyword: 
near-collision,  MD4,  HMAC/NMAC,  challenge and response,  Hash(Password||Challenge), 

Full Text: PDF(285.9KB)

Summary: 
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.