Why is RMAC resistant to birthday attacks?

[Ed Gerck]

Sidney Markowitz wrote:

> Ed Gerck" <egerck at nma.com> said:
> > That's is not the reason it was devised. The reason is to prevent a birthday
> > attack for 2^(t/2) tries on a MAC using a t-bit key. Needless to say, it also makes
> > harder to try a brute force attack.
>
> RMAC was devised for the reason I stated, as it says in the last quote from
> the paper above. The salt is there to make the cost of the extension forgery
> attack more expensive because the birthday surprise shows that just the number
> of bits in the cipher block may not make it expensive enough without a salt.
> The key size is not relevant to the "birthday attack" (actually extension
> forgery attack) as shown in the table where the work factor expressed as a
> function of the block length and the salt length, not the key size.

A minor nit, but sometimes looking into why things were devised is helpful.
What I explained can be found in
http://csrc.nist.gov/encryption/modes/workshop2/report.pdf
and especially useful is the segment:

The RMAC algorithm was a refinement of the DMAC algorithm in which a random bit
string was exclusive-ORed into the second key and then appended to the resulting MAC
to form the tag. The birthday paradox in principle was no longer relevant, for, say, the
AES with 128 bit keys, because the tag would be doubled to 256 bits. Joux presented his
underlying security model and the properties that he had proven for RMAC: the number
of queries that bounded the chance of a forgery was relatively close to the number of 128
bit keys.

Cheers,
Ed Gerck


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