collision resistance -- Re: Why is RMAC resistant to birthday attacks?

[Ed Gerck]

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 majordomo at wasabisystems.com