Why is RMAC resistant to birthday attacks?

[bear]

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?

Does it mean I can then create a bogus message, which the oracle
has never seen, and generate a MAC that checks for it?  If so
how?

In protocol terms, let's say Alice is a digital notary.  Documents
come in, and Alice attests to their existence on a particular
date by adding a datestamp, affixing a keyed MAC, and sending
them back.

Now Bob sends Alice 2^32 messages (and Alice's key-management
software totally doesn't notice that the key has been worn to
a nub and prompt her to revoke it).  Reviewing his files, Bob
finds that he has a January 21 document and a September 30
document which have the same MAC.

What does Bob do now?  How does this get Bob the ability to
create something Alice didn't sign, but which has a valid MAC
from Alice's key?

				Bear




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