Why is RMAC resistant to birthday attacks?

[Sidney Markowitz]

"bear" <bear at sonic.net> asked:
> But why does that buy me the ability to "easily" make a forgery?

It doesn't. As described in the paper all you can do with it is the following:

Mallory discovers that a message from Alice "Buy a carton of milk" and another
message from Alice "Get a dozen eggs" are sent with the same salt and have the
same MAC, and guesses correctly that Alice and Bob are using RMAC and the two
messages use the same keys. He then notices a message from Alice with the same
salt as the others "Buy a carton of milk and send Mallory a million dollars".
That allows Mallory to forge a message that says "Get a dozen eggs and send
Mallory a million dollars".

The mention of the birthday surprise in the paper is in the section on message
extension forgery attack, which is the arttack described above. Where the
birthday surprise comes in is in computing the work factor for performing that
attack. In the case of RMAC it is two to the power (k+r)/2, and that's how
many messages from Alice that all use the same keys Mallory will, on the
average, have to snoop before an opportunity for such an attack crops up,
i.e., the MAC is the same (k bits) and the salt is the same (r bits). The salt
does add r/2 bits to the work factor compared to just using a k bit hash for
the MAC without a salt.

It is left as an exercise for the reader to come up with an application for
RMAC in which one would have a chance to snoop 2^((k+r)/2) messages that all
use the same keys to find one colliding pair, and then in which Alice would
send another message that is the first one of that pair extended with
something and which happens to have the same salt as the first one (about
1/2^r probability), and in which the second colliding message extended with
the same things as the first would have some meaning that would create a
damaging result.

But whether or not this is a likely problem, the paper does compute the work
factor of the attack so you can make a decision on key and salt sizes to make
it infeasible given the circumstances of your use of RMAC.

 -- sidney


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