Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions

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 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 /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. We give several new attacks and limitations. Most notably, we give a new attack that results in a singleblock collision and has advantage