# 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\mathbin\|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\mathbin\|X,M_2\mathbin\|(X\oplus \Delta R))$$ is a collision pair for the full function $$F$$ for any $$X$$.