# Hash Functions and Probabilty

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.

-
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
@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

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.
@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