Subject: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]

From: David Wagner <[email-masked]>
Date: Sat, 29 Oct 2005 23:12:00 -0700 (PDT)

Dan Bernstein writes:
>Here's the standard example. The legitimate users exchange authenticated
>public keys g^x and g^y, and an independent authenticated random H. They
>compute the Diffie-Hellman shared secret g^xy and a short hash H(g^xy).
>If the attacker can't distinguish g^xy from a uniform random group
>element then, by the leftover-hash lemma, the attacker can't distinguish
>H(g^xy) from a uniform random short string.

Ok.  Now I get it.  I see what you're saying, and it makes sense.
That kind of protocol hadn't occurred to me.  (I guess you are assuming
that H is chosen by a party who won't be malicious, which is reasonable.)

Thanks for the detailed explanation.  That was very helpful.

To make a pre-fixed 2-universal hash work in this context, it seems
we need it to be the case that:
  (a) the 2-universal hash function is chosen by a party who is
  known not to be malicious, and its value is authenticated so
  that everyone can know it came from that party; and,
  (b) all inputs to the hash function are chosen by users who are
  known not to be malicious, and are authenticated so that everyone
  can verify that they came from those users.
In this case, a 2-universal hash function fixed in advance will
work (for some choice of security parameters).

It seems that all of these conditions need to hold true if we want
to use the Leftover Hash Lemma.  There are also protocols where these
conditions do not hold, and where a hash function chosen and fixed in
advance is not secure.

So it sounds like 2-universal key derivation has to be used with some
care, and cannot be blindly applied to all protocols.  If we were going
to replace the NIST KDF with a 2-universal based KDF, then we would
probably need some extra precautionary usage notes describing what
conditions the protocol must satisfy.

Is that right?

>There are some serious limitations here, notably the short H output
>length, but the limitations shouldn't be exaggerated.

Yup.  Thank you for your clarifying email.

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

---

From: canetti <[email-masked]>
Date: Sun, 30 Oct 2005 09:59:07 -0500 (EST)

If I may jump into the discussion to harp on another point...

On Sat, 29 Oct 2005, David Wagner wrote:

...

> conditions the protocol must satisfy.

I think so. And this highlights the need for a spearate function for
randomness extraction (or, call it key derivation if you like) and a separate
one for key expansion. The first one is intimitely tied to the specific
key exchange method in use, and very different extraction/derivation
functions are needed for each different key exchange method. The second
one is generic, and should depend only on the needs of the application
in terms of key lengths etc.

Ran

PS: 2-universal hashing is one (rather primitive) instantiation of a
"randomness extractor". Other constructions exist in the modern literature.
So it's probably better to use the generic term for the primitive rather
than a specific algorithm.