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

[Ed Gerck]

David Wagner wrote:

> > 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.

The event is finding 1 collision out of n messages.

> 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.

;-) I never said it was new. But since you apparently sided with #1 and I
sided with #2, I was commenting that -- for once -- we both seem to be
right. BTW, the first time I read those chapters was in '97 and I still go
back to them when I need to brush up on something. The HAC is a great
book and, as you probably know, it's 100% available online too.

Cheers,
Ed Gerck




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