3
$\begingroup$

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.
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Jan 4 at 13:53
  • 1
    $\begingroup$ 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) $\endgroup$ Jan 4 at 16:42
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 4 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 4 at 17:01
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jan 4 at 17:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.