Breaking effort on both Weak and Strong collision resistance hash values I know the fact that the effort of brute force attack to break weak collision resistance hash value takes $2^n$ while in the strong collision resistance takes $2^{n/2}$. Can someone explain why strong collision resistance takes less effort?
Basically strong collision resistance means you can't find any pair $(x,x')$ for which $h(x)=h(x')$ holds.

Weak collision resistance means that you can't find any $x'$ for all given $x$ such that $h(x)=h(x')$ holds.



To break strong collision resistance an obvious strategy is to just list a large chunk of hashes and see for any matches among them.

For weak collision resistance the obvious strategy is to take your $x$ and iterate through other potential candidates until you hit a new $x'$ which is a collision.

Obviously the former approach will lead to results before the latter.



Another illustration (which is less definition or attack-centric) is the classic one of birthdays.

Weak collision resistance essentially corresponds to finding somebody who has the exact same birthday as you have. For this you probably need to find around 200 people before chances are that you'll get a match.

Strong collision resistance on the other hand means that you meet people until any of two of them have a matching birthday. You expect this to happen with $&gt;50\%$ probability after around 23 people.