Subject: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)

From: David Wagner <[email-masked]>
Date: Sat, 29 Oct 2005 11:50:07 -0700 (PDT)

It may be hard for people to remember the thread context.  We've had a
long chain of responses (some of which seemed to have missed the point
that I was trying to make).  Therefore, I want to refresh everyone's
memory.  You may recall that Dan Bernstein wrote:

  How do we build PRFs? By hashing the key and the input.

In response, I wrote:

  That's one possibility, although I'm starting to become inclined to
  limit our reliance on hash functions as much as necessary, after all
  these attacks on many of our hash functions.  Another possibility --
  which I would have more confidence in at the moment -- is to use a
  block cipher based PRF such as AES-OMAC.

Let me stress that Bernstein asked about a PRF (a pseudorandom functions),
not, e.g., key extraction from a biased source.

My response was that, if you want a PRF, Bernstein's scheme is a poor
choice.  It is better to use a construction like AES-OMAC than to use
what Bernstein proposed.

Bernstein seems to be suggesting SHA256(K||X).  That is a poor choice
of PRF.  It is not secure against truncation attacks.  And even if we
assume that X is of fixed length, it is a poor choice of a construction,
because it makes very strong assumptions about the properties of the hash.
(It is secure in the random oracle model, but the RO model makes very
strong "assumptions" about the hash.)

As Hugo Krawczyk says, if you want to use a hash-based PRF,
SHA256-HMAC(K,X) is better.  It makes more realistic assumptions about
the hash function, and it doesn't need the RO model.

But I was saying that better still would be to use a block-cipher based
PRF, such as AES-OMAC(K,X).  AES-OMAC assumes only that AES is a PRP
(pseudorandom permutation).  This is a standard and commonly accepted
notion of security for a block cipher.  It is in some sense the weakest
interesting concept of what it means for a block cipher to be secure.
Weaker assumptions are better, because it means that AES-OMAC is less
likely to disappoint.

What also seems relevant is that the recent results on hash functions
cast doubt in my mind on the security of hashing when used for, say,
pseudorandom functions.  Hash functions weren't (primarily) designed
for that kind of purpose.  In comparison, this is exactly what block
ciphers were designed for.

Therefore, if you want a PRF, my suggestion is that something like
AES-OMAC may be one of the most conservative choices out there.

Now, let's come to the responses that we have heard from Dan Bernstein
and others.  They missed the above point.  They went on tangents.
Bernstein claimed that some construction using AES + Luby-Rackoff +
Miyaguchi-Preneel leads to a hash scheme that is ``exactly the same''
as AES-OMAC.  I believe that claim to be inaccurate.  I have been trying
to pin Bernstein down on exactly what he means and why things it would
be the case.  I have been failing.

I apologize for dragging you through all this background.  My only excuse
is that it is not my fault: it looks to me like Bernstein has made two
claims that are unjustified, but trying to get this point across has led
to a long chain of responses that make it hard to remember the context
and the background.

With that background, let's come to your email:

John Wilkinson writes:
>I suspect that Dr. Bernstein's will claim that the following two  
>KDF's are equivalent, from a provable security perspective:
>
>KDF1: Ki = CMAC-AES256(SHA256(x),i), where x is the shared secret,  
>SHA256(x) is used as the key to CMAC, and i is a counter used as the  
>message input to CMAC.
>
>KDF2: Ki = SHA256(i,x), where i is a counter, x is the shared secret,  
>and (i,x) represents the concatenation of i and x.

Well, I don't know what he will claim in the future, but that's not what
he was claiming before.

His claims before were not about KDFs intended for use with biased
sources of shared secrets (e.g., Diffie-Hellman shared secrets); they
were about PRFs.  Under the standard meaning of the term, a PRF is only
required to be secure when the key is chosen uniformly at random.

So I don't think your KDF schemes are relevant to the objections I have
raised to Bernstein's comments.

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

---

From: John Wilkinson <[email-masked]>
Date: Sat, 29 Oct 2005 17:57:55 -0400

Getting back to the original topic of the NIST HKDF proposal, several
people suggested that they were uncomfortable with the construction
H_i = H( i || SV || contextID ), which is the one suggested in the
HKDF proposal, with some optional arguments suppressed.

Most of these same people suggested instead something along the lines
of K_i = PRF( H(SV), i || contextID ), where H(SV) is the key input to
the PRF, and ( i || contextID ) is the "message" input to the PRF.
HMAC and CMAC were both suggested as suitable PRFs.

Neither HMAC, nor CMAC retains any security guarantee as a PRF if the
key is not chosen uniformly at random. If we assume that H(SV) is
uniformly random, given that SV may not be, then we should have no
concern with the NIST HKDF. If are not willing to assume that H(SV) is
uniformly random, then our arguments for the PRF-based construction
must be heuristic, and based on non-standard assumptions about the
PRF. If we assume that SV is uniformly random, then we can skip the
"pre-hashing" step, and use SV directly as the key to the PRF.

While it doesn't strike me as unreasonable to desire some additional
measure of heuristic protection, given all that has happened with our
hash functions of late, let us at least be clear that our arguments
are heuristic, and not based on any proven properties of PRFs under
standard assumptions.

Given that the preference for one KDF over the other is just that, a
preference, I would argue that the NIST HKDF proposal should stand
unmodified. Those who are uncomfortable with it are always free to
choose other KDFs.

-John

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Oct 2005 03:21:04 -0000

David Wagner writes:
> You may recall that Dan Bernstein wrote:
  [ ... ]
> choice.

``Bernstein's scheme''? All I said was that we build ``PRFs'' by hashing
the key and the input. For example, AES_k(m) is a hash of (k,m).

In case you've forgotten the context here: We're talking about the
construction of key-derivation functions. _I_ didn't say that we want a
PRF; _Krawczyk_ said that we want a PRF. I quite explicitly _eliminated_
this PRF distraction by rewriting Krawczyk's function as a hash.

> for that kind of purpose.

That depends on the hash function!

What you're trying to say, apparently, is that some hash functions were
designed purely for collision resistance. It's certainly true that we
see mixed results when those functions are reviewed for their merits as
stream ciphers. But some of them have held up. Meanwhile, other hash
functions were designed from the start to be useful for stream ciphers.
Four examples:

   (1) Finding collisions in the Chaum-van Heijt-Pfitzmann hash function
       provably requires finding a huge discrete log. The same hash
       function is useless as a stream cipher. (It's also very slow.)

   (2) MD5 has failed at its original goal of being collision-resistant,
       but it nevertheless seems to hash its input thoroughly enough to
       be usable for stream ciphers. Nobody has reported a successful
       distinguisher for the (fairly slow, roughly 40 cycles per byte)
       stream MD5(k,0),MD5(k,1),... when k is a secret uniform random
       256-bit key and 0,1,... are 256-bit nonces.

   (3) The Salsa20 hash function, like AES, was designed from the start
       to be secure when used as a stream cipher. It doesn't resist
       collisions; it doesn't even compress its input! There are several
       reasonable ways to use Salsa20 to build a collision-resistant
       variable-length-input hash function, but I wouldn't expect that
       to set speed records.

   (4) The Zobrist hash function and UMAC's hash function UHASH are
       useless as stream ciphers. They also don't resist collisions. Of
       course, they have other interesting properties.

Hashing is an extremely broad concept. For each application, perhaps a
particular hash function H is useful, and perhaps it isn't; one can't
tell without looking at the details of H.

Getting back to key derivation: There are many plausible ways to build a
safe key-derivation function. History shows a notable lack of success in
breaking key-derivation proposals, even wimpy MD5-based constructions.
Furthermore, one can easily afford to spend thousands of CPU cycles on
key derivation. On the other hand, especially in hardware, one often
can't afford to fritter away code space. So a sensible designer will
build a key-derivation function by grabbing any component that's already
in the system---AES, for example, or SHA-256---and reusing it.

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