[11893] in cryptography@c2.net mail archive
Re: Why is RMAC resistant to birthday attacks?
daemon@ATHENA.MIT.EDU (Ed Gerck)
Tue Oct 22 16:24:35 2002
Date: Tue, 22 Oct 2002 12:15:37 -0700
From: Ed Gerck <egerck@nma.com>
To: bear <bear@sonic.net>
Cc: Victor.Duchovni@morganstanley.com,
Cryptography <cryptography@wasabisystems.com>
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@wasabisystems.com
