Cryptology ePrint Archive: Report 2012/672

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

Itai Dinur and 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.

Category / Keywords: Hash function, cryptanalysis, SHA-3, Keccak, collisions, internal differentials, squeeze attack.

Publication Info: Full version of the FSE 2013 paper

Date: received 28 Nov 2012, last revised 12 Feb 2013

Contact author: itai dinur at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20130212:114430 (All versions of this report)

Short URL: ia.cr/2012/672

Discussion forum: Show discussion | Start new discussion