Abstract:
At Crypto '06, Bellare presented new security proofs for HMAC and
NMAC, under the assumption that the underlying compression function is
a pseudo-random function family. Conversely, at Asiacrypt '06,
Contini and Yin used collision techniques to obtain forgery and
partial key-recovery attacks on HMAC and NMAC instantiated with MD4,
MD5, SHA0 and reduced SHA1. In this paper, we present the first
full key-recovery attacks on NMAC and HMAC instantiated with a
real-life hash function, namely MD4. Our main result is an attack on
HMAC/NMAC-MD4 which recovers the full MAC secret key after roughly
$2^{88}$ MAC queries and $2^{95}$ MD4 computations. We also extend the
partial key-recovery Contini-Yin attack on NMAC-MD5 (in the
related-key setting) to a full key-recovery attack. The attacks are
based on generalizations of collision attacks to recover a secret IV,
using new differential paths for MD4.
Bibtex:
@inproceedings{FLN07,
author = {Pierre-Alain Fouque and
Ga{\"e}tan Leurent and
Phong Q. Nguyen},
title = {Full Key-Recovery Attacks on {HMAC/NMAC-MD4} and {NMAC-MD5}},
booktitle = {Proc. CRYPTO '07},
year = {2007},
pages = {13-30},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {4622}