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

["D. J. Bernstein" <djb at cr.yp.to>]

David Wagner writes:
> The key assumption about is that the hash and the message must be
> *independent*.

But you are wildly exaggerating this when you say that the hypothesis is
that the hash is ``independent of the adversary's choices.'' That
hypothesis is both unnecessary and false.

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.

There is no requirement that H be kept secret. One can even reuse H for
many messages; see Shoup's Theorem 6.22. As Shoup comments after the
theorem:

   We have a ``secret'' random variable A that is distributed uniformly
   over a large subset of some set A, but we want to derive from A a
   ``secret key'' whose distribution is close to that of the uniform
   distribution on a specified ``key space'' Z (typically, Z is the set
   of all bit strings of some specified length). The leftover hash
   lemma, combined with Theorem 6.22, allows us to do this using a
   ``public'' hash function---generated at random once and for all,
   published for all to see, and used over and over to derive secret
   keys as needed.

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

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

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg