1

I'm struggling to get a clear understanding of second preimage resistance and collision resistance.

Research on the internet yielded the following definitions:

Second pre-image resistance

Given an input m1, it should be difficult to find a different input m2 such that hash(m1) = hash(m2). Functions that lack this property are vulnerable to second-preimage attacks.

Collision resistance

It should be difficult to find two different messages m1 and m2 such that hash(m1) = hash(m2). Such a pair is called a cryptographic hash collision. This property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as that required for pre-image resistance; otherwise collisions may be found by a birthday attack.

As far as I understand, every collision resistant hash function is also second pre-image resistant.

I don't understand why collision resistance is harder to achieve, given that input m1 of second pre-image resistance could still be theoretically any input in the domain of the hash function.

Fang
  • 113
  • 5

1 Answers1

4

I don't understand why collision resistance is harder to achieve,

With a second-preimage attack m1 is given and one has to find a m2 with the same hash value.

With a collision attacks one can instead choose both m1 and m2 which gives more freedom on how to attack the problem - and thus can make the problem easier. One could for example start with a common source and then use an algorithm which modifies the source in two ways but keeps the resulting hash value the same, i.e. create different m1 and m2 which have the same hash value.

Steffen Ullrich
  • 190,458
  • 29
  • 381
  • 434
  • Does that make sense? You say a preimage attack is harder, yet collision resistance is harder to achieve. Maybe I'm missing something... – Fang Nov 03 '18 at 20:03
  • 3
    @Fang: The preimage attack is harder to do which means that resistance against preimage attack is easier to achieve. The collision attack is easier to do which means that resistance against collision attack is harder to achieve. – Steffen Ullrich Nov 03 '18 at 20:04