Cryptology ePrint Archive: Report 2016/295

Collision Attack on GRINDAHL

Thomas Peyrin

Abstract: Hash functions have been among the most scrutinized cryptographic primitives in the previous decade, mainly due to the cryptanalysis breakthroughs on MD-SHA family and the NIST SHA3 competition that followed. GRINDAHL is a hash function proposed at FSE 2007 that inspired several SHA3 candidates. One of its particularities is that it follows the RIJNDAEL design strategy, with an efficiency comparable to SHA2. This paper provides the first cryptanalytic work on this scheme and we show that the 256-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 $2^{112}$ hash computations, an attacker can generate a collision for the full 256-bit version of GRINDAHL.

Category / Keywords: secret-key cryptography / GRINDAHL, RIJNDAEL, hash functions, collision, cryptanalysis.

Original Publication (in the same form): IACR-JOC-2015

Date: received 16 Mar 2016

Contact author: thomas peyrin at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160317:162204 (All versions of this report)

Short URL: ia.cr/2016/295

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]