Hash Algorithm Strength

Normally when people talk about the birthday paradox, they mean "it is surprisingly likely that some two students in a classroom will have the same birthday" rather than "it is surprisingly likely that some student will have the same birthday as the teacher."

Anyways, let's say h is a hashing function, and x = h(a), where I know x but not a. I want to find b so that h(b) = h(a). Let's say that for a random b, we have P(h(a)=h(b)) = p. Then it is quite easy to compute that the expected number of tries to find b with h(a)=h(b) is 1/p.

(In particular:

  E(#of tries) = (p)(1) + (1-p)(p)(2) + (1-p)(1-p)(p)(3) + ...
  =  p(1/p)(1/p) = 1/p.

)