Why is RMAC resistant to birthday attacks?

[Ed Gerck]

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.

Cheers,
Ed Gerck


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