Why is RMAC resistant to birthday attacks?
bear at sonic.net
Wed Oct 23 10:50:44 EDT 2002
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
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.
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography