Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by D.W., DrLecter, figlesquidge, Gilles, e-sushi May 21 '14 at 13:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

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