# SHA-1:Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output?

Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output? What is the probability that a 160-bit SHA-1 hash output contains at least 128 1's?

-

No, theoretically a SHA1 hash can be any 160-bit value, including the string of 160 zeroes.

As for your second question, if we fudge a little bit and consider SHA1 a truly random function this becomes the same question as the following:

If we flip 160 coins, what is the probability that at least 128 of them will be heads?

Solution is left as an exercise to the reader; I suspect this might be a homework question.

-
Additional hint: build (perhaps with a spreadsheet or short program) a Pascal Triangle of appropriate size (perhaps filling it with odds rather than raw number of possibilities); then sum the appropriate terms. –  fgrieu May 16 '13 at 4:49

Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output?

A good (secure) hash function has output that is uniformly and evenly distributed and shouldn't be distinguishable from random value.

Chi-squared tests of several hash functions

So the minimum number of possible ones is $0$ and the maximum number of possible ones is $160$.

What is the probability that the 160 bit result contains at least 128 1's?

The number of possible combinations of 128 ones in 160 bits, which is $4.64648350·10^{33}$, multiply that by the probability each combination, which is $1/(2^{160}) = 6.84227766·10^{-49}$, making the final number $3.17925303·10^{-15}$, about $0.00000000000000317925303\,\%$.

To calculate the probability of at least 128 bits being ones, you have to repeat the same for 129, 130, 131, ..., 160. Then finally add all these probabilities together.

The math is too complicated for me, so I'm not gonna do it.

-
Adnan, your calculation of the probability in the second half of the question is wrong. –  D.W. May 16 '13 at 5:29
@D.W. Yeah, I kind of thought so, it's a bit beyond me. Please, edit the question to correct the "formula", we'd all learn something. –  Adnan May 16 '13 at 5:47
@Adnan, see pg1989's answer for the correct approach to get the right answer. –  D.W. May 16 '13 at 6:05
@D.W. I have looked at it and thought about it, but that's all I was able to figure out. Probability of one coin being head is 0.5, two coins being heads is 0.5*0.5, 3 coins is 0.5*0.5*0.5 so 128 coins is 0.5^128, and then we have a lot of combinations to for these coins to occur which is Comb(128, 160), then we multiply the two numbers. Since you think it's wrong, please help know what is right, a little hint would be a;right as well. –  Adnan May 16 '13 at 6:27
@D.W. Okay, with the help of Antony Vennard, I think the answer is a bit better now. –  Adnan May 16 '13 at 8:28

While others have blindly posted that the minimum number of possible 1s is 0 based on random oracle assumptions, it must be kept in mind that SHA-1 is not a random oracle, it is a specific algorithm. AFAIK, there is no known proof that there exists an input for which SHA-1 outputs all 0s. So there is no "known mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output". We don't know if the minimum number of 1s is 0, 1, 2 or even 3. That being said, it is fair to say that we strongly suspect that it is 0.

-