Subject: [Cfrg] Fwd: Hash-Based Key Derivation

From: David Wagner <[email-masked]>
Date: Tue, 25 Oct 2005 14:47:12 -0700 (PDT)

Simon Blake-Wilson writes:
>Thanks David ... interesting stuff. You clearly have a clear idea of what
>you think a KDF does in terms of security, but I guess I'd still like to
>see a convincing formal defintion.

For me, a KDF is a function that takes a secret input S and some auxiliary
input X.  The security requirement is that KDF(S,X) should act as a
pseudorandom function: in other words, an attacker should not be able
to distinguish KDF(S,.) from R(.), where R is a uniformly random function.

Achieving this security requirement will require some assumptions on the
distribution on S.  Thus, we can talk about a particular scheme being
a good KDF for some particular distribution on S (e.g., the uniform
distribution), or being a good KDF for some class of distributions
(e.g., distributions with high min-entropy).  Standard PRFs suffice if
the secret S is known to be uniformly distributed (or pseudorandom).
In the random oracle model, pre-hashing followed by a PRF suffices if
the secret S is known to have high min-entropy and is generated by an
efficient procedure that is independent of the random oracle.

>Also if making random oracle model assumptions is OK, then the definition
>in the I-D is also likely to be good, isn't it? For example, won't H(S|X)
>also be a good KDF if H is assumed to be a random oracle?

Yes, both H(S||X) and F(H(S),X) are good KDFs in the random oracle model.
However, I prefer the latter, because it minimizes the use of the
random oracle assumption.  The former assumes that the hash function
remains secure even if the adversary can specify many X-values and learn
H(S||X) for each such X (with the same S throughout).  This is a strong
assumption, which our hash functions weren't necessarily designed for.
The latter scheme makes a weaker assumption: that the hash function works
when the attacker does not have this extra ability to specify X-inputs.
Therefore, F(H(S),X) reduces our reliance on the hash function.  This is
admittedly a subtle point.  Still, as I remember Mihir Bellare and Phil
Rogaway putting it once, the weaker the assumptions you start from,
the less likely the scheme is to disappoint.

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

---

From: David Wagner <[email-masked]>
Date: Tue, 25 Oct 2005 14:55:52 -0700 (PDT)

Tom Shrimpton writes:
>The problem is that all of our existing hash functions are based on the 
>Merkle-Damgard paradigm, but plain MD doesn't preserve random-oracle-ness.
>There's a nice new paper by Coron, Dodis, Malinaud and Puniya 
>"Merkle-Damgard Revisited: How to Construct a Hash Function" that addresses 
>this issue.

Amusingly, I view that paper as supporting the random oracle model,
not undermining it.  That paper provided evidence that it may be
reasonable to model our hash functions as random oracles, as long as
the hash functions are only invoked on some prefix-free message space.
More precisely, if the compression function is modeled as a random oracle,
then the MD scheme is also a random oracle as long as you ensure there is
no pair of possible messages M,M' in the message space such that M is a
prefix of M'.  And good cryptosystem designers already ought to know to
avoid length-extension attacks on MD hashes by ensuring that the message
space is chosen to be prefix-free.

I guess what I'm saying is that good cryptographic design involves
both provable security (e.g., in the random oracle model) as well as
application of good cryptographic hygiene, prudent engineering practices,
and other heuristic rules of thumb.  This combination seems to lead to
pretty reasonable protocols.

---

From: David Wagner <[email-masked]>
Date: Tue, 25 Oct 2005 14:58:45 -0700 (PDT)

>> I wanted call your attention to an individual draft on "Hash-Based  
>> Key Derivation."
>>       http://www.ietf.org/internet-drafts/draft-dang-nistkdf-00.txt

One more quick comment:

2.1.5: The protocol should specify whether SharedInfo will be used or not.
If SharedInfo is used, then either the number of substrings (the value
n) should be fixed and specified by the protocol, or else the value of
n should be prepended to SharedInfo.

---

From: David Wagner <[email-masked]>
Date: Wed, 26 Oct 2005 10:07:23 -0700 (PDT)

Dan Brown writes:
>Aside, if H fails to be collision-resistant (for its length), isn't there 
>an argument that it isn't pseudorandom?  I suppose that depends very much 
>on the definition of PRF, of course.

First, there is only one definition of PRF: the standard one.

Second, the first question in some sense has a type error: a PRF takes
two inputs (a key and a 'message'), while a hash takes one input (a
'message').

But supposing that we view a hash H as a PRF through the construction
F(K,X) = H(K||X), then the answer is "No".  It is possible for a
function to be pseudorandom but not collision-resistant.  For example,
take this function:
  Evil(K,X):
  1. If K = 0^128, output 0^128.
  2. Otherwise, output AES(K,X).
This is pseudorandom but not collision-resistant, since
  Evil(0^128,X) = Evil(0^128,X') for any X!=X'.