I have always heard that

A change in just one bit of the original text shall change half of the bits of its hash.

I think this property is called the diffusion property.

However, I wonder why the diffusion property is so important in hashing functions.

I understand that for encryption algorithms this is a needed property. Without it, an attack based on language stats could be carried out.

Hashing functions however are one-way, which means that you can not get the original text from the hash. Why should hash functions exhibit the diffusion property then?

Update 1:
Given that you could use hashing functions for hiding information or for assuring the integrity of a document, I think it is a good idea to separate both aspects.

If we are using it for hiding information such as password this property in needed. Look at Lucas Kauffman's answer.

But if you are using hash functions to guarantee the integrity of a document. Is it still a needed property then?


It is for the same reason, suggest you have a table with hashes, and you find out that there is one hash (A) that's almost the same as a hash you are trying to break (B). If there is randomization then you have nothing, otherwise you know that the hash you are trying to break is similar to the plain text of hash A. So this would make a bruteforce attack easier since you know it must be a hash of something close to the plaintext of A.

Add to this that you might have 10 hashes that look similar to B, you can start finding a pattern in their plaintext form and reduce your bruteforce span even more.

|improve this answer|||||
  • But if you are using the hashing function just to guarantee the integrity of a document. Is it needed? – eversor May 6 '12 at 13:23
  • if it's for integrity only, maybe then not, but I'm not sure. – Lucas Kauffman May 6 '12 at 13:32

Hash functions are used in many places, and some of them require more than collision and preimage resistance.

A few examples:

  • As a pseudo-random function in key derivation. Obviously the key should be as random as possible.
  • As a padding in RSA. The security proofs are based on the random oracle model. So we want our concrete hash functions to come as close as possible to a random oracle
  • Truncated hashes should still have the same security properties as a full hash (apart from the inherent weaknesses of a shorter hash output).
  • Hash functions can be used in a CTR mode like construction to create a stream cipher. Obviously this requires unbiased, random looking output
  • Hash functions can be used as a PRNG, similar requirements as for stream ciphers
|improve this answer|||||

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.