16

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?

yyyyyyy
  • 12,081
  • 4
  • 47
  • 68
QWASH
  • 171
  • 1
  • 4
  • https://en.wikipedia.org/wiki/Collision_resistance – D.W. Feb 06 '17 at 04:54
  • 2
    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 06 '17 at 11:10
  • 4
    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 06 '17 at 16:17
  • resistance is futile – Jodrell Feb 06 '17 at 16:27

1 Answers1

38

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

yyyyyyy
  • 12,081
  • 4
  • 47
  • 68
  • 12
    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. –  Feb 06 '17 at 04:28
  • 12
    To put it simply, "collision resistant" means there's no way of finding collisions that is faster than simply guessing at random. – Mark Feb 06 '17 at 08:39
  • 1
    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. – kasperd Feb 06 '17 at 22:02