Why is RMAC resistant to birthday attacks?

[Ed Gerck]

Wei Dai wrote:

> 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.

My earlier comment to bear applies here as well -- this attack can be avoided
if only a subset of the MAC tag  is used OR if the message to be hashed has
a fixed length defined by the issuer. Only one of these conditions are needed.

> 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.

except as above noted, which is easy to implement.

Cheers,
Ed Gerck




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