2
$\begingroup$

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 :/

$\endgroup$
  • $\begingroup$ This might be better on stats.SE. $\endgroup$ – Dan Dec 18 '13 at 0:05
  • $\begingroup$ @Dan might be, how to move? $\endgroup$ – Timo Huovinen Dec 18 '13 at 7:41
  • $\begingroup$ 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. $\endgroup$ – Dan Dec 18 '13 at 18:08
2
$\begingroup$

To answer your edit...

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.

$\endgroup$
  • $\begingroup$ Specifically, Sterling gives $$p = \frac{n!}{n^n} \approx \sqrt{2\pi n} e^{-n}$$ where here $n = 2^{160}$. $\endgroup$ – Geoffrey Irving Dec 25 '13 at 1:27
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why is it less by one? (sorry if this sounds stupid) $\endgroup$ – Timo Huovinen Dec 17 '13 at 7:45
  • $\begingroup$ @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? $\endgroup$ – k20 Dec 17 '13 at 16:03
  • $\begingroup$ yes the 99 makes it clearer, thank you $\endgroup$ – Timo Huovinen Dec 17 '13 at 19:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is the sha1 hash really a bin of 2^160 unique objects? $\endgroup$ – Timo Huovinen Dec 17 '13 at 7:43
  • $\begingroup$ 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? $\endgroup$ – Wolfgang Bangerth Dec 17 '13 at 7:59
  • $\begingroup$ @WolfgangBangerth hashes in general, I just picked sha1 because I heard that it was better than say md5 $\endgroup$ – Timo Huovinen Dec 17 '13 at 15:00

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.