27 March 2013 Brussels, Belgium

Orr Dunkelman
University of Haifa

Four rounds are not enough

Keccak's resistance to cryptanalytic attempts is probably a leading reason for its selection as SHA-3. In this talk we discuss the best collision attack against Keccak at the time of its selection: after several years of cryptanalysis and a lot of effort, the largest number of Keccak rounds for which actual collisions were found was only 2. In this work we develop improved collision finding techniques which enable us to double this number. More precisely, we can now find within a few minutes on a single PC actual collisions in standard Keccak-224 and Keccak-256, where the only modification is to reduce their number of rounds to 4. Our new attack combines differential and algebraic techniques, and uses the fact that each round of Keccak is only a quadratic mapping in order to efficiently find pairs of messages which follow a high probability differential characteristic. This is a joint work with Itai Dinur and Adi Shamir.


[Slides]