11

I am studying the subject from these notes. However it is not clear what is the difference between "Second Pre-image Resistance" and "Collision Resistance" properties of Cryptographic Hash Functions.

As the notes say at "Second Pre-image Resistance", given x1 it is computationally infeasible to deduce x2 such that h(x1) = h(x2). What is the relation between x1 and x2 here?

At "Collision Resistance", it is computationally infeasible to find a x1 != x2 such that h(x1)=h(x2). Is that a sub-case of "Second Pre-image Resistance", where x1 != x2?

Could you clarify the difference between these two?

Michael
  • 213
  • 2
  • 4
  • Their definition of second pre image resistance is impossible to achieve. –  Oct 10 '14 at 18:41

2 Answers2

15

Collision resistance is about the infeasibility of finding two distinct inputs m and m' such that h(m) = h(m'). The attacker gets to choose m and m' arbitrarily, as long as he ends up with two distinct messages that hash to the same value.

Second-preimage resistance is very similar except that the attacker does not get to choose m. Instead, we give him m, and challenge him with finding m' (distinct from m) such that h(m) = h(m').

A second-preimage is also a collision, but we keep the concept distinct because second-preimages are supposed to be substantially harder. If the hash function has an output of n bits and is "perfect" (no known weakness), then the cost of finding a collision is 2n/2, while the cost of finding a second-preimage is 2n (i.e. a lot more).


Suppose that we are talking about signatures. Since a signature algorithm begins by hashing the data that is to be signed, and then works only with the resulting hash value, then it follows that if h(m) = h(m'), then a signature s on message m will also be a valid signature on message m'. The goal of the attacker is to forge a signature, i.e. get a signature that seems valid on a message of his choosing.

If the attacker sees a valid, signed message m, then he may want to find a message m' that hashes to the same value. This is the second-preimage model. For the signature system to be robust, the hash function must provide second-preimage resistance.

Collision resistance, on the other hand, is not necessary in that case. It is necessary, though, with another model where the attacker can obtain a signature on a message m that looks innocent, and wants that signature to be also valid on a message m' with less benign contents. For instance, I am the attacker and I send you a contract where you promise to send me 1$. However, I crafted that contract m such that it collides (hashes to the same value) with a slightly different contract m', where you promise to send me 1000000$. If I can get you to sign the first contract, then, thanks to the collision, your signature also applies to the second one (and you lose).

Thus, collision resistance and second-preimage resistance are two distinct concepts, and what you need depends on the context. In the case of signatures, you need at least second-preimage resistance; but if the context is such that the attacker can obtain signatures on data that he chooses, then collision resistance is also needed. This has been demonstrated with MD5 as the hash function, and X.509 certificates (mind the details: the collision attack on MD5 could be applied to certificates because the researchers found a CA that generates certificate serial numbers in a predictable way).

Tom Leek
  • 170,038
  • 29
  • 342
  • 480
4

Second pre-image resistance simply has more constraints than collision resistance.

In your examples, x1 and x2 are the inputs, and h(x1) and h(x2) are the outputs.

For second pre-image resistance, you are given x1, and must find an input (x2) that hashes to the same output value. You do not get to choose x1 in this attack.

There is no such constraint for collision resistance. You are free to choose both x1 and x2 in an attempt to find a collision of the outputs.

Xander
  • 35,616
  • 27
  • 114
  • 141