12
$\begingroup$

I was wondering if the uniform distribution of hash values is a generally required criteria for cryptographic hash functions.

The english wikipedia article only mentions four main properties. But it looks like the commonly used algorithms show a nearly perfect uniform distribution. So my question(s) would be:

  • Are hash functions supposed to have uniform distributed values?
  • (If so) Is it an explicit requirement or an implication of the second and last property mentioned by wikipedia (irreversibility + collision resistance)?
  • Are there any hash functions, currently used, that do not show such distribution?
  • Is there a scientific paper or article addressing this issue? (Unfortunately I was unable to find one)
Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
9
$\begingroup$

The idea of a hash function is the idea of a random Oracle. For any given input, this Oracle should return a truly uniformly random output. This is ideal of how hash functions work, so any hash function that isn't uniformly random is not behaving the same way as a random Oracle. So yes, hash functions should have uniformly distributed values.

I don't believe it's necessarily an explicit requirement to be uniform, but not being uniform would certainly weaken the strength of the hash. For example, if the hash was a 'normal' distribution, certain outputs would be far more common than other. We could get collisions far easier then.

I'm unfamiliar of any cryptographic hashes attempting to reach a non-uniform distribution as I imagine they would be more vulnerable to collisions and preimage attacks. If you were so inclined, you could hash the values with a known uniform distribution use the output in a non-uniform distribution function.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. That's what I thought. Do you happen to know a source or scientific paper addressing this issue? Unfortunately I did not found any. $\endgroup$
    – masinger
    Mar 4, 2016 at 18:54
  • $\begingroup$ @azarinak “but not being uniform would certainly weaken the strength of the hash “ is not quite true. The strength of a hash is the number of output permutations only. SHA-1 produces ~ 10^48 (256^20) permutations with a uniform distribution. A Pearson hash of 21 octets produces ~10^50 (binomial formula) permutations with a binomial distribution. In summary, a uniform distribution is not a requirement, it's just the most efficient (read shortest) output. $\endgroup$
    – Paul Uszak
    May 17, 2016 at 13:51
  • $\begingroup$ A hash does not produce a permutation, it produces a psuedo-random distribution of values. And if you have a hash with 2^n possible outputs where certain outputs are more likely than others, an attacker would simply find collisions of the higher frequency values. It is easier to break a random binomial distribution than a uniform distribution of the same bit length. $\endgroup$
    – Azarinak
    Jun 1, 2016 at 2:39
  • $\begingroup$ @Azarinak The question does not say anything about identical bit lengths though. So in fact 10^50 > 10^48. $\endgroup$
    – Paul Uszak
    Jul 21, 2016 at 23:37
4
$\begingroup$

I agee with @Azarinak but to expand upon his answer a bit: all hashing functions contain collisions - infact an infinite number of collisions. That is merely a feature of taking an input of potentially infinite length and producing a fixed length output. But despite that fact, one major purpose of a hash function is still to minimise collisions, and the best way to do that is to have the output uniformly distributed.

One might think that a hash function which avoided certain outputs would succeed at producing a non-uniformly distributed output without increasing the number of collisions. However that would be incorrect - the reason being that for every output not "used up" another one must be used more frequently (remember the number of possible inputs to the hash function is infinite).

A hash function of infinitely many bits would circumvent the normal-distribution requirement. However, a requirement of a hash function is for it to produce a fixed length output, so such a function would not technically be a hash function.

Finally, there are a few different Wikipedia pages discussing hash functions and one of them says this:

A good hash function should map the expected inputs as evenly as possible over its output range. That is, every hash value in the output range should be generated with roughly the same probability.

https://en.m.wikipedia.org/wiki/Hash_function

Improve this answer
$\endgroup$

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.