Paper 2022/184

Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3 (Full Version)

Jian Guo, Nanyang Technological University
Guozhen Liu, Nanyang Technological University
Ling Song, Jinan University
Yi Tu, Nanyang Technological University

In this work, we focus on collision attacks against instances of SHA-3 hash family in both classical and quantum settings. Since the 5-round collision attacks on SHA3-256 and other variants proposed by Guo et al. at JoC~2020, no other essential progress has been published. With a thorough investigation, we identify that the challenges of extending such collision attacks on SHA-3 to more rounds lie in the inefficiency of differential trail search. To overcome this obstacle, we develop a SAT-based automatic search toolkit. The tool is used in multiple intermediate steps of the collision attacks and exhibits surprisingly high efficiency in differential trail search and other optimization problems encountered in the process. As a result, we present the first 6-round classical collision attack on SHAKE-128 with time complexity $2^{123.5}$, which also forms a quantum collision attack with quantum time ${{2^{67.25}}/{\sqrt{S}}}$, and the first 6-round quantum collision attack on SHA3-224 and SHA3-256 with quantum time ${{2^{97.75}}/{\sqrt{S}}}$ and ${{2^{104.25}}/{\sqrt{S}}}$, both with negligible requirement of classical and quantum memory. The fact that classical collision attacks do not apply to 6-round SHA3-224 and SHA3-256 shows the higher coverage of quantum collision attacks, which is consistent with that on SHA-2 observed by Hosoyamada and Sasaki at CRYPTO~2021.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
SHA-3 SAT-based Automatic Search Tool Collision Attacks Quantum Cryptanalysis
Contact author(s)
guojian @ ntu edu sg
guozhen liu @ ntu edu sg
songling qs @ gmail com
tuyi0002 @ e ntu edu sg
2022-09-20: revised
2022-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jian Guo and Guozhen Liu and Ling Song and Yi Tu},
      title = {Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3 (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/184},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.