The importance of weak collision resistance is best understood in the
context of digital signatures, which are used to create legally
binding digital contracts proving who signed what. Without going into
details of digital signatures right now, it is sufficient to know that
the contract’s text is a message M and that digital signatures on M
are created from the cryptographic hash value H(M).
Suppose Alice and Mallory agree that Mallory buys Alice’s used car for
20,000€. Both digitally sign the contract’s message M. However,
Mallory changes his mind and does not want to buy the car any longer.
If hash function H is not weakly collision resistant, Mallory may be
able to create a second contract M’ which includes the price of 1€ for
Alice’s car such that H(M) = H(M’). In this situation, as digital
signatures are derived from hash values, the digital signatures of
Alice and Mallory created for M are also valid for M’. Thus, Alice
has no proof that Mallory signed M in the first place.
So: If a message M is given, nobody should be able to create a second
message M’ with the same hash value under weak collision resistance.
For strong collision resistance, nobody should be able to create any
collision at all, even if those collisions only occur for messages
that look like gibberish without practical value.
A different angle on collision resistance is provided by the following
birthday analogy. Consider the hash function mapping each person to
his or her month and day of birth. Essentially, there are 366
different hash values (including February 29), and a collision occurs
when two people share the same birthday.
Suppose you are in class. When you wonder whether some of your fellow
your birthday, you consider weak collision
resistance. In contrast, when you ask whether any pair of students
shares the same birthday, you consider strong collision resistance.
For simplicity, ignore leap years and consider just 365 different
birthdays, all with the same probability. I’m confident that for a
class of 30 students you can compute the probabilities of
(a) somebody sharing your birthday as well as
(b) any pair sharing a common birthday.
If you do the math for the first time, you may be surprised by the
high probability in case (b), which is known as the birthday paradox
(whose essence is the fact that the number of pairs grows
quadratically, about which you can read more at Wikipedia).
As the probability of case (b) is larger than that of case (a), it is
harder to defend against case (b). Thus, hash functions targeting
strong collision resistance must be “stronger” than those offering
weak collision resistance.