Surely there can be no real collision resistant Hash function since hash values are of finite size which means there are finitely many of them, but there are an infinite number of messages we could hash, which means (using the pigeon-hole principle) that some messages must lead to the same hash value.


marked as duplicate by otus, e-sushi Apr 24 '16 at 8:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ Collision resistance does not mean that no collisions exist (as you correctly observed, they do for any useful hash function), but that those are (computationally) hard to find. $\endgroup$ – yyyyyyy Apr 23 '16 at 13:18

Collision resistance relates to how difficult it is to find a collision, not the total lack of collisions. In other words, a hash function $H(x)$ is collision resistant if and only if all attackers given reasonable computational resources (probabilistic polynomial algorithms) have only a negligible chance of finding two messages, $m_0$ and $m_1$ such that $H(m_0)=H(m_1)$.

Note that this is not an information theoretic type of security - an attacker given unlimited computational resources will always be able to find a collision (or as many collisions as desired). It is possible to get information theoretic security from something like a one-time MAC (where even an unlimited attacker has only a negligible chance of devising two messages with the same MAC tag), but that relies on a secret key used only once, whereas in a hash function nothing is secret.


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