(Pseudo) Preimage Attack on Round-Reduced Grøstl Hash Function and Others

Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian ZouLecture Notes in Computer Science 2012 · DOI · OpenAlex

Presented at FSE 2012, this research explores the security margins of the Grøstl hash function—one of the five finalists in the NIST SHA-3 competition—alongside other prominent designs like Whirlpool and AES-based hashes. The authors demonstrate the first "pseudo preimage" attacks on round-reduced versions of Grøstl, proving that even sophisticated "wide-pipe" designs have structural vulnerabilities that can be exploited using optimized cryptanalytic techniques.

The Preimage Challenge in Wide-Pipe Designs

In cryptography, a preimage attack involves finding an input that hashes to a specific target value. For a secure $n$-bit hash function, this should ideally require $2^n$ operations. Grøstl uses a "wide-pipe" design, meaning its internal state is $2n$ bits (double the hash size). This design choice is intended to provide a higher security margin against certain collision and preimage attacks by making the internal state significantly larger than the final output.

The challenge addressed here is whether this wide-pipe structure holds up against advanced Meet-in-the-Middle (MitM) attacks. Specifically, the authors look at pseudo preimage attacks, where the attacker is allowed to choose the initial value (IV) of the hash function to find a match. While less severe than a standard preimage attack (where the IV is fixed), pseudo preimage attacks are critical indicators of a hash function's structural strength and its resistance to more complex multi-block attacks.

Optimized Meet-in-the-Middle Framework

The researchers utilize a refined Meet-in-the-Middle (MitM) framework, originally pioneered by Aoki and Sasaki. The core idea is to split the hash function into two parts: a "forward chunk" and a "backward chunk." By calculating both independently and looking for a match at a middle point, the attacker can find a solution much faster than brute force.

The general Meet-in-the-Middle framework with initial structure and partial matching.

Key techniques employed to extend the reach of the MitM attack include:

  • Initial Structure & Local Collisions: Allowing the two sub-functions to share certain steps to increase the number of rounds that can be attacked.
  • Partial Matching: Instead of matching the entire state at once, they match a portion of it first to filter candidates, reducing computational overhead.
  • Splice-and-Cut: A technique that treats the compression function as a circle, allowing any step to be the starting or matching point.

Key Insight: The Three-Sum Optimization

The most significant breakthrough in this paper is the realization that Grøstl’s wide-pipe state ($2n$ bits) can be matched with a complexity less than $2^n$. This is possible because the compression function's structure ($F(H,M) = P(H \oplus M) \oplus Q(M) \oplus H$) allows the attack to be reframed as a specialized three-sum problem.

By restricting certain internal states to specific subspaces (finding "partial zero preimages"), the authors bypass the standard birthday bound limits that usually protect wide-pipe designs. This allows them to find matches in the $2n$-bit state using fewer than $2^n$ operations, effectively neutralizing the intended advantage of the wide-pipe architecture.

Illustration of the three-sum optimization using lookup tables to find matches in the internal state.

Results and Impact

The paper delivers several "firsts" and "bests" in the field of hash cryptanalysis. Notably, it incorporates the output transformation (the final step of the hash) into the attack, providing a more complete picture of the function's security than previous studies that only focused on the compression function.

Target Rounds Attacked Time Complexity Memory Complexity
Grøstl-256 5 / 10 $2^{244.85}$ $2^{230.13}$
Grøstl-512 8 / 14 $2^{507.32}$ $2^{507.00}$
Whirlpool 5 / 10 $2^{481.5}$ $2^{64}$
Whirlpool (2nd Preimage) 5 / 10 $2^{448}$ $2^{64}$

The Whirlpool results represent a significant improvement over the previous best attack ($2^{504}$ time). Additionally, the authors improved the time complexity for 7-round AES hashing modes compared to previous state-of-the-art work.

Limitations and Conclusion

While these results are mathematically significant, they are round-reduced and theoretical. The attacks do not break the full versions of Grøstl (which use 10 or 14 rounds), and the security claims of the full Grøstl hash remain intact. Furthermore, with time complexities like $2^{244}$, these attacks cannot be executed on any existing or foreseeable hardware.

However, they serve as a vital "stress test" for modern hash designs. The research proves that wide-pipe constructions are not a silver bullet against preimage attacks and that the internal structure of the compression function remains a critical factor in overall security. Future work may involve applying these optimized chunk separation strategies to other AES-like structures to further map the boundaries of hash function security.

Summary updated

BibTeX
@inproceedings{wu2012pseudo,
  author = {Shuang Wu and Dengguo Feng and Wenling Wu and Jian Guo and Le Dong and Jian Zou},
  title = {{(Pseudo) Preimage Attack on Round-Reduced Grøstl Hash Function and Others}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2012},
  doi = {10.1007/978-3-642-34047-5\_8},
}
Figure