There seems to be a question about whether: 1. the internal collision probability of a hash function is bounded by the inverse of the size of its internal state space, or
2. the internal collision probability of a hash function is bounded by the inverse of the square root of size of its internal state space. If we assume that the hash function is a good one and thus its hash space is uniformely distributed (a good hash function is a good PRF), then we can say: For a hash function with an internal state space of size S, if we take n messages x1, x2, ...xn, the probability P that there are i and j such that hash(xi) = hash(xj), for xi <> xj, is P = 1 - (S!/( (S^n)*(S - n)!) which can be approximated by P ~ 1 - e^(-n*(n - 1)/2^(S + 1) ). We see above a n^2 factor which will translate into a factor with sqrt(2^S) when we solve for n. For example, if we ask how many messages N we need in order to have P > 0.5, we solve for n and the calculation gives: N ~ sqrt( 2*ln(2)*2^S ). Thus, if we consider just two messages, affirmation #1 holds, because P reduces to 1/S. If we consider n > 2 messages, affirmation #2 holds (the birthday paradox). Cheers, Ed Gerck --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]