[11884] in cryptography@c2.net mail archive
Re: Why is RMAC resistant to birthday attacks?
daemon@ATHENA.MIT.EDU (Ed Gerck)
Tue Oct 22 13:31:53 2002
Date: Tue, 22 Oct 2002 10:29:49 -0700
From: Ed Gerck <egerck@nma.com>
To: Victor.Duchovni@morganstanley.com
Cc: Cryptography <cryptography@wasabisystems.com>
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. In RMAC, t is increased to 2t, so that
2^(2t/2) = 2^t and there is no reduction in the number of queries due to the
"birthday paradox". For example, for a MAC tag with 128-bit keys, the number
of queries that bound the chance of a forgery is still close to 128 bits. The
penalty is doubling the size of the MAC tag.
BTW, for MAC systems where collisions are prevented a priori, the
"birthday paradox" does not apply.
Cheers,
Ed Gerck
Victor.Duchovni@morganstanley.com wrote:
> The RMAC FIPS draft does not appear to explicitly state when RMAC is
> useful. What is the scenario in which (presumably unlike some other keyed
> MAC algorithms) RMAC is resistant to birthday attacks? More broadly for an
> arbitrary keyed MAC (in a plausible application!) how does the birthday
> attack come into play?
>
> With unkeyed message digests encrypted by a public key, the attacks are
> clear, Alice sends Bob message A, Bob agrees to message A, and signs it.
> Later Alice claims that Bob signed message B. The birthday paradox
> helps Alice because she can generate lots of minor variants of each
> message, generate ~sqrt(2^n) hashes of each and have a good shot at
> finding a collision.
>
> With keyed MACs Alice and Bob share the same secretkeys, either can
> freely generate messages with correct MAC values, so the MAC cannot be
> used as evidence to a third party that Alice is the signer of the
> message.
>
> In this case the attacker is clearly not either Alice or Bob. So Eve wants
> to convince Bob that a message really is from Alice. What does Eve do?
> Does Eve somehow entice Alice to send ~sqrt(2^n) messages to Bob? How does
> the birthday attack come into play when the attacker cannot independently
> test potential collisions?
>
> Please pardon the naive question, I just want to understand the premises
> of the problem to which RMAC is a solution.
>
> --
> Viktor.
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
