Collision Attack on Grindahl

摘要

Hash functions have been among the most scrutinized cryptographic primitives in the previous decade, mainly due to the cryptanalysis breakthroughs on MD-SHAfamily and the NIST SHA-3 competition that followed. Grindahl is a hash function proposed at FSE 2007 that inspired several SHA-3 candidates. One of its particularities is that it follows the AES design strategy, with an efficiency comparable to SHA-256. This paper provides the first cryptanalytic work on this scheme and we show that the -bit version of Grindahl is not collision resistant. Our attack uses byte-level truncated differentials and leverages a counterintuitive method (reaching an internal state where all bytes are active) in order to ease the construction of good differential paths. Then, by a careful utilization of the freedom degrees inserted every round, and with a work effort of approximatively hash computations, an attacker can generate a collision for the full -bit version of Grindahl.