International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jian Guo , Nanyang Technological University
Guozhen Liu , Nanyang Technological University
Ling Song , Jinan University, Guangzhou
Yi Tu , Nanyang Technological University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: In this work, we focus on collision attacks against instances of \shac hash family in both classical and quantum settings. Since the 5-round collision attacks on \shacc-256 and other variants proposed by Guo \etal 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 \shac to more rounds lie in the inefficiency of differential trail search. To overcome this obstacle, we develop a \sat 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 \shakea with time complexity \cpshake, which also forms a quantum collision attack with quantum time \cpshakeq, and the first 6-round quantum collision attack on \shacc-224 and \shacc-256 with quantum time \cpshattf and \cpshatfs, where $S$ represents the hardware resources of the quantum computer. The fact that classical collision attacks do not apply to 6-round \shacc-224 and \shacc-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.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32645,
  title={Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3},
  publisher={Springer-Verlag},
  author={Jian Guo and Guozhen Liu and Ling Song and Yi Tu},
  year=2022
}