3
$\begingroup$

I was looking at the security level of instances of sponge construction on Wikipedia depicted in the following image. enter image description here It seems to me that the security level for collision resistance follows the formula $\min(d/2,c/2)$ while for the preimage it is $\min(d,c/2)$. Can somebody explain why it is the case, please? I mean why do both have c/2 but one is d/2 and the other d?

$\endgroup$

1 Answer 1

1
$\begingroup$

I believe the discrepancy is due to some counter-intuitive properties of the sponge.

The collision resistance property of sponges comes from how the permutation $\pi(S)$ randomizes arbitrary inputs, that may be controlled by an adversary, onto a small image space. The adversary can either freely adjust inputs until a collision within the capacity section is found, where then the subsequent call to $\pi$ is fully controllable, giving $d = \pi(S')_{[0...d-1]} = \pi(S)_{[0...d-1]},$ $S' \not = S, S' = R'||C', C' = C$; Or, the adversary finds the more intuitive collision on the output bits given any $S' \not = S$. The easier of the two tasks determines collision resistance.

The preimage resistance property on the other hand, is essentially boiled down to the one-wayness of the hash, e.g. how hard it is to find any $x'$ given $d = h(x)$. If no collision on $C$ is found, then the adversary doesn't have complete control over the evaluation of the permutation $\pi(R'||k)$ with $k = C$, and the resistance is measured by the difficulty of replicating a $|d|$ sized output. However, if a collision on $C$ is found, both $\pi$ and $\pi^{-1}$ can be completely under the control of an adversary, so intermediate states performed when processing a chosen input $x'$ can be made to match other discovered intermediate states of inputs $x^*$ to produce matching $h(x) = h(x') = h(x^*)$. Then, the resistance against inversion of $h(x)$ into viable matching $x^*$ is directly related to the collision resistance of the capacity. The easier of the two tasks here determines preimage resistance.

$\endgroup$
1
  • 1
    $\begingroup$ Adding to this, you can see these arguments in a little more detail in section 5 of the original sponge function paper keccak.team/files/SpongeFunctions.pdf $\endgroup$
    – rozbb
    Aug 8, 2023 at 2:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.