Paper 2023/389

TIDAL: Practical Collisions on State-Reduced Keccak Variants

Sahiba Suryawanshi, IIt Bhilai
Dhiman Saha
Shashwat jaiswal, IIt Bhilai

An important tool that has contributed to collision search on Keccak/SHA3 is the Target Difference Algorithm (TDA) and its inter- nal differential counterpart Target Internal Difference Algorithm (TIDA), which were introduced by Dinur et al. in separate works in FSE 2012 and 2013 respectively. These algorithms provide an ingenious way of extend- ing the differential trails by one round and exploiting the affine subspaces generated due to the low algebraic degree of the Keccak S-box. The cur- rent work introduces TIDAL, which can extend TIDA by one more round capitalizing on linearization techniques introduced by Guo et al. in JoC. This approach requires increment consistency checks, which is also im- proved in this work. The TIDAL strategy, in conjunction with a determin- istic internal differential trail, has been applied to Keccak variants up to 400-bit state-size and leads to practical collision attacks for most of them up to 5 rounds. In particular collisions have been confirmed for 4-round Keccak[136, 64] with a complexity of 220 and on 6-round of Keccak[84,16] with a complexity of 25 . Further, this work completely characterizes all collision attacks on state-reduced variants, showcasing that TIDAL covers most space up to 5 rounds. As state and round-reduced Keccak variants are used to realize the internal states of many crypto primitives, the re- sults presented here generate a significant impact. Finally, it shows new directions for the long-standing problem of state-reduced variants being difficult to be attacked.

Available format(s)
Attacks and cryptanalysis
Publication info
SHA3Keccakcollisionconnectorstate reduce keccak
Contact author(s)
sahibas @ iitbhilai ac in
dhiman @ iitbhilai ac in
shashwatj @ iitbhilai ac in
2023-03-24: approved
2023-03-18: received
See all versions
Short URL
No rights reserved


      author = {Sahiba Suryawanshi and Dhiman Saha and Shashwat jaiswal},
      title = {TIDAL: Practical Collisions on State-Reduced Keccak Variants},
      howpublished = {Cryptology ePrint Archive, Paper 2023/389},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.