Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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.

enter image description here
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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.