Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We are considering bit strings of length 160. Let there be some input x, and hash function $H(x) \rightarrow \left \{ 0,1 \right \}^{160}$. How many turns at least it takes to make collision: $H(x_{1})=H(x_{2})$?

I've heard that it may have something common with Birthday Paradox or some probability inequality.

share|improve this question
    
What is the domain of the input $x$? –  Ilya Jan 10 '13 at 17:41
    
Some longer bit string of unknown length (let say infinite length). It's not important in this problem. –  pavlucco Jan 10 '13 at 17:48
    
I am missing something, is your hash $H:\{0,1\}^{160} \to \{0,1\}^{160}$? How are the inputs distributed? –  copper.hat Jan 10 '13 at 17:54
1  
@pavlucco: You might want to read Hash Collision Probabilities. You might also want to read On Probabilities of Hash Value Matches Lastly, this NIST paper. Regards –  Amzoti Jan 10 '13 at 17:56
    
@copper.hat Let say inputs are random values. –  pavlucco Jan 10 '13 at 18:00
add comment

1 Answer

You might look at the generalized birthday problem. What is the appropriate number for $d$, the equivalent of the number of days in a year? This presumes that your question is inputting many different inputs $x_i$ and looking for the first collision of any pair.

share|improve this answer
    
But in birthday paradox we are considering one value. In this case we are considering sequence of values. –  pavlucco Jan 10 '13 at 17:50
    
@pavlucco: what you mean by considering one value? In the birthday paradox you have inputs that are randomly selected out of $365.$ In your case you have values (the hashes) that are (if your hash is good) randomly selected out of $2^{160}$. The argument goes through the same way. The fact that the hashes are the output of a hash function is unimportant. –  Ross Millikan Jan 10 '13 at 18:36
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.