# Why has the sponge construction's generic collision finding attack a complexity of O(min(2^(-n/2) , 2^(-c/2)))?

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?

-

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$.