Improved (Pseudo) Preimage Attack and Second Preimage Attack on Round-Reduced Grostl Hash Function

摘要

The Grostl hash function is one of the five finalists in the third round of SHA-3 competition hosted by NIST. In this paper, we propose some improved (pseudo) preimage attacks on the Grostl hash function by using some techniques, such as subspace preimage attack and the guess-and-determine technique. We present the improved pseudo preimage attacks on 5-round Grostl-256 hash function and 8-round Grostl-512 hash function, and the complexities of these attacks are (2~(239.90), 2~(240.40)) (in time and memory) and (2~(199.50), 2~(499)), respectively. We also extend the pseudo preimage from 5 rounds to 6 rounds for Grostl-256 hash function, besides the biclique attack. Furthermore, we propose the pseudo second preimage attack on 6-round Grostl-256 hash function. The complexities of our 6-round (pseudo) preimage and second preimage attacks are (2~(253.26), 2~(253.67)) and (2~(251.0), 2~(252.0)), respectively. As far as we know, these are the best known preimage attacks on round-reduced Grostl hash function.