# Hash in set probability?

First off I would like to mention that I am absolutely terrible at statistics... so bear with me please.

## The question:

a sha1 hash is a hexadecimal string of 40 characters, the largest number being:

ffffffffffffffffffffffffffffffffffffffff


which if you convert it to a decimal, it becomes around 1.2830013993246E+48.

I don't know what the exact value is or how to obtain it, but lets say that it is X.

What is the probability that X number of unique strings when hashed with the sha1 algorithm will have every single possible character combination of a sha1 string?

And does this apply for other hashing algorithms too??

Basically is a sequence of 2^160 unique strings guaranteed to generate every possible combination of a sha1 hash?

P.S. if someone has a better title for this question it would be much appreciated, also I am unsure if this is the best place to ask this :/

• This might be better on stats.SE.
– Dan
Commented Dec 18, 2013 at 0:05
• @Dan might be, how to move? Commented Dec 18, 2013 at 7:41
• You got good answers here, so moving's probably not a good idea. The usual way to move is to copy your question and paste it into another site's "ask a question" page, then delete the original question.
– Dan
Commented Dec 18, 2013 at 18:08

Basically is a sequence of 2^160 unique strings guaranteed to generate every possible combination of a sha1 hash?

No, there is almost no chance. The probability is some double exponential like exp(-exp(100)).

Say that by some miracle you have seen no collision among your first 2^160 - 1 unique strings. Then your last unique string will still have about a (2^160-1)/(2^160) probability of hashing to a sha1 value that you have already seen.

• Specifically, Sterling gives $$p = \frac{n!}{n^n} \approx \sqrt{2\pi n} e^{-n}$$ where here $n = 2^{160}$. Commented Dec 25, 2013 at 1:27

The probability is zero, because X is less (by one) than the number of possible character combinations of a sha1 string.

• Why is it less by one? (sorry if this sounds stupid) Commented Dec 17, 2013 at 7:45
• @timo because 0, ..., fff...f is a sequence of fff...f + 1 things. If you replace fff...f hex in your question with 99 dec then maybe this will be clearer?
– k20
Commented Dec 17, 2013 at 16:03
• yes the 99 makes it clearer, thank you Commented Dec 17, 2013 at 19:06

If you repeatedly select elements from a bin with $n$ objects, replacing the objects each time, the expected time to select each element at least once is $$E = n \left(\log n + \gamma + o(1)\right).$$ For $n = 2^{160}$, this is $1.6 \times 10^{50}$.

To see this, note that the probability of choosing a new object if $k$ elements are already chosen is $(n-k)/n$. Summing gives $$E = \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{k=1}^n \frac{1}{k} = n H_n$$ where $H_n$ is the $n$th harmonic number.

• is the sha1 hash really a bin of 2^160 unique objects? Commented Dec 17, 2013 at 7:43
• Hashing algorithms are design in such a way that they map random objects to random hashes with uniform probability density in the hashes if the objects are uniformly distributed in input space, at least approximately. If this was true exactly, then the hash outputs are indeed just selecting from a bin. Of course, a hash is not ideal. Does your question pertain to SHA1 in particular, or are you just interested in hashes in general? Commented Dec 17, 2013 at 7:59
• @WolfgangBangerth hashes in general, I just picked sha1 because I heard that it was better than say md5 Commented Dec 17, 2013 at 15:00