Why is RMAC resistant to birthday attacks?
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).
> 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.
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography