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

[Adam Back]

But the salt doesn't increase the MAC length.  It just frustrates
attempts to collect message+MAC pairs to find a collision.  Think of
it like a salt on unix passwords.  You can still brute force one
particular target in the same time, but the salt reduces your scope
for pre-computation.

There is still probability 1/2^m of finding a collision given two
random messages, whether the salt has size 0 or 64.

Note that the salt is optional.  They list parameter sets I through V.
Parameter sets II through V are considered safe for general use.
Parameter set II has salt size 0.

Parameter set I is considered only safe for applications where only a
limited number of messages could be sent.  This is more a function of
the small MAC size (32 bits) I think than the fact that the salt size
is 0 for parameter set I.

I would have thought that unless the keys can essentially never change
(for example burnt into hardware) the salt option is of limited
practical use.

The choice of parameter sets is a bit odd.  For example there are no 0
size salts for MAC outputs over 64 bits, while there is for the
smaller MAC outputs, and yet you would think the smaller MAC outputs
are more in need of the salt as finding a collision is more
realistically achievable.  Collecting 2^64 messages (for parameter set
V) seems already quite theoretical for many applications without
adding a 128 bit salt.  Yet collecting 2^32 messages (parameter set
II) seems much more plausible and yet there is no salt defined at that
parameter set.  Given the definition of the parameter sets I suspect
people will interpret the standard as that they must use one of the
listed parameter sets and can't use their own.  At least most
implementations will tend to do that.  Would it not be simpler to just
do away with the salt and parameter sets and describe the collision
problem and note that minimally K2 should be changed (however the
application may decide to arrange this) frequently enough to avoid a
non-neglible risk of collisions being obtainable to attacker.

If the salt is removed / ignored, RMAC is essentially the same as
CBC-MAC but just defined for use with AES (rather than just DES), so
providing more security due to larger block size (and key size).

The one difference which is an incremental improvement over raw
CBC-MAC is that the final CBC-MAC a-like output is encrypted with the
2nd key K3.  (K3 defined as K2 xor salt, K2 an independent key).

However for example Rogaway and Black's XCBC is simpler, more
efficient (not requiring a key schedule for each salt-change) and
equally deals with variable length messages).

http://csrc.nist.gov/encryption/modes/proposedmodes/xcbc-mac/xcbc-mac-spec.pdf

The protection against collisions is of limited practical value, and I
think better left out of the standard.

Adam

On Tue, Oct 22, 2002 at 01:52:18PM -0700, Sidney Markowitz wrote:
> Victor.Duchovni at morganstanley.com
> > I want to understand the assumptions (threat models) behind the
> > work factor estimates. Does the above look right?
> 
> I just realized something about the salt in the RMAC algorithm,
> although it may have been obvious to everyone else:
>
> RMAC is equivalent to a HMAC hash-based MAC algorithm, but using a
> block cipher. 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.
>
> The security of HMAC against attacks based on collisions is measured
> as a function of the bit length of the hash. Using a block cipher in
> CBC mode makes it in effect a b bit hash, where b is the block
> length of the cipher. In many cases the block length of a cipher
> being 64 or 128 bits will be too small by itself. Hence the need to
> add r bits from the salt and the need to write up explicitly how
> RMAC handles collision based attacks and how the salt affects that.

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