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

[David Wagner <[e-mail]>]

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
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg