Why is RMAC resistant to birthday attacks?

[Ed Gerck]

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 at 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 at wasabisystems.com


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