Paper 2012/672

Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials

Itai Dinur, Orr Dunkelman, and Adi Shamir

Abstract

On October 2-nd 2012 NIST announced its selection of the Keccak scheme as the new SHA-3 hash standard. In this paper we present the first published collision finding attacks on reduced-round versions of Keccak-384 and Keccak-512, providing actual collisions for 3-round versions, and describing an attack which is $2^{45}$ times faster than birthday attacks for 4-round Keccak-384. For Keccak-256, we increase the number of rounds which can be attacked to 5. All these results are based on a generalized {\it internal differential attack} (introduced by Peyrin at Crypto 2010), and use it to map a large number of Keccak inputs into a relatively small subset of possible outputs with a surprisingly large probability. In such a \textit{squeeze attack} it is easier to find random collisions in the reduced target subset by a standard birthday argument.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Full version of the FSE 2013 paper
Keywords
Hash functioncryptanalysisSHA-3Keccakcollisionsinternal differentialssqueeze attack.
Contact author(s)
itai dinur @ weizmann ac il
History
2013-02-12: revised
2012-11-28: received
See all versions
Short URL
https://ia.cr/2012/672
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/672,
      author = {Itai Dinur and Orr Dunkelman and Adi Shamir},
      title = {Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials},
      howpublished = {Cryptology ePrint Archive, Paper 2012/672},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/672}},
      url = {https://eprint.iacr.org/2012/672}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.