Why is RMAC resistant to birthday attacks?

[Wei Dai]

On Tue, Oct 22, 2002 at 11:09:41AM -0700, bear wrote:
> Now Bob sends Alice 2^32 messages (and Alice's key-management
> software totally doesn't notice that the key has been worn to
> a nub and prompt her to revoke it).  Reviewing his files, Bob
> finds that he has a January 21 document and a September 30
> document which have the same MAC.
> 
> What does Bob do now?  How does this get Bob the ability to
> create something Alice didn't sign, but which has a valid MAC
> from Alice's key?

Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows
MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states
of the MAC after processing x and y are the same and therefore will remain
equal given identical suffixes. So he can get a MAC on x | z and
it's also a valid MAC for y | z, which Alice didn't sign.  This applies
for CBC-MAC, DMAC, HMAC, and any another MAC that is not randomized or
maintains state (for example a counter) from message to message.

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