4
$\begingroup$

Why cryptographic hash functions must be collision-free and is there any methods to evaluate whether a function is not resistant to collision?

Thanks,

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

If a hash function is not collision-resistant (there is no such thing as collision-free in hash functions because their output has a fixed length) then an adversary can break the function with little effort. More formally (but still quite informally):

You have a set $X$ of possible inputs. For each input $x \in X$ the hash function $F$ will output $h=F(x)$. Note that there are more than one $x$ that will give the same $h$ as a result, and the set of all possible results of $F$ is finite, unlike $X$. The function's job is to make it hard for the attacker to find any $x'$ so that $F(x') = F(x) = h$.

Edit: I also found this question which is relevant to this one

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The main argument is valid only if "break the function" is defined in term of collision resistance, and then it is a circular argument. There are uses of a hash function where collision-resistance is not a required property; e.g. in HMAC, see this. +1 nevertheless for the distinction between collision-resistant and collision-free. $\endgroup$
    – fgrieu ♦
    May 31, 2013 at 17:30
  • $\begingroup$ A cryptographic hash function is defined as a hash function (fixed output length) which is collision resistant and pre-image resistant. I do not see any circular arguement. If HMAC need a cryptographically hash function or not is entirely irrelevant. $\endgroup$
    – tylo
    Jun 4, 2013 at 9:33
  • 1
    $\begingroup$ Though I agree that there is no such thing as collision-free regarding hash functions, I would disagree that hash algorithms are still constrained to fixed length outputs. Check these out for more details. $\endgroup$
    – JZeolla
    Jun 5, 2013 at 17:16
7
$\begingroup$

An example may help demonstrate why collision resistance is important.

Hash algorithms are often used for computing digital signatures. The signer of a message runs the original message through a hash algorithm to produce a digest value, then encrypts the digest to produce a signature. Someone verifying the signature will run the message through the same hash algorithm, and will decrypt the attached signature value to ensure the digest it contains matches the one they computed.

If collisions are easy to find, they allow an attacker to take an authentic digitally signed message, find a different message that produces the same digest (the collision), then substitute the fake message for the real one while keeping the same signature value. Someone trying to validate the signature won't be able to tell the difference. This destroys the value of digital signatures.

Testing is difficult. You can apply chi-squared tests and look for uneven digest bit distributions over a wide number of single- and multi- bit changes, but that's not proof. Most of the strength relies on the algorithm's resulting digest size being large enough to mask any undiscovered weaknesses.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The description of digital signature is valid for some signature schemes; and there are other uses of hash algorithms where collisions would be a problem. The argument remains excellent. $\endgroup$
    – fgrieu ♦
    May 31, 2013 at 17:27
  • $\begingroup$ @fgrieu, I wanted to give an illustrated example. Because any hash function could be used this way, it is important that the chosen one has the property of collision resistance. $\endgroup$
    – John Deters
    May 31, 2013 at 22:22
  • 1
    $\begingroup$ Another note: signature schemes do not "encrypt the digest"; they apply some secret cryptographic function, which is not encryption, to the digest. In RSA signature with appendix (RSASSA), the function happens to be the composition of a public "padding" function, and the function $x\mapsto x^d\bmod N$, known as textbook RSA decryption (not encryption). $\endgroup$
    – fgrieu ♦
    Jun 1, 2013 at 10:50
  • $\begingroup$ The question was for hash functions and collision resistance, not for digital signatures. $\endgroup$
    – tylo
    Jun 4, 2013 at 9:22
  • 2
    $\begingroup$ The question was "why is collision resistance important?" A simplistic digital signature explanation serves as a example of a system that doesn't work if it's not collision resistant. I'll clarify the answer a bit. $\endgroup$
    – John Deters
    Jun 4, 2013 at 14:41
2
$\begingroup$

I am not sure that I have understood the question, but to complete the first answer, if a hash function was not collision resistant, we could find multiple messages which produce the same hash and sign this resulting digest. So a practical interest of such a property is for the use of a hash function in a signature scheme.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well we can still find multiple messages that produce the same signature, the question is how hard is it to do so? That's where the 'resistant' bit becomes relevant $\endgroup$
    – rath
    May 31, 2013 at 12:12
  • $\begingroup$ Beside the difficulty of finding a collision or preimage, "hash and sign" is just one application of hash functions. The question seems to be more general, as "why do you need this stuff at all?" $\endgroup$
    – tylo
    Jun 4, 2013 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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