CryptoDB
Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | CRYPTO 2022 |
| Abstract: | Sponge hashing is a novel alternative to the popular Merkle-Damg\aa 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 an arbitrary $S$-bit auxiliary advice input about the random permutation and $T$ queries. Recent work by Coretti et al.\ (CRYPTO '18) showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Theta(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 \emph{short} collisions, we study the complexity of finding a $B$-block collision for a given parameter $B\ge 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{align*} \Omega \left(\left(\frac{S^{2}T}{2^{2c}}\right)^{2/3} + \frac{T^2}{2^r}\right). \end{align*} In some range of parameters, our attack has constant advantage of winning while the previously-known best attack has exponentially small advantage. To the best of our knowledge, this is the first natural application for which sponge hashing is \emph{provably less secure} than the corresponding instance of Merkle-Damg\aa 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$ and has advantage $\Omega({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$ and in some range of parameters. |
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32157,
title={Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions},
publisher={Springer-Verlag},
author={Cody Freitag and Ashrujit Ghoshal and Ilan Komargodski},
year=2022
}