Paper 2017/128

New Collision Attacks on Round-Reduced Keccak

Kexin Qiao, Ling Song, 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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
KeccakSHA-3hash functionlinearizationdifferential
Contact author(s)
songling @ ntu edu sg
History
2017-03-03: revised
2017-02-16: received
See all versions
Short URL
https://ia.cr/2017/128
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/128,
      author = {Kexin Qiao and Ling Song and Meicheng Liu and Jian Guo},
      title = {New Collision Attacks on Round-Reduced Keccak},
      howpublished = {Cryptology ePrint Archive, Paper 2017/128},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/128}},
      url = {https://eprint.iacr.org/2017/128}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.