16
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ en.wikipedia.org/wiki/Collision_resistance $\endgroup$
    – D.W.
    Feb 6 '17 at 4:54
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Foerster
    Feb 6 '17 at 11:10
  • 4
    $\begingroup$ 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. $\endgroup$
    – Eric Lippert
    Feb 6 '17 at 16:17
  • $\begingroup$ resistance is futile $\endgroup$
    – Jodrell
    Feb 6 '17 at 16:27
38
$\begingroup$

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.

However, the term "collision resistance" denotes something different from what you seem to think: It just means that collisions are hard to find, in a computational sense. We expect from a good hash function that nobody is able to find two inputs that lead to the same hash value, but we do not care about their abstract existence, which is a necessary evil.

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')$.

Improve this answer
$\endgroup$
3
  • 12
    $\begingroup$ And here, "nobody should ever find" means "it would take a very, very long time", because given enough time and computing power, you can find just about anything. Except things that don't exist, like my social skills. $\endgroup$
    – Nic
    Feb 6 '17 at 4:28
  • 12
    $\begingroup$ To put it simply, "collision resistant" means there's no way of finding collisions that is faster than simply guessing at random. $\endgroup$
    – Mark
    Feb 6 '17 at 8:39
  • 1
    $\begingroup$ Some of the most widely used hash functions have a length field of 64 or 128 bits, which means the input length is theoretically bounded, but in practice that doesn't really matter. $\endgroup$
    – kasperd
    Feb 6 '17 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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