Why is RMAC resistant to birthday attacks?

[bear]

On Tue, 22 Oct 2002, Wei Dai wrote:

>On Tue, Oct 22, 2002 at 11:09:41AM -0700, bear wrote:
>> Reviewing his files, Bob
>> finds that he has a January 21 document and a September 30
>> document which have the same MAC.
>>
>> What does Bob do now?  How does this get Bob the ability to
>> create something Alice didn't sign, but which has a valid MAC
>> from Alice's key?
>
>Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows
>MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states
>of the MAC after processing x and y are the same and therefore will remain
>equal given identical suffixes. So he can get a MAC on x | z and
>it's also a valid MAC for y | z, which Alice didn't sign.  This applies
>for CBC-MAC, DMAC, HMAC, and any another MAC that is not randomized or
>maintains state (for example a counter) from message to message.

This is interesting, but there are two easy ways to prevent it:

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.

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.

And these are both very basic points, and ought to be easy things
for MAC designers to avoid.  So, if I found a MAC algorithm that
were subject to the attack you describe, I would cheerfully toss
it out with the morning trash as a Bad Idea.

				Bear









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