Why is RMAC resistant to birthday attacks?

Ed Gerck egerck at nma.com
Tue Oct 22 15:15:37 EDT 2002

bear wrote:

> On Tue, 22 Oct 2002, Ed Gerck wrote:
> >Short answer:  Because the MAC tag is doubled in size.
> >
> >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.
> This is a point I don't think I quite "get". Suppose that I have
> a MAC "oracle" and I bounce 2^32 messages off of it.  With a
> 64-bit MAC, the odds are about even that two of those messages
> will come back with the same MAC.
> But why does that buy me the ability to "easily" make a forgery?

;-) please note that you already have one forgery...

BTW, it is important to look at the size of the internal chaining variable.
If it is 128-bit, this means that attacks with a 2^128 burden would likely
work. However, if only a subset of the MAC tag  is used OR if the
message to be hashed has a fixed length defined by the issuer, this is not
relevant. Only one of these conditions are needed.

Ed Gerck

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

More information about the cryptography mailing list