Why is RMAC resistant to birthday attacks?

[Wei Dai]

On Wed, Oct 23, 2002 at 07:50:44AM -0700, bear wrote:
> 1) First, it doesn't work unless the MAC algorithm is sequentially
>    linear (ie, unless its internal state never depends on nonlinear
>    interactions between earlier and later parts of the message).
>    Sequential linearity, for this reason, seems like a very bad
>    property for a MAC algorithm to have.

I'm not sure what you're talking about. What's an example of a MAC 
algorithm that is not sequentially linear?

> 2) Second, it only works if the MAC generated discloses the *entire*
>    internal state of the MAC algorithm -- which it should not, any
>    more than any other pseudorandom number generated should disclose
>    the entire internal state of the PRNG that generated it.  The
>    MAC algorithm should have *FAR* more internal state than the number
>    of bits disclosed in the MAC.  If the algorithm has N bits of
>    internal state and the MAC is M bits where M < N, and the algorithm
>    is secure, then the attacker cannot determine with a better than
>    1/((N-M)^2) probability that the MAC algorithm's internal state
>    is in fact the same after each of two messages that generate
>    identical MACs.

It would be nice to have more internal state, but I'm not aware
of any efficient (by which I mean as fast as the underlying block cipher)  
MAC construction based on block ciphers that have more internal state than
the size of the cipher block, unless it is either randomized or carries
state from message to message.

If the algorithm has only N bits of internal state, then it does not
improve security to reveal less than N bits in the MAC tag. I already
explained why in a reply to Ed Gerck, but perhaps did so poorly. So again,
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.  The probability that all
those MAC tags are equal when there is no collision in the internal state
can be made much smaller than the probability that there is a collision,
by increasing n. So the attacker can always determine with high
probability when an internal collision has occured.

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