# If a hash function $H$ is collision resistant, is it true that $H(x)\neq H(x')$ for all messages $x, x'$ with $x \neq x'$?

I am puzzled with a question that seems to be based on theory.

If there is a collision resistant hash function (since it is not possible for a hash function to be collision free, this is a theoretical question), would it be true to say that there are no two unique hash values for all possible messages $x$ and $x'$ where $x\neq x'$?

I feel like this would be true... Can anyone back me up on this?

• en.wikipedia.org/wiki/Collision_resistance – D.W. Feb 6 '17 at 4:54
• Without looking at the definition you can make an initial guess based on the common meaning of the word "resistant" which doesn't mean "free of" or "immune from". Resistance makes an action harder not impossible. – David Foerster Feb 6 '17 at 11:10
• Your question in the title is "is it true that if H is collision-resistant, that it is also collision-free?", and you then go on to say in the body that no H is collision free. So you know the answer to your question: no. – Eric Lippert Feb 6 '17 at 16:17
• resistance is futile – Jodrell Feb 6 '17 at 16:27

As you correctly observed, for any function $$H\colon \{0,1\}^\ast\to\{0,1\}^n$$ collisions must exist, simply because $$\{0,1\}^\ast$$ is an infinite set and $$\{0,1\}^n$$ is finite. One could define "hash function" to mean something else (e.g., taking only a bounded input length), but this is non-standard.
Thus, no: Collision resistance does not mean that $$H(x)\neq H(x')$$ for any $$x\neq x'$$. It rather means that practically, nobody should ever find $$x\neq x'$$ with $$H(x)=H(x')$$.