Introduction
HAVAL is a variable-output cryptographic hash function proposed in 1992, designed to offer greater flexibility and security than its predecessors, MD4 and MD5. It supports 3, 4, or 5 passes, with higher pass counts intended to provide increased resistance to cryptanalysis. While the 3-pass variant was compromised shortly after its introduction, the 4-pass and 5-pass versions were long considered secure. This research, presented at FSE 2006, provides the first practical collision attacks against 4-pass HAVAL and the first theoretical attack against the 5-pass variant, demonstrating that HAVAL's security margins are narrower than previously believed.
Methodology: Modular Differential Cryptanalysis
The authors employ modular differential cryptanalysis, a technique popularized by Xiaoyun Wang's work on MD5 and SHA-1. The attack follows a three-stage process:
- Differential Path Construction: Identifying a sequence of bit-level differences in internal states that cancel out to produce a collision.
- Derivation of Sufficient Conditions: Establishing bit-level requirements for chaining variables to ensure the differential path is maintained.
- Message Modification: Utilizing "Basic Modification" for the first round and "Advanced Modification" for the second round to satisfy these conditions deterministically rather than probabilistically.
The 4-pass attack specifically utilizes a "two-block" strategy, where differences introduced in the first 1024-bit message block are partially corrected by the second block, facilitating the final collision.
Key Insights
A critical component of the attack is the analysis of HAVAL's non-linear boolean functions. The researchers identified specific input patterns where bit differences could be "absorbed" or propagated in a controlled manner.
The application of advanced message modification is the primary driver of the attack's efficiency. By strategically altering message words, the researchers can satisfy conditions deep into the second pass of the algorithm. This transition from theoretical vulnerability to practical exploit allows for collision generation on commodity hardware, reducing the search space significantly compared to pure probabilistic methods.
Results and Validation
The study yields significant results for both high-pass variants of HAVAL:
- 4-Pass HAVAL: The most efficient attack has a complexity of $2^{36}$ HAVAL operations. In practice, the researchers successfully generated a collision in approximately eight hours on a standard notebook PC.
- 5-Pass HAVAL: The authors presented a theoretical attack with a complexity of $2^{123}$. While not yet practical, this complexity is lower than the $2^{128}$ operations required for a generic birthday attack on a 256-bit hash, proving a mathematical weakness in the full 5-pass design.
Conclusion
This work represents a major advancement in the cryptanalysis of the MD-family of hash functions. By demonstrating practical collisions for 4-pass HAVAL and a theoretical break for 5-pass HAVAL, the authors have redefined the security landscape for this algorithm. While pre-image attacks remain a separate challenge, the collapse of collision resistance in the full-pass versions suggests that HAVAL should no longer be considered for security-critical applications.
Summary updated