International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Preimage Attacks on 3-Pass HAVAL and Step-Reduced MD5

Authors:
Jean-Philippe Aumasson
Willi Meier
Florian Mendel
Download:
URL: http://eprint.iacr.org/2008/183
Search ePrint
Search Google
Abstract: This paper presents preimage attacks for the hash functions 3-pass HAVAL and step-reduced MD5. Introduced in 1992 and 1991 respectively, these functions underwent severe collision attacks, but no preimage attack. We describe two preimage attacks on the compression function of 3-pass HAVAL. The attacks have a complexity of about $2^{224}$ compression function evaluations instead of $2^{256}$. Furthermore, we present several preimage attacks on the MD5 compression function that invert up to 47 (out of 64) steps within $2^{96}$ trials instead of $2^{128}$. Though our attacks are not practical, they show that the security margin of 3-pass HAVAL and step-reduced MD5 with respect to preimage attacks is not as high as expected.
BibTeX
@misc{eprint-2008-17860,
  title={Preimage Attacks on 3-Pass HAVAL and Step-Reduced MD5},
  booktitle={IACR Eprint archive},
  keywords={cryptanalysis, hash function, preimage attack},
  url={http://eprint.iacr.org/2008/183},
  note={Accepted to SAC 2008 jeanphilippe.aumasson@gmail.com 14061 received 23 Apr 2008, last revised 1 Jul 2008},
  author={Jean-Philippe Aumasson and Willi Meier and Florian Mendel},
  year=2008
}