[11885] in cryptography@c2.net mail archive
Re: Why is RMAC resistant to birthday attacks?
daemon@ATHENA.MIT.EDU (bear)
Tue Oct 22 14:12:27 2002
Date: Tue, 22 Oct 2002 11:09:41 -0700 (PDT)
From: bear <bear@sonic.net>
To: Ed Gerck <egerck@nma.com>
Cc: Victor.Duchovni@morganstanley.com,
Cryptography <cryptography@wasabisystems.com>
In-Reply-To: <3DB58B0D.BD117040@nma.com>
On Tue, 22 Oct 2002, Ed Gerck wrote:
>Short answer: Because the MAC tag is doubled in size.
>
>Longer answer: The =93birthday paradox=94 says that if the MAC tag has t b=
its,
>only 2^(t/2) queries to the MAC oracle are likely needed in order to disc=
over
>two messages with the same tag, i.e., a =93collision,=94 from which forger=
ies
>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?
=09=09=09=09Bear
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
