Why is RMAC resistant to birthday attacks?

[Ed Gerck]

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

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

Cheers,
Ed Gerck



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