@article{Huang_Ben-Yehuda_Dunkelman_Maximov_2022, title={Finding Collisions against 4-Round SHA-3-384 in Practical Time}, volume={2022}, url={https://tosc.iacr.org/index.php/ToSC/article/view/9857}, DOI={10.46586/tosc.v2022.i3.239-270}, abstractNote={<p>The Keccak sponge function family, designed by Bertoni <em>et al.</em> in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis of SHA-3 has attracted a lot of attention. Currently, the most powerful collision attack on SHA-3 is Jian Guo <em>et al.</em>’s linearisation technique. However, this technique is infeasible for variants with a<br>smaller input space, such as SHA-3-384.<br>In this work we improve upon previous results by utilising three ideas which were not used in previous works on collision attacks against SHA-3. First, we use 2-block messages instead of 1-block messages, to reduce constraints and increase flexibility in our solutions. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we propose an efficient deduce-and-sieve algorithm on the basis of two new non-random properties<br>of the Keccak non-linear layer.<br>The resulting collision-finding algorithm on 4-round SHA-3-384 has a practical time complexity of 2<sup>59.64</sup> (and a memory complexity of 2<sup>45.94</sup>). This greatly improves upon the best known collision attack so far: Dinur <em>et al.</em> achieved an impractical 2<sup>147</sup> time complexity. Our attack does not threaten the security margin of the SHA-3 hash function. However, the tools developed in this paper could be used to analyse other cryptographic primitives as well as to develop new and faster SAT solvers.</p>}, number={3}, journal={IACR Transactions on Symmetric Cryptology}, author={Huang, Senyang and Ben-Yehuda, Orna Agmon and Dunkelman, Orr and Maximov, Alexander}, year={2022}, month={Sep.}, pages={239–270} }