Cryptology ePrint Archive: Report 2017/128

New Collision Attacks on Round-Reduced Keccak

Kexin Qiao and Ling Song and Meicheng Liu and Jian Guo

Abstract: In this paper, we focus on collision attacks against Keccak hash function family and some of its variants. Following the framework developed by Dinur et al. at FSE~2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors one round further hence achieve collision attacks for up to 5 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearization of all S-boxes of the first round, the problem of finding solutions of 2-round connectors are converted to that of solving a system of linear equations. However, due to the quick freedom reduction from the linearization, the system has solution only when the 3-round differential trails satisfy some additional conditions. We develop a dedicated differential trail search strategy and find such special differentials indeed exist. As a result, the first practical collision attack against 5-round SHAKE128 and two 5-round instances of the Keccak collision challenges are found with real examples. We also give the first results against 5-round Keccak224 and 6-round Keccak collision challenges. It is remarked that the work here is still far from threatening the security of the full 24-round Keccak family.

Category / Keywords: Keccak, SHA-3, hash function, linearization, differential

Original Publication (with minor differences): IACR-EUROCRYPT-2017

Date: received 13 Feb 2017, last revised 3 Mar 2017

Contact author: songling at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20170303:085240 (All versions of this report)

Short URL: ia.cr/2017/128

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]