Are collision-resistant hash functions even possible? [see description] [duplicate]

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.

• 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. – yyyyyyy Apr 23 '16 at 13:18

1 Answer

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.