I prefer using definitions that explicitly specify who does what.
Weak collision resistance: After Bob creates some message x1, it is "computationally infeasible" for an attacker Mallory to compute some other message x2 such that h(x1) == h(x2).
Strong collision resistance: It is "computationally infeasible" for an attacker Mallory to find any two messages x1 and x2 such that h(x1) == h(x2).
The negations would be:
Weak collision vulnerability: After Bob creates some message x1, it is "computationally feasible" for an attacker Mallory find a bound collision -- to compute some other message x2 such that h(x1) == h(x2).
Strong collision vulnerability: It is "computationally feasible" for an attacker Mallory to find a free collision -- to find any two messages x1 and x2 such that h(x1) == h(x2).
Specific examples:
- The "XOR checksum" (and each non-cryptographic hashe in general) is weak collision vulnerable -- and therefore is strong collision vulnerable.
- The MD5 hash is now known to be strong collision vulnerable, but (as far as we know) it still has weak collision resistance.
- The SHA3 hash (as far as we know) has strong collision resistance -- and therefore also has weak collision resistance.
Strong collision resistance implies weak collision resistance, in the random oracle model,
as Vijay Ganesh points out in
"Cryptographic Hash Functions".
(Vijay apparently thinks the term "infeasible" is useful in this context).
Klaus Schmeh apparently made up the "bound collision" and "free collision" terminology for the book "Cryptography and Public Key Infrastructure on the Internet".
Therefore,
weak collision vulnerability implies strong collision vulnerability, in the same model.
One might argue that strong collision vulnerability implies weak collision vulnerability:
After Mallory creates two messages x1 and x2 that collide,
it is theoretically possible that Bob might create a message exactly the same as x1, and then Mallory could easily remember the x2 message that Mallory generated earlier.
In practice, any protocol where Mallory influences Bob into using a message generated by Mallory (a chosen-plaintext attack) is already considered broken in other ways.
In practice, we assume that, without such influence, the probability that Bob coincidentally picks such a message generated by Mallory is negligible.
I suspect otus is alluding to the fact that people who work with keyed hash functions have their own definitions for these terms that are incompatible with the definitions used by people who work with unkeyed hash functions.
Shoichi HIROSE mentions this conflicting terminology in the introduction of his 2005 paper "Weak Security Notions of Cryptographic Unkeyed Hash Functions and their Amplifiability".
