Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm trying to learn about sponge function for creating hash functions and generic attacks on it.

I'm looking for the collision finding attack scenario which leads to $O(\min(2^{-n/2} , 2^{-c/2}))$ time complexity, where $n$ is the sponge output length(hash output length) and $c$ is the capacity length of sponge state.

I know that $2^{-n/2}$ comes from a traditional birthday attack on the output, but what is the attack scenario for $2^{-c/2}$ complexity?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

Denote the internal sponge state by $$ S = R||C, $$ where C has size c -- capacity.

Every iteration a message block of length $|R|$ is xored into $R$ and then the permutation $P$ is applied. Therefore, if we obtain a collision in $C$ (which can be obtained in $2^{c/2}$ steps with the basic birthday attack), we could cancel any difference in $R$ by injecting an appropriate pair of messages.

So, if $(M_1,M_2)$ yields a zero difference in $C$ and difference $\Delta R$ in $R$, the pair $$ (M_1||X,M_2||(X\oplus \Delta R)) $$ is a collision pair for the full function $F$ for any $X$.

share|improve this answer
Thank you Dmitry Khovratovich, Just please edit your post for beginners like me, that you can find collision in $2^{\frac{c}{2}}$ complexity because of the generic birthday attack. thank you for your great answer again :) –  Shnd Jan 2 at 17:07
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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