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

From: David Wagner <[email-masked]>
Date: Thu, 27 Oct 2005 19:25:41 -0700 (PDT)

Dan Bernstein writes:
>David Wagner writes:
>> The simplest randomized construction is to let UH(.,.) be a 2-universal
>> hash, pick R randomly, publish R, and use UH(R,S) as your key, where
>> S is the secret input.  This is a KDF with no auxiliary inputs.
>
>For example, if you have a 1024-bit Diffie-Hellman result with 512 bits
>of apparent entropy, and you want to convert it into a 256-bit key, you
>can view it as a polynomial mod 2, multiply by x^256, and reduce the
>result modulo a standard irreducible degree-256 polynomial.

I'd like to see the proof.  Can you show me how the proof goes?
I'll admit to a little bit of skepticism about its provable security.

Here's what's got me puzzled.  The Leftover Hash Lemma requires that
the 2-universal hash be chosen randomly.  You have specified a scheme
where we use a single hash function that has been fixed in advance --
but then the Leftover Hash Lemma is not applicable.  If you're not using
the Leftover Hash Lemma, then what are you using to prove this fact?
What are you assuming about Diffie-Hellman?

If you change your fixed hash function to a random 2-universal hash
function, then I'll believe your claim, albeit with a caveat that you
didn't mention.  The caveat is that your 256-bit key actually has only
128 bits of security, in the sense that the distribution on keys has
variation distance at most 1/2^128 from the uniform distribution.  Thus,
you have started out with 512 bits of entropy, and you've ended up with
only 128 bits of provable security.  That seems a little bit wasteful,
if I understand correctly.

I'd like to better understand the performance overhead of using
2-universal extractors.  We need 512 bits of apparent entropy in the
Diffie-Hellman shared secret g^{xy}.  It looks to me like this means
that we cannot use short exponent Diffie-Hellman: each party's exponents
need to be at least 512 bits long.  This sounds unfortunate, due to its
significant performance costs.  Do I have this correct?  Or is there
some trick that lets you prove this secure even with short exponents?

I'd welcome feedback about whether if my reasoning above is accurate....

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Oct 2005 09:46:08 -0000

David Wagner writes:
> The Leftover Hash Lemma requires that
> but then the Leftover Hash Lemma is not applicable.

The hash function has to be chosen randomly, and has to be independent
of all the other random choices in the protocol, but this doesn't mean
that the choice has to wait until the last possible moment! A single
random hash function can be standardized and reused for many keys. See,
e.g., Shoup's Computational Introduction to Number Theory and Algebra,
Theorem 6.22.

Regarding the number of secure bits obtained in this way: My point was
that there's an obvious, and quite severe, limit on the number. Perhaps
the limit is actually even smaller; I made no effort to check.

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