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

[David Wagner]

> 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.
[...]
> 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).

Umm, that's basically what I said in my previous message to the
cryptography mailing list.  But my terminology was better chosen.
In case 2, calling this "the internal collision probability" is
very misleading; there is no event whose probability is the inverse
of the square root of the size of the internal state space.

Again, this is nothing new.  This is all very basic stuff, covered
in any good crypto textbook: e.g., _The Handbook of Applied Cryptography_.
You might want to take the time to read their chapters on hash functions
and message authentication before continuing this discussion.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com