Why is RMAC resistant to birthday attacks?

Ed Gerck egerck at nma.com
Tue Oct 22 17:32:55 EDT 2002

Wei Dai wrote:

> On Tue, Oct 22, 2002 at 12:31:47PM -0700, Ed Gerck wrote:
> > My earlier comment to bear applies here as well -- this attack can be avoided
> > if only a subset of the MAC tag  is used
> I can't seem to find your earlier comment. It probably hasn't gone through
> the mailing list yet.
> I don't see how the attack is avoided if only a substring of the MAC tag
> is used. (I assume you mean substring above instead of subset.)

Yes, subset -- not  a string with less N characters at the end. For example,
you can calculate the P subset as MAC mod P, for P smaller than
2^(bits in the MAC tag).

> The
> attacker just needs to find messages x and y such that the truncated MAC
> tags of x|0, x|1, ..., x|n, matches those of y|0, y|1, ..., y|n, and this
> will tell him that there is an internal collision between x and y.

No. The attacker gets A and B, and sees that A = B. This does not mean
that a=b in  A = a mod P and B = b mod P.  The internal states are possibly
different even though the values seen by the attacker are the same.

> n only
> has to be large enough so that the total length of the truncated MAC tags
> is greater than the size of the internal state of the MAC.
> > OR if the message to be hashed has
> > a fixed length defined by the issuer. Only one of these conditions are needed.
> No I don't think that works either. The attacker can try to find messages
> x and y such that MAC(x|0^n) = MAC(y|0^n) (where 0^n denotes enough zeros
> to pad the messages up to the fixed length).  Then there is a good
> chance that the internal collision occured before the 0's and so
> MAC(x|z)  = MAC(y|z) for all z of length n.

Why do you think there is a "good chance"?

Note that all messages for which you can get a MAC have some fixed message
length M. The attacker cannot leverage a MAC value to calculate the state of
a M+1 length message -- exactly because this is prevented by making all messages
have length M.

Ed Gerck

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

More information about the cryptography mailing list