[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: (IMPORTANT) Call for AH-MD5 and ESP-DES to move forward




The following telegraphic presentation attempts at summing up our relevant
knowledge, accumulated during the past year or two, on the use of keyed hash
functions as MACs. I hope it will help in clarifying the current discussion.

I will consider the following schemes:

 *  The "prepend key and length" scheme, PKL(msg) = Hash(key,length,msg)
 *  The "envelope" scheme, ENV(msg) = Hash(key,pad,msg,key)
 *  The HMAC scheme, HMAC(msg)  = Hash(key,pad1, Hash(key,pad2,msg))
 *  The NMAC scheme, NMAC(msg) =  Hash_key1 (Hash_key2(msg))
    (This last scheme is similar to HMAC, with the exceptions that
     it uses two keys instead of one, and puts the keys in the IV of
     the hash function instead of in the first part of the input.)


I) No feasible attack is currently known against any of these schemes.
If this is satisfactory then any of the above schemes will do.
However, one may want to have a better assurance than that for a standard.
Thus, attempts have been made to gain further assurance in the security
of schemes by proving statements of the sort: "If the underlying hash 
function enjoys property X then scheme Y is a good MAC".
The weaker property X is, the more assurance we have in the security of
scheme Y. I am not aware of any other method for gaining assurance
in the security of a MAC scheme based on cryptographic hash functions.

II) The only claim I know, of the sort described above, regarding PKL and ENV
is: "If the compression function of the underlying hash function
is pseudorandom then PKL and ENV are good MACs".

This was the first statement of this sort that was proven, regarding any scheme;
thus at the time ENV and PKL gave the best assurance. However,
Pseudorandomness is quite a strong assumption.


III)  On the more recently proposed NMAC scheme one can show that
"If the hash function is collision-free (in a very weak sense)
and the compression function is a good MAC on 512-bit messages then NMAC
is a good MAC".
Here the required properties of the hash function are much weaker
than pesudorandomness. In fact, they are quite minimal in the sense that
if they are not satisfied by some hash function then it is hard to imagine
that this hash function can be used to genrate MACs in any way at all.
In particular, this is the best security guarantee known for a hash-based MAC.

However, NMAC has the drawbacks that it uses two keys rather than one
and that it requires a small change in the code  of the hash function
(i.e., putting the keys in the IV). Thus HMAC was proposed as a compromise.
HMAC uses only one key and requires no change in the code of the hash
function. However, an additional "mixing" property of the compression
function is assumed. Still, the combined assumptions on the hash function
are near-minimal and in particular much weaker than those of (II).

In short, out of the schemes that use a single 128-bit key and do not
change the code of the underlying hash function, HMAC provides
the strongest assurance in its security.

I must say that, given that all these schemes are of comparable efficiency,
I find it hard to imagine why the forum would want to adopt a scheme
that provides weaker assurance than HMAC.


Ran Canetti