Why is RMAC resistant to birthday attacks?

Ed Gerck egerck at nma.com
Thu Oct 24 13:13:12 EDT 2002



David Wagner wrote:

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

Thanks again. I should have had some coffee at that time...I meant SQUARE ROOT.

As to the point you say is in question: "the only way to reduce the likelihood of internal
collisions is to increase the internal state space." -- this is clearly true but is NOT what
is in discussion here. The point is whether the only way to reduce the likelihood of
attacks based on MAC collisions is to increase the internal state space.  These
statements are not equivalent.

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

However, it was possible to reduce the likelihood of attacks based on MAC
collisions is to increase the internal state space.   This is what I was trying to
explain. More below...

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

It's always good to read more, and learn more. But what I'm saying is
written in many such papers, including some that are written for
a general audience:

---------------
To attack MD5 [for example], attackers can choose any set of messages and
work on these  offline on a dedicated computing facility to find a collision.
Because attackers know the hash algorithm and the default IV, attackers can
generate the hash code for each of the messages that attackers generate. However,
when attacking HMAC, attackers cannot generate message/code pairs offline
because attackers do not know K. Therefore, attackers must observe a
sequence of messages generated by HMAC under the same key and perform
the attack on these known messages. For a hash code length of 128 bits, this
requires 264 observed blocks (273 bits) generated using the same key.
------------------in Dr. Dobbs, April 1999.

The point is clear: WITHOUT increasing the internal search space of MD5,
MD5 is used in a way that vastly reduces the likelihood of attacks based on
MAC collisions.

Cheers,
Ed Gerck








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



More information about the cryptography mailing list