International Association for Cryptologic Research

International Association
for Cryptologic Research


Senyang Huang


Finding Collisions against 4-Round SHA-3-384 in Practical Time
The Keccak sponge function family, designed by Bertoni et al. 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 et al.’s linearisation technique. However, this technique is infeasible for variants with asmaller input space, such as SHA-3-384.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 propertiesof the Keccak non-linear layer.The resulting collision-finding algorithm on 4-round SHA-3-384 has a practical time complexity of 259.64 (and a memory complexity of 245.94). This greatly improves upon the best known collision attack so far: Dinur et al. achieved an impractical 2147 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.
Reconstructing an S-box from its Difference Distribution Table 📺
Orr Dunkelman Senyang Huang
In this paper we study the problem of recovering a secret S-box from its difference distribution table (DDT). While being an interesting theoretical problem on its own, the ability to recover the S-box from the DDT of a secret S-box can be used in cryptanalytic attacks where the attacker can obtain the DDT (e.g., in Bar-On et al.’s attack on GOST), in supporting theoretical analysis of the properties of difference distribution tables (e.g., in Boura et al.’s work), or in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis).We show that using the well established relation between the DDT and the linear approximation table (LAT), one can devise an algorithm different from the straightforward guess-and-determine (GD) algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the GD algorithm. We tested our new algorithm on random S-boxes of different sizes, and for random 14-bit bijective S-boxes, our results outperform the GD attack by several orders of magnitude.