I am studying a function where I found the some hash properties.

Hash functions:

  1. Given a code c is computationally infeasible to find m such that h(m) = c
  2. Given m is computationally infeasible to find n != m such that h(m) = h(n)
  3. It is computationally infeasible to find any pair (m, n) such that h(m) = h(n)

Actually every point is clear to me. But I wondering what is the difference between point 2 and point 3? Can anyone give me any clue? Thanks.


For cryptographic hash functions, there are the 3 definitions of collision resistance, (first) preimage resistance and second preimage resistance.

Number 3 is collision resistance, and it is quite different than No. 1 and No. 2, which is due to the birthday problem (also see birthday attack).

In No. 1 and 2, the resulting hash value is fixed (once directly and once indirectly due to a fixed element as input to the hash function). In No. 3 however, you just have to find two elements with the same hash value. So you start by hashing two elements and the hash value has $n$ bits. The chance that they are equal is $1/2^n$. Now you hash a third value. The probability that it is equal to either the first or second value is $2\cdot(1/2^n)=1/2^{n-1}$, the next element has a chance of $3\cdot(1/2^n)\approx 1/2^{n-1.6}$, and so on.

In average (and this is a very rough estimate) you can find a collision after $2^{n/2}$ hashed values. For No.1 and No.2, you need to test in average $2^{n-1}$ values.

Btw, No.1 is (first) preimage resistance and No.2 is second preimage resistance. The difference between these two is less obvious, but you can create toy examples with preimage resistance but no 2nd preimage resistance. For example:

Why doesn't preimage resistance imply the second preimage resistance?

Pre-image resistant but not 2nd pre-image resistant?

The second thread also lists a function which is 2nd preimage resistant but not fully preimage resistant, but that is a very specific example and probably goes too far for your questions.

| improve this answer | |

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