Subject: Re: [Cfrg] soliciting feedback on HKDF

From: "Blumenthal, Uri" <[email-masked]>
Date: Tue, 20 Oct 2009 10:04:59 -0400

I'd like to bring up my old question that hasn't been answered.

Design of hash functions had  producing unique digests (collision avoidance) as its primary goal. Any randomization properties - if they existed - were just a by-product.

Engineers noticed that hash output looked random to them, and started using hash functions as randomizers.

HMAC construct was designed to foil certain attacks against keyed hash functions. What are the reasons to believe that HMAC adds anything to the randomization property of the underlying hash functions?

(I'm not asking for a proof - just give me something that wouldn't be foolish to believe :-)

----- Original Message -----
From: [email-masked] <[email-masked]>
To: Dan Harkins <[email-masked]>
Cc: Tim Polk <[email-masked]>; David McGrew <[email-masked]>; [email-masked] <[email-masked]>; Hugo Krawczyk <[email-masked]>
Sent: Mon Oct 19 23:36:24 2009
Subject: Re: [Cfrg] soliciting feedback on HKDF

On Monday,2009-10-19, at 17:36 , Dan Harkins wrote:

>   A very nice I-D and I think HKDF will be a valuable building  
> block for protocol designers.

I would like to echo this sentiment: in attempting to stringently  
evaluate "Everything that could possibly go wrong" with Tahoe-LAFS's  
crypto design [1], I keep thinking that the KDF is a linchpin  
component in several places.  (The recent revelation of related-key  
issues in AES-256 is one of the reasons to think this.)  Thank you  
for working on the design and standardization of HKDF!

For what it is worth -- I really don't want to start an argument  
about this somewhat tangential issue -- I don't like HMAC-SHA256  
nearly as well as I like Poly1305-AES or Poly1305-Salsa20.  This is  
an unfortunate period in cryptography when there isn't a really good  
secure hash function that we can rely on, and the strong security  
proofs and superior performance of the Carter-Wegman MACs like  
Poly1305 look better to me than the security proofs of HMAC.

Regards,

Zooko Wilcox-O'Hearn

[1] http://allmydata.org/trac/tahoe/wiki/NewCaps/WhatCouldGoWrong
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Basil Dolmatov <[email-masked]>
Date: Tue, 20 Oct 2009 18:58:42 +0400

> (I'm not asking for a proof - just give me something that wouldn't be foolish to believe :-)
There cannot be a definite answer without a thorough mathematical 
analysis of HMAC transformation and its influence upon randomness of the 
source.

Moreover, taking into account that hash output is not by definition the 
source of uniformly distributed randomness, the question which 
properties will be held by the result of consecutive computation of hash 
and HMAC will definitely depend upon the hash function used and HMAC 
transformation used.

dol@

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 20 Oct 2009 10:32:08 -0700 (PDT)

Hi Uri,

  Check out "Random Oracles are Practical" by Bellare and Rogaway.
Section 6 discusses how to use a standard hash function, which by
itself has too much structure, to make a random oracle.

  In fact, they provide an example to extend the range and domain of
the mapping for an example random oracle and end up with something that
looks remarkably like a KDF. It even includes a random "salt" to
instantiate multiple independent random oracles.

  Dan.

On Tue, October 20, 2009 7:04 am, Blumenthal, Uri wrote:
> Design of hash functions had  producing unique digests (collision
> avoidance) as its primary goal. Any randomization properties - if they
> existed - were just a by-product.
>
> HMAC construct was designed to foil certain attacks against keyed hash
> functions. What are the reasons to believe that HMAC adds anything to the
> randomization property of the underlying hash functions?
>
> Cc: Tim Polk <[email-masked]>; David McGrew <[email-masked]>;
> [email-masked] <[email-masked]>; Hugo Krawczyk <[email-masked]>

---

From: "Blumenthal, Uri" <[email-masked]>
Date: Tue, 20 Oct 2009 13:43:31 -0400

There are two issues. One - whether a hash function as-designed is a good
source of randomness. The other one - which is the most relevant here - is
whether HMAC adds anything useful to randomization property.

Because neither hashes like SHA nor HMAC were designed as randomizers.

I'll certainly look up the reference, thanks!

-- 
Regards,
Uri         [email-masked]
<Disclaimer>

---

From: Zooko Wilcox-O'Hearn <[email-masked]>
Date: Tue, 20 Oct 2009 16:51:43 -0600

> instantiate multiple independent random oracles.

Yes, and you might also be interested in "How Risky is the Random- 
Oracle Model?" by Gaetan Leurent and Phong Q. Nguyen 2008 which  
attacks those constructions from BR93 along the way of making  
interesting points about "How bad is it" in different cryptosystems  
if the thing standing in for a random oracle fails to act like one.

http://eprint.iacr.org/2008/441

Regards,

Zooko