Abstract Sponge hashing is a novel alternative to the popular Merkle-Damgård hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA-3 hashing standard. Sponge hashing is parametrized by two numbers, r and c (bitrate and capacity, respectively), and by a fixed-size permutation on r+c r + c bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with arbitrary S -bit auxiliary advice input about the random permutation that make T online queries. Recent work by Coretti et al. (CRYPTO ’18) showed that such adversaries can find collisions (with respect to a random c -bit initialization vector) with advantage (ST²/2ᶜ + T²/ 2^r) Θ (S T 2 / 2 c + T 2 / 2 r). Although the above attack formally breaks collision resistance in some range of parameters, its practical relevance is limited since the resulting collision is very long (on the order of T blocks). Focusing on the task of finding short collisions, we study the complexity of finding a B -block collision for a given parameter B 1 B ≥ 1. We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage aligned ( (S^2T2^{2c}) ^2/3 + T²2ʳ). aligned Ω S 2 T 2 2 c 2 / 3 + T 2 2 r. In certain range of parameters (e. g. , ST²>2ᶜ S T 2 > 2 c), our attack outperforms the previously-known best attack. To the best of our knowledge, this is the first natural application for which sponge hashing is provably less secure than the corresponding instance of Merkle-Damgård hashing. Our attack relies on a novel connection between single-block collision finding in sponge hashing and the well-studied function inversion problem. We also give a general attack that works for any B 2 B ≥ 2 and has advantage (STB/2^{c} + T²/2^{ \{r, c\}}) <mml: math xmlns: mml="http: //www. w3. org/1998/Math/M
Ghoshal et al. (Fri,) studied this question.