Why is RMAC resistant to birthday attacks?

[Victor.Duchovni at morganstanley.com]

On Tue, 22 Oct 2002, Ed Gerck wrote:

> Short answer:  Because the MAC tag is doubled in size.

I know, but this is not my question.

>
> Longer answer: The “birthday paradox” says that if the MAC tag has t bits,
> only 2^(t/2) queries to the MAC oracle are likely  needed in order to discover
> two messages with the same tag, i.e., a “collision,” from which forgeries
> could easily be constructed.

So the threat model assumes that there is a MAC oracle. What is a
practical realization of such an oracle? Does Eve simply wait for (or
entice) Alice to send enough (intercepted) messages to Bob?

Are there any other birthday attack scenarios for keyed MAC? In many
applications the collection sufficiently many messages between Alice and
Bob is simply out of the question. In such cases if Eve cannot mount the
attack independently and cannot collect 2^(n/2) messages from Alice to
Bob, presumably RMAC does not offer an advantage over any other keyed MAC.

I am not confused by the RMAC algorithm or so the associated work factor
estimates, I want to understand the assumptions (threat models) behind the
work factor estimates. Does the above look right?

-- 
	Viktor.


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