Short answer: Because the MAC tag is doubled in size. Longer answer: The �birthday paradox� says that if the MAC tag has t bits, only 2^(t/2) queries to the MAC oracle are likely needed in order to discover two messages with the same tag, i.e., a �collision,� from which forgeries could easily be constructed. In RMAC, t is increased to 2t, so that 2^(2t/2) = 2^t and there is no reduction in the number of queries due to the "birthday paradox". For example, for a MAC tag with 128-bit keys, the number of queries that bound the chance of a forgery is still close to 128 bits. The penalty is doubling the size of the MAC tag.
BTW, for MAC systems where collisions are prevented a priori, the "birthday paradox" does not apply. Cheers, Ed Gerck [EMAIL PROTECTED] wrote: > The RMAC FIPS draft does not appear to explicitly state when RMAC is > useful. What is the scenario in which (presumably unlike some other keyed > MAC algorithms) RMAC is resistant to birthday attacks? More broadly for an > arbitrary keyed MAC (in a plausible application!) how does the birthday > attack come into play? > > With unkeyed message digests encrypted by a public key, the attacks are > clear, Alice sends Bob message A, Bob agrees to message A, and signs it. > Later Alice claims that Bob signed message B. The birthday paradox > helps Alice because she can generate lots of minor variants of each > message, generate ~sqrt(2^n) hashes of each and have a good shot at > finding a collision. > > With keyed MACs Alice and Bob share the same secretkeys, either can > freely generate messages with correct MAC values, so the MAC cannot be > used as evidence to a third party that Alice is the signer of the > message. > > In this case the attacker is clearly not either Alice or Bob. So Eve wants > to convince Bob that a message really is from Alice. What does Eve do? > Does Eve somehow entice Alice to send ~sqrt(2^n) messages to Bob? How does > the birthday attack come into play when the attacker cannot independently > test potential collisions? > > Please pardon the naive question, I just want to understand the premises > of the problem to which RMAC is a solution. > > -- > Viktor. > > --------------------------------------------------------------------- > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
