Abstract
The Keccak hash function is one of the five finalists in NIST’s SHA-3 competition, and so far it showed remarkable resistance against practical collision finding attacks: 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 paper 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. When we apply our techniques to 5-round Keccak, we can get in a few days excellent near collisions, where the Hamming distance is 5 in the case of Keccak-224 and 10 in the case of Keccak-256. 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.
Chapter PDF
Similar content being viewed by others
References
Aumasson, J.-P., Meier, W.: Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. NIST Mailing List (2009)
Bernstein, D.J.: Second preimages for 6 (7 (8??)) rounds of keccak? NIST mailing list (2010)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. Presented at the ECRYPT Hash Workshop (2007)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak SHA-3 submission. Submission to NIST (Round 3) (2011)
Boura, C., Canteaut, A.: Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 1–17. Springer, Heidelberg (2011)
Boura, C., Canteaut, A., Canniére, C.D.: Higher-order differential properties of keccak and luffa. Cryptology ePrint Archive, Report 2010/589 (2010), http://eprint.iacr.org/
Daemen, J., Rijemn, V.: Plateau Characteristics. IET Information Security 1(1), 11–17 (2007)
Dinur, I., Dunkelman, O., Shamir, A.: New attacks on Keccak-224 and Keccak-256. Cryptology ePrint Archive, Report 2011/624 (2011), http://eprint.iacr.org/
Duan, M., Lai, X.: Improved zero-sum distinguisher for full round Keccak-f permutation. Cryptology ePrint Archive, Report 2011/023 (2011)
Duc, A., Guo, J., Peyrin, T., Wei, L.: Unaligned rebound attack - application to keccak. Cryptology ePrint Archive, Report 2011/420 (2011)
Khovratovich, D.: Cryptanalysis of Hash Functions with Structures. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 108–125. Springer, Heidelberg (2009)
Khovratovich, D., Biryukov, A., Nikolic, I.: Speeding up Collision Search for Byte-Oriented Hash Functions. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 164–181. Springer, Heidelberg (2009)
Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 260–276. Springer, Heidelberg (2009)
Morawiecki, P., Srebrny, M.: A SAT-based preimage analysis of reduced KECCAK hash functions. Cryptology ePrint Archive, Report 2010/285 (2010)
Naya-Plasencia, M., Röck, A., Meier, W.: Practical Analysis of Reduced-Round Keccak. In: Bernstein, D.J., Chatterjee, S. (eds.) INDOCRYPT 2011. LNCS, vol. 7107, pp. 236–254. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dinur, I., Dunkelman, O., Shamir, A. (2012). New Attacks on Keccak-224 and Keccak-256. In: Canteaut, A. (eds) Fast Software Encryption. FSE 2012. Lecture Notes in Computer Science, vol 7549. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34047-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-34047-5_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34046-8
Online ISBN: 978-3-642-34047-5
eBook Packages: Computer ScienceComputer Science (R0)