Paper 2026/2107

Enhancing SAT Solving to Find (Near) Collisions in 6-Round SHA-3 Variants

Abstract

The Keccak hash function, designed by Bertoni et al., was selected as the new generation of Secure Hash Algorithm (SHA-3) in 2012. For NIST-standardized SHA-3 instances (SHA3-224/256/384/512, SHAKE128, SHAKE256), practical collision attacks have reached five rounds; six-round SHAKE128 was known only as a theoretical attack with cost $2^{123.5}$ six-round evaluations~\cite{tuyi2022sha3}. In this paper, we present the first classical practical collision attack on six-round SHAKE128 with $d{=}160$ and total complexity about $2^{47.82}$. Building on the Dinur-framework Dinur et al.~\cite{dinur2012new} and the SAT tooling of Guo et al.~\cite{tuyi2022sha3}, we introduce a parameterized colliding-trail SAT model--- collision length in digest and weight bounds are chosen at setup together with leaner differential encodings. Specifically, we introduce an enhanced heuristic strategy to identify suitable differential trails and employ multiple techniques to optimize the connectors: for the connector phase, we minimize weighted propagation cost of second round and third round, and penalize costly $\mathrm{DDT}{=}2$ transitions; candidate $\chi$-compatible equations are chosen by a bit-granular greedy routine that maximizes connector degrees of freedom. In addition to SHAKE128, we report six-round \textbf{near}-collisions on SHA3-224 and SHA3-256 (four and six differing digest bits, respectively), and practical collisions on four- and five-round SHAKE256 with the full $512$-bit digest.