Why is RMAC resistant to birthday attacks?

[Ed Gerck]

Wei Dai wrote:

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

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.

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

You seem to say that even if some of the internal state is hidden from the MAC
tag, once an attacker sees a MAC collision he can deduct that an internal collision
occurred as well. If so, this is incorrect.

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

Not really. You can prevent internal collision attacks, for example, by using
the envelope method (e.g., HMAC) to set up the MAC message. In such a
case, having a previous message M the attacker can discover (e.g., by calculating
over a large number of messages) another message M* such that hash(M) =
hash(M*) -- i.e., an internal collision. However, finding out this internal collision
CANNOT be leveraged into subverting the receiving party in accepting M* as
genuine.

Thus, without increasing the size of the internal search space AND without
preventing internal collisions by any other way, it is possible to prevent an
attack that would use an internal collision.

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

You seem to imply that it is harder to defend against an attacker who knows
less (only detects collisions), than against an attacker who knows more (also
knows the internal state).  The reverse is true, by logic.

Also, please note that those techniques, and also the envelope method, are indeed
useful to prevent attacks when an attacker can detect collisions in the internal
state -- as my example above exemplifies.

Cheers,
Ed Gerck


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