# Preimage resistance of sponge-based hashes and XOFs

In the sponge construction for hash functions, including SHA3 and SHAKE, its used a permutation $$f:\{0,1\}^r\times\{0,1\}^c\to\{0,1\}^r\times\{0,1\}^c\\ \;\quad(R,C)\quad\quad\mapsto\quad\;(R',C')$$ where $$r$$ is the rate, $$c$$ is the capacity (with $$r+c=1600$$ in SHA3 and SHAKE). Function $$f$$ is iterated with a $$r$$-bit (padded) message block XORed with $$R$$. The hash is the first $$d$$ bits of $$R'$$ at the last output of $$f$$ assuming $$d\le r$$ (for eXtendable Output Functions, it's performed $$\lceil d/r\rceil-1$$ extra iterations of $$f$$, and the output is the first $$d$$ bits of the concatenation of the $$R'$$ in the last $$\lceil d/r\rceil$$ iterations of $$f$$).

In SHA3 with $$d$$-bit output, it's used $$c=2d$$. There was some back an forth on that, and by this account, the rationale for $$c=2d$$ was having $$d$$ bits of preimage resistance.

Function $$d$$ $$r$$ $$c$$ Collision resistance* Preimage resistance*
$$\operatorname{SHA3-224}$$ $$224$$ $$1152$$ $$448$$ $$112$$ $$224$$
$$\operatorname{SHA3-256}$$ $$256$$ $$1088$$ $$512$$ $$128$$ $$256$$
$$\operatorname{SHA3-384}$$ $$384$$ $$832$$ $$768$$ $$192$$ $$384$$
$$\operatorname{SHA3-512}$$ $$512$$ $$576$$ $$1024$$ $$256$$ $$512$$
$$\operatorname{SHAKE128}$$ $$d$$ $$1344$$ $$256$$ $$\min(d/2,128)$$ $$\min(d,128)$$
$$\operatorname{SHAKE256}$$ $$d$$ $$1088$$ $$512$$ $$\min(d/2,256)$$ $$\min(d,256)$$

* Stated design goal

1. How is the stated preimage resistance above justified (against classical computers, under an ideal permutation model for $$f$$) ?
2. Could we obtain the stated assurances with a lower $$c$$ (thus a faster processing of large messages), in particular in light of Charlotte Lefevre & Bart Mennink's Tight Preimage Resistance of the Sponge Construction, in proceedings of Crypto 2022 and ePrint.
• This comment is a bit of a rant. I wish the security level of the sponge/duplex constructions was clearly explained somewhere. There seem to be a bunch of different claims being made by different authors and lots of overcomplicated nonsense being thrown around in papers/presentations. If papers were written as comprehensively as possible, everyone would be better off. Or at least state things in plain English for non-academics and then in a more complex way for academics. Some authors manage to do this. Jan 4 at 13:53
• Regarding question 1), My understanding is that most of these bounds given in several works are mainly derived through indifferentiability analysis. That is, assuming that the permutation is modelled as a random one, it is hard to distinguish a sponge from a random oracle & a simulator simulating the permutation from the random oracle. In other words, we can simulate the sponge given a random oracle and the attacker can't detect inconsistencies. Consequently, we can replace the sponge by a random oracle, then the tasks is to break whatever property of the random oracle (in this case pre-image) Jan 4 at 16:42
• The designers of the sponge constructions already showed that for $q$ queries, the indifferentiablity bound is $q(q+1)/2^{c+1}$. In, our sort of game hop, now the adversary has to find pre-images for $d$-bits ouputs of a true random oracle. Which can only happen with probability $1/2^d$. So finding pre-images requires making queries that at least break indifferentiability or pre-images in the ROM. Hence, the numbers in the table. Jan 4 at 16:56
• I haven't been able to look at the paper by Levefre and Mennik fully (only the presentation). However, my understanding is that their result doesn't affect bounds for fixed-size SHA3 primitives. But other sponge constructions might benefit from their tighter bounds. I also haven't evaluated the SHAKE family. Jan 4 at 17:01
• @MarcIlunga: your second comment seems to be what Q1 asks, and is worth an answer! The results in the article increase the proven preimage resistance for some notable sponge-based hashes, but not for $\operatorname{SHA3-}d$ (that can't be: it's already at the brute-force threshold without considering the hash structure). However I don't know for $\operatorname{SHAKE}n$ and $d>n=c/2$. Further, Q2 asks if we could lower $c$, not if we could increase the proven preimage resistance.
– fgrieu
Jan 4 at 17:59