In this work we improve previous results with three ideas which were not used in previous works against SHA-3. First, in order to reduce constraints and increase flexibility in our solutions, we use 2-block messages instead of 1-block messages. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we consider two new non-random properties of the Keccak non-linear layer and propose an efficient deduce-and-sieve algorithm based on these properties.
The resulting collision-finding algorithm on 4-round SHA3-384 has a practical time complexity of $2^{59.64}$ (and memory complexity of $2^{45.93}$). This greatly improves the previous best known collision attack by Dinur et al., whose $2^{147}$ time complexity was far from being practical. Although our attack does not threaten the security margin of the SHA-3 hash function, the tools developed in this paper could be useful in future analysis of other cryptographic primitives and also in development of new and faster SAT solvers.
Category / Keywords: SHA-3 hash function, collision attack, deduce-and-sieve algorithm, SAT solver Date: received 18 Feb 2022, last revised 30 Mar 2022 Contact author: senyang huang at eit lth se Available format(s): PDF | BibTeX Citation Version: 20220330:144140 (All versions of this report) Short URL: ia.cr/2022/194