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.

Cheers,
Ed Gerck


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



More information about the cryptography mailing list