[Resource Topic] 2023/389: TIDAL: Practical Collisions on State-Reduced Keccak Variants

Welcome to the resource topic for 2023/389

TIDAL: Practical Collisions on State-Reduced Keccak Variants

Authors: Sahiba Suryawanshi, Dhiman Saha, Shashwat jaiswal


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.

ePrint: https://eprint.iacr.org/2023/389

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .