Paper 2022/184

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

Jian Guo, Guozhen Liu, Ling Song, and Yi Tu

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, both with negligible requirement of classical and quantum memory. 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
SHA-3SAT-based Automatic Search ToolCollision AttacksQuantum Cryptanalysis
Contact author(s)
guozhen liu @ ntu edu sg
History
2022-02-20: received
Short URL
https://ia.cr/2022/184
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/184,
      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},
      howpublished = {Cryptology ePrint Archive, Paper 2022/184},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/184}},
      url = {https://eprint.iacr.org/2022/184}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.