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

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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>+</mml:mo> <mml:mi>c</mml:mi> </mml:mrow> </mml:math> 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 $$\Theta (ST^2/2^c + T^2/ 2^{r})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>S</mml:mi> <mml:msup> <mml:mi>T</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>/</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>c</mml:mi> </mml:msup> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>T</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>/</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>r</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . 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\ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>B</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage $$\begin{aligned} \Omega \left( \left( \frac{S^{2}T}{2^{2c}}\right) ^{2/3} + \frac{T^2}{2^r}\right) . \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mfenced> <mml:msup> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:msup> <mml:mi>S</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>T</mml:mi> </mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>c</mml:mi> </mml:mrow> </mml:msup> </mml:mfrac> </mml:mfenced> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:mfrac> <mml:msup> <mml:mi>T</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>r</mml:mi> </mml:msup> </mml:mfrac> </mml:mfenced> <mml:mo>.</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> In certain range of parameters (e.g., $$ST^2&gt;2^c$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:msup> <mml:mi>T</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>&gt;</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>c</mml:mi> </mml:msup> </mml:mrow> </mml:math> ), 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\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>B</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> and has advantage $$\Omega ({STB}/{2^{c}} + {T^2}/{2^{\min \{r,c\}}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/M