Why is RMAC resistant to birthday attacks?

[David Wagner]

Ed Gerck  wrote:
>Wei Dai wrote:
>> 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.
>
>Actually, for any two (different) messages the internal collision probability
>is bounded by the inverse of the SQUARE of the size of the internal state space.

No, I think Wei Dai had it right.  SHA1-HMAC has a 160-bit internal state.
If you fix two messages, the probability that they give an internal collision
is 1/2^160.

Maybe you are thinking of the birthday paradox.  If you have 2^80 messages,
then there is a good probability that some pair of them collide.  But this
is the square root of the size of the internal state space.  And again, Wei
Dai's point holds: the only way to reduce the likelihood of internal collisions
is to increase the internal state space.

In short, I think Wei Dai has it 100% correct.

>Not really. You can prevent internal collision attacks, for example, by using
>the envelope method (e.g., HMAC) to set up the MAC message.

This is not accurate.  The original van Oorschot and Preneel paper
describes an internal collision attack on MD5 with the envelope method.
Please note also that HMAC is different from the envelope method, but
there are internal collision attacks on HMAC as well.  Once again, I
think Wei Dai was 100% correct here, as well.

You might want to consider reading some of the literature on internal
collision attacks before continuing this discussion too much further.
Maybe all will become clear then.

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