Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

Thanks,

share|improve this question
add comment

3 Answers 3

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

share|improve this answer
1  
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. –  fgrieu May 31 '13 at 17:30
    
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. –  tylo Jun 4 '13 at 9:33
    
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. –  Steel City Hacker Jun 5 '13 at 17:16
add comment

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.

share|improve this answer
    
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. –  fgrieu May 31 '13 at 17:27
    
@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. –  John Deters May 31 '13 at 22:22
1  
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). –  fgrieu Jun 1 '13 at 10:50
    
The question was for hash functions and collision resistance, not for digital signatures. –  tylo Jun 4 '13 at 9:22
1  
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. –  John Deters Jun 4 '13 at 14:41
add comment

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.

share|improve this answer
    
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 –  rath May 31 '13 at 12:12
    
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?" –  tylo Jun 4 '13 at 9:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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