Why is RMAC resistant to birthday attacks?

[Ed Gerck]

Victor.Duchovni at morganstanley.com wrote:

> On Tue, 22 Oct 2002, Ed Gerck wrote:
>
> > Short answer:  Because the MAC tag is doubled in size.
>
> I know, but this is not my question.

;-) your question was "Why is RMAC resistant to birthday attacks?"

> > 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.
>
> So the threat model assumes that there is a MAC oracle. What is a
> practical realization of such an oracle? Does Eve simply wait for (or
> entice) Alice to send enough (intercepted) messages to Bob?

Eve may just watch traffic that comes into her company's servers, knowing
the back-end plain text messages. No need to watch external networks. Eve
may also be, for example, one of those third-party monitoring services that
monitor traffic inside enterprise's networks for the purpose of "assuring security".

> Are there any other birthday attack scenarios for keyed MAC?

A birthday attack requires 2^(t/2) values, which looks surprising low -- hence
the name "paradox" (btw, this attack provides the mathematical model behind the
game of finding people with same birthday in a party, which works for a
surprisingly low number of people).  If you can get 2^(t/2) values, the attack
works.

> In many
> applications the collection sufficiently many messages between Alice and
> Bob is simply out of the question. In such cases if Eve cannot mount the
> attack independently and cannot collect 2^(n/2) messages from Alice to
> Bob, presumably RMAC does not offer an advantage over any other keyed MAC.

In an Internet message, datagrams can be inserted, dropped, duplicated, tampered
with or delivered out of order at the network layer (and often at the link layer). TCP
implements a reliable transport mechanism  and copes with the datagram unreliability
at the lower layers. However, TCP is unable to cope with a fraudulent datagram that is
crafted to pass TCP's protocol checks and is inserted into the datagram stream. That
datagram will be accepted by TCP and passed on to higher layers. A cryptographic
system operating  below TCP is needed to avoid this attack and filter out the deviant
datagrams -- and that's where you would use a MAC, if you want to protect each
datagram. It's not difficult, thus, to have more than 2^32 MACs in one message or
in a series of messages.

This is a scenario where it is not so difficult for an attacker to forge an acceptable
MAC for a datagram that was not sent in a given sequence, possibly tampering with
the upper-layer message and also making it more vulnerable to denial-of-service attacks.
Note that having a MAC above TCP does not prevent this attack, even though it can
detect it (and thus lead to a denial-of-service).

> I am not confused by the RMAC algorithm or so the associated work factor
> estimates, I want to understand the assumptions (threat models) behind the
> work factor estimates. Does the above look right?

If birthday attack is a concern, RMAC is helpful. If not, then not.

Cheers,
Ed Gerck


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