Paper 2008/183
Preimage Attacks on 3-Pass HAVAL and Step-Reduced MD5
Jean-Philippe Aumasson, Willi Meier, and Florian Mendel
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.
Note: Revised version
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Accepted to SAC 2008
- Keywords
- cryptanalysishash functionpreimage attack
- Contact author(s)
- jeanphilippe aumasson @ gmail com
- History
- 2008-07-01: last of 9 revisions
- 2008-04-24: received
- See all versions
- Short URL
- https://ia.cr/2008/183
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/183, author = {Jean-Philippe Aumasson and Willi Meier and Florian Mendel}, title = {Preimage Attacks on 3-Pass {HAVAL} and Step-Reduced {MD5}}, howpublished = {Cryptology {ePrint} Archive, Paper 2008/183}, year = {2008}, url = {https://eprint.iacr.org/2008/183} }