Why is RMAC resistant to birthday attacks?

[Sidney Markowitz]

Ed Gerck" <egerck at nma.com> said:
> No -- these are all independent things. One can build an RMAC wih SHA-1.
> An RMAC does not have to use an HMAC scheme. One can also have an
> HMAC hash-based MAC algorithm using a block cipher, that is not an RMAC.

Some quotes from the paper:

"This paper defines an authentication mode of operation, called RMAC, for a
symmetric key block cipher algorithm"

The definition of RMAC in the table of defnintions: "The name of the
authentication mode that is specified in this Recommendation"

"In particular, RMAC is an algorithm for generating a message authentication
code (MAC) from the data to be authenticated and from an associated value
called a salt, using a block cipher and two secret keys [...]"

"Fips Pub 198 specified a different MAC algorithm, called HMAC, that is also
appropriate for protection of sensitive data. Because HMAC is constructed from
a hash function rather than a block cipher algorithm, RMAC may be preferable
for application environments in which an approved block cipher is more
convenient to implement than an approved hash function."

> > The paper states that it is for use instead of HMAC iin circumstances
> > where for some reason it is easier to use a block cipher than a
cryptographic
> > hash.
>
> 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.

 -- sidney


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