comparing RMAC to AES+CBC-MAC or XCBC (Re: Why is RMAC resistant to birthday attacks?)

[Sidney Markowitz]

Adam Back <adam at cypherspace.org> wrote:
> But the salt doesn't increase the MAC length.  It just frustrates
> attempts to collect message+MAC pairs to find a collision.
[...]
> There is still probability 1/2^m of finding a collision given two
> random messages, whether the salt has size 0 or 64.

No, because it is not a collision for the purpose of this attack on this
algorithm unless the b bit untruncated MAC and the r bit salt both match, even
if the m bit truncated MAC matches. As it says in the paper:

"the unauthorized party would have to collect 2^((b+r)/2) message-tag pairs in
order to expect to detect a collision"

That's because the collision is only of use for the extension forgery attack
if the two colliding messages have the property that RMAC(x) == RMAC(y) and
RMAC(x||z) == RMAC(y||z) which is only true for a collision of the full b bit
untruncated MAC and the r bit salts are the same..

> The choice of parameter sets is a bit odd.

I think that they are chosen to make the work factors for General Forgery and
Extension Forgery attacks about the same in any one parameter set. It would
not make sense to have a parameter set which was a lot weaker to one of the
attacks than to the other. Look at Table 2 to see that is so.

 -- sidney


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