Subject: RE: [Cfrg] New Proofs for NMAC and HMAC: Security Without Collision-Resistance

From: "Blumenthal, Uri" <[email-masked]>
Date: Tue, 7 Feb 2006 17:58:57 -0500

Hi David, 

>> One observation: this paper basically says that we were looking for
>> wrong properties! Collision resistance (strong or weak) is  
>> unnecessary: if the underlying compression function is a PRF then
>> keyed MAC is secure; and if it's not a PRF (Bellare proved that
>> a slightly weaker assumption is still OK) - then weak collision
>> resistance won't help.
>>
>> So when we specify requirements for crypto hash - what we really
>> want/need is Pseudo-Randomness. Then we can safely use it in key
>> derivation, and then keyed MAC is also secure.
>
> AFAICT, Mihir's work doesn't address the issue of whether or not
> NMAC or HMAC is a secure way of deriving symmetric keys from a
> Diffie-Hellman secret.

True. But *if* the construct is a PRF - and there's a good chance of it
if the underlying primitive is a PRF - then key derivation using that
construct to derive keys seems secure enough (yes I realize that DH
secret may have properties :-).

> The abstract describes the work as showing that the functions
> are good PRFs (or just good MACs) based on some different
> assumptions

Hmm... What I read from the paper is something different: in order to
have a good MAC one _has_ to start with a PRF as a compression function.
I don't see anything but assumption that SHA (or MDx) in fact _are_ PRFs
- just the statement that _if_ they are - not only HMAC is secure
(regardless of presence or absence of collision resistance), but also
key derivation applications. Consequently - if those hash function are
in fact _not_ PRFs, then not only key derivation shouldn't be done with
them - but also MACing may be insecure even using HMAC construct.

> ......... but a DH key derivation function can't be shown
> to be secure merely because it is a PRF.

Understand, though not quite. We can discuss this.

> Of course, this is not to suggest that HMAC is a bad KDF. 
> I suspect that it is a good one, but I just don't think
> that the work cited proves anything in that direction.

:-)

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 16 Feb 2006 18:08:42 -0000

It's well known that the standard Wegman-Carter hash-and-encrypt MACs
are secure if the secret-key hash function has low differential
probabilities and the secret-key encryption function is a PRF.

NMAC, HMAC, etc. are examples of the Wegman-Carter framework. They use
SHA with a secret IV as the hash function---conjectured to have low
differential probabilities---and SHA with another secret IV as the
encryption function---conjecturally a PRF.

These aren't particularly good Wegman-Carter examples. We have _faster_
hash functions that are _proven_ to have low differential probabilities.
For example, Poly1305 has low differential probabilities and is much
faster than SHA, so it's much better than SHA as the hash function in a
Wegman-Carter MAC.

See http://cr.yp.to/talks.html#2005.02.15 for many more examples.

> have a good MAC one _has_ to start with a PRF as a compression function.

No. You _can_ start with a PRF compression function, cascade it to build
a PRF hash function, and conclude that the PRF hash function has low
differential probabilities; but most constructions in the literature
don't work this way. For example, Poly1305 certainly isn't a PRF. The
PRF property is overkill.

> construct to derive keys seems secure enough

No. The Vernam key generator is trivially proven to be a PRF, but it's
useless for deriving a secret key from a Diffie-Hellman result g^xy.

It's true that cipher designers use the same basic techniques to build

   * fast key-derivation functions believed to be secure,
   * fast short-key functions believed to be PRFs,
   * fast functions believed to be one-way,
   * fast functions believed to be collision-resistant,

etc.; but these security properties shouldn't be confused. We have many
examples of specific functions that are secure for one context and
breakable for another. It's often a speed disaster to reject functions
in one context merely because they don't qualify in another, and it's
often a security disaster to allow functions in one context merely
because they qualify in another.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago