International Association
for Cryptologic Research

The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256. In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing the internal differential characteristic. Further more, we figure out the expected size of collision subsets in internal differentials, by analyzing the collision probability of the digests rather than the intermediate states input to the last nonlinear layer. These techniques enhance the analysis of internal differentials, leading to the best collision attacks on four round-reduced variants of the SHA-3 instances. In particular, the number of attacked rounds is extended to 5 from 4 for SHA3-384, and to 6 from 5 for SHAKE256.

The KECCAK hash function was selected by NIST as the winner of the SHA-3 competition in 2012 and became the SHA-3 hash standard of NIST in 2015. On account of SHA-3’s importance in theory and applications, the analysis of its security has attracted increasing attention. In the SHA-3 family, SHA3-512 shows the strongest resistance against collision attacks: the theoretical attacks of SHA3-512 only extend to four rounds by solving polynomial systems with 64 times faster than the birthday attack. Yet for the SHA-3 instance SHAKE256, there are no results on collision attacks that we are aware of in the literatures. In this paper, we study the collision attacks against round-reduced SHA-3. Inspired by the work of Dinur, Dunkelman and Shamir in 2013, we propose a variant of birthday attack and improve the internal differential cryptanalysis by abstracting new concepts such as differential transition conditions and difference conditions table. With the help of these techniques, we develop new collision attacks on round-reduced SHA-3 using conditional internal differentials. More exactly, the initial messages constrained by linear conditions pass through the first two rounds of internal differential, and their corresponding inputs entering the last two rounds are divided into different subsets for collision search according to the values of linear conditions. Together with an improved target internal difference algorithm (TIDA), collision attacks on up to 5 rounds of all the six SHA-3 functions are obtained. In particular, collision attacks on 4-round SHA3-512 and 5-round SHAKE256 are achieved with complexity of $2^{237}$ and $2^{185}$ respectively. As far as we know, this is the best collision attack on reduced SHA3-512, and it is the first collision attack on reduced SHAKE256.