Collision Attack on GRINDAHL

Thomas Peyrin

Paper 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in JOC 2015
Keywords: GRINDAHL RIJNDAEL hash functions collision cryptanalysis.
Contact author(s): thomas peyrin @ gmail com
History: 2016-03-17: received
Short URL: https://ia.cr/2016/295
License: CC BY

BibTeX

@misc{cryptoeprint:2016/295,
      author = {Thomas Peyrin},
      title = {Collision Attack on {GRINDAHL}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/295},
      year = {2016},
      url = {https://eprint.iacr.org/2016/295}
}