Paper 2022/1009
TimeSpace Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
Abstract
Sponge hashing is a novel alternative to the popular MerkleDamgård hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA3 hashing standard. Sponge hashing is parametrized by two numbers, $r$ and $c$ (bitrate and capacity, respectively), and by a fixedsize 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 $\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 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 singleblock collision and has advantage $$ \Omega \left(\left(\frac{S^{2}T}{2^{2c}}\right)^{2/3} + \frac{T^2}{2^r}\right). $$ In certain range of parameters (e.g., $ST^2>2^c$), our attack outperforms the previouslyknown 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 MerkleDamgård hashing. Our attack relies on a novel connection between singleblock collision finding in sponge hashing and the wellstudied 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 unboundedlength collisions and those for finding very short collisions. Most notably, we prove (via a highly nontrivial compression argument) that the above attack is optimal for $B=2$ in some range of parameters.
Note: Fixed a typo in Claim 5.9
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2022
 Keywords
 Timespace tradeoffsAIRPMSponge constructionshort collisions
 Contact author(s)

cfreitag @ cs cornell edu
ashrujit @ cs washington edu
ilank @ cs huji ac il  History
 20230309: last of 2 revisions
 20220805: received
 See all versions
 Short URL
 https://ia.cr/2022/1009
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1009, author = {Cody Freitag and Ashrujit Ghoshal and Ilan Komargodski}, title = {TimeSpace Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions}, howpublished = {Cryptology ePrint Archive, Paper 2022/1009}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1009}}, url = {https://eprint.iacr.org/2022/1009} }