Why is RMAC resistant to birthday attacks?

[Wei Dai]

On Wed, Oct 23, 2002 at 05:01:52PM -0700, Ed Gerck wrote:
> 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)

No matter how good the MAC design is, it's internal collision probability
is bounded by the inverse of the size of its internal state space. The
point is that you can't prevent an attacker from learning about an
internal collision, once it happens, by hiding some of the state from the
MAC tag.  The only way to prevent internal collision attacks is to
decrease the internal collision probability, which unless the MAC is badly
designed to begin with, requires increasing the size of the internal state
space.

I'm sorry but I don't know how to explain this any better. I've tried to
do it three different ways, and I hope someone else will do a better job
if you still are not convinced.

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

Those techniques may be useful when the attack requires knowing the 
internal state, but they are not useful when the attack only requires 
detecting collisions in the internal state. The literature you mention 
must be about the former case.

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