Why is RMAC resistant to birthday attacks?

Wei Dai weidai at weidai.com
Tue Oct 22 16:21:54 EDT 2002


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

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



More information about the cryptography mailing list