7
$\begingroup$

So I understand the two concepts:

  • (Strong) collision resistance: it is infeasible to find a pair $x \neq x'$ such that $h(x) = h(x')$
  • Weak collision resistance / 2nd-preimage resistance: for all $x \in D$ it is infeasible to find $x' \neq x$ such that $h(x)=h(x')$

But I'm confused as to how to negate the two. This is what I end up with:

  • h is not (strongly) collision resistant if: it is feasible to find a pair $x \neq x'$ such that $h(x)=h(x')$
  • h is not weakly collision resistant (not 2nd-preimage resistant) if: there exists $x \in D$ such that it is feasible to find $x' \neq x$ such that $h(x)=h(x')$

These two negations seem the same. Suppose I show h is not (strongly) collision resistant, because of $x \neq x'$ where $h(x)=h(x')$. Surely this then shows h is not weakly collision resistant when the $x \in D$ is $x$ or $x'$? (sorry for the different uses of $x$ there!) A similar argument would say that any $h$ that is not weakly collision resistant is strongly collision resistant. But it's absurd that the negations of the two concepts are the same! Where have I gone wrong?

$\endgroup$

3 Answers 3

8
$\begingroup$

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".

$\endgroup$
1
  • 1
    $\begingroup$ One doesn't need a random oracle to get "Strong collision resistance implies weak collision resistance". $\;\;\;\;\;$ $\endgroup$
    – user991
    Sep 17, 2014 at 11:40
2
$\begingroup$

First, I must warn you that any definition that uses "feasible" will not be a rigorous one. The only way I know to rigorously define collision and preimage resistances is using function families, i.e. keyed hash functions.

That said, if you believe the negations are equivalent, the definitions you are using are themselves equivalent (you correctly negated them). You could fix this by replacing "for all $x$" with "for almost all $x$". The fact that you know one pair $h(y) = h(y')$ doesn't break second preimage resistance for an arbitrary $x$.

The key here is that in (strong) collision resistance both $x$ and $x'$ are under the attacker's control. In weak collision resistance, i.e. second preimage resistance, $x$ is given "randomly".

$\endgroup$
0
$\begingroup$

I think your two negations are not the same, here is my reasoning:

The existence of a $x \in D$ for which it is feasible to find a second pre-image (the second negation), does not guarantee that it is feasible to find that $x$. Therefore, the second negation does not immediately imply the first.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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