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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$r+c$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>+</mo> <mi>c</mi> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Theta (ST^2/2^c + T^2/ 2^{r})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>S</mi> <msup> <mi>T</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mi>c</mi> </msup> <mo>+</mo> <msup> <mi>T</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mi>r</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$B\ge 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage <Equation ID="Equ10"> <EquationSource Format="TEX">$\begin{aligned} \Omega \left( \left( \frac{S^{2}T}{2^{2c}}\right) ^{2/3} + \frac{T^2}{2^r}\right) . \end{aligned}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <mi mathvariant="normal">Ω</mi> <mfenced close=")" open="("> <msup> <mfenced close=")" open="("> <mfrac> <mrow> <msup> <mi>S</mi> <mn>2</mn> </msup> <mi>T</mi> </mrow> <msup> <mn>2</mn> <mrow> <mn>2</mn> <mi>c</mi> </mrow> </msup> </mfrac> </mfenced> <mrow> <mn>2</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo>+</mo> <mfrac> <msup> <mi>T</mi> <mn>2</mn> </msup> <msup> <mn>2</mn> <mi>r</mi> </msup> </mfrac> </mfenced> <mo>.</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>In certain range of parameters (e.g., <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$ST^2>2^c$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <msup> <mi>T</mi> <mn>2</mn> </msup> <mo>></mo> <msup> <mn>2</mn> <mi>c</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>), 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$B\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and has advantage <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\Omega ({STB}/{2^{c}} + {T^2}/{2^{\min \{r,c\}}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="italic">STB</mi> </mrow> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mi>c</mi> </msup> <mo>+</mo> <msup> <mi>T</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mrow> <mo movablelimits="true">min</mo> <mo stretchy="false">{</mo> <mi>r</mi> <mo>,</mo> <mi>c</mi> <mo stretchy="false">}</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, adapting an idea of Akshima et al. (CRYPTO ’20). We complement the above attacks with bounds on the best possible attacks. Specifically, we prove that there is a qualitative jump in the advantage of best possible attacks for finding unbounded-length collisions and those for finding very short collisions. Most notably, we prove (via a highly non-trivial compression argument) that the above attack is optimal for <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$B=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> in some range of parameters.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年12月5日

查看全文

Cody Freitag,
Ashrujit Ghoshal,
Ilan Komargodski

摘要

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 $\Theta (ST^2/2^c + T^2/ 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\ge 1$ $B \geq 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 $\begin{aligned} \Omega \left( \left( \frac{S^{2}T}{2^{2c}}\right) ^{2/3} + \frac{T^2}{2^r}\right) . \end{aligned}$ $\begin{matrix} Ω ({(\frac{S^{2} T}{2^{2 c}})}^{2 / 3} + \frac{T^{2}}{2^{r}}) . \end{matrix}$ In certain range of parameters (e.g., $ST^2>2^c$ $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\ge 2$ $B \geq 2$ and has advantage $\Omega ({STB}/{2^{c}} + {T^2}/{2^{\min \{r,c\}}})$ $Ω (STB / 2^{c} + T^{2} / 2^{min {r, c}})$ , adapting an idea of Akshima et al. (CRYPTO ’20). We complement the above attacks with bounds on the best possible attacks. Specifically, we prove that there is a qualitative jump in the advantage of best possible attacks for finding unbounded-length collisions and those for finding very short collisions. Most notably, we prove (via a highly non-trivial compression argument) that the above attack is optimal for $B=2$ $B = 2$ in some range of parameters.