Why is RMAC resistant to birthday attacks?

Ed Gerck egerck at nma.com
Wed Oct 23 20:01:52 EDT 2002

Wei Dai wrote:

> ...
> suppose that an attacker finds two messages X and Y such that MAC(X|0) =
> MAC(Y|0), MAC(X|1) = MAC(Y|1), up to MAC(X|n) = MAC(Y|n). There are two
> possibilities: either there is a collision in the internal state after
> processing X and Y, or the internal states are different and all those MAC
> tags match up through seperate coincidences.
> ...

I think that there is a third (and dominating) possibility: this is a very bad MAC.
(A required property of MACs is providing a uniform distribution of values for a
change in any of the input bits, which makes the above sequence extremely

BTW, references for using MAC subsets OR fixed-length messages to prevent
guessing the internal chaining value should be straight forward to find in the

Ed Gerck

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

More information about the cryptography mailing list