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