[11925] in cryptography@c2.net mail archive
collision resistance -- Re: Why is RMAC resistant to birthday attacks?
daemon@ATHENA.MIT.EDU (Ed Gerck)
Thu Oct 24 15:32:31 2002
Date: Thu, 24 Oct 2002 11:43:37 -0700
From: Ed Gerck <egerck@nma.com>
To: Wei Dai <weidai@weidai.com>, bear <bear@sonic.net>,
Victor.Duchovni@morganstanley.com,
Cryptography <cryptography@wasabisystems.com>,
David Wagner <daw@cs.berkeley.edu>
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@wasabisystems.com
