4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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 $>50\%$ probability after around 23 people.

| improve this answer | |
$\endgroup$
0
$\begingroup$

It might be easier to consider the birthday problem first. Consider the following problems:

Problem 1: What is the number of people needed to find someone with the same birthday as you with probability > 0.5?

Problem 2: What is the number of people needed to find any two persons that have the same birthday with probability > 0.5?

These two are very well-known problems. The answer to the first is 253 persons, while the answer to the second is 23 persons. Two important questions to ask here are: 1) How many comparisons do you need to find a match to you in the first case, and 2) how many comparisons do you need to find a pair of people with the same birthday in the second case. Let us take them one by one:

1) To find a match to you, you need to compare yourself with the other 253 persons, which means you need to make 253 comparisons.

2) To find a pair with the same birthday, you need to compare pairs from the 23 persons. Therefore you need to make (23 choose 2) = (23 x 22)/2 = 253 comparisons too.

You can see that the same number of comparisons is needed in both cases. In the first case, more persons are needed because you are comparing to one reference (yourself). However, in the second case, a fewer number of people is needed to produce the same number of comparisons because you are comparing all possible pairs.

When talking about hash functions, the effort of comparison is negligible when compared to the effort of computing a hash. So what matters here is not the number of comparisons you make (which is the same in both cases), but the number of values you need to compare. This number is much smaller ($2^{N/2}$ values) if you are looking for pairs (in strong collision resistance) rather than comparing to a known reference value (in weak collision resistance which needs $2^N$ values).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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