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

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

Jack Lloyd writes:
>On Tue, Oct 25, 2005 at 02:39:20PM -0700, David Wagner wrote:
>> there is NO known solution to this problem in the standard model.  If you
>> start with a secret value that is not known to be uniformly distributed,
>> but is only known to have high min-entropy, then the only (provably secure)
>> way I know of to get a good key out of it is to use a random oracle.
>
>I believe a perfect compressor might also do the trick here, would it not? Of
>course even if it does, that doesn't exactly ground the problem...

In theory, possibly, but there are many problems with this idea:

(1) You have to know the distribution on the secret input exactly before
you can apply perfect compression.  Different distributions will require
different compressors.  If you slightly mis-estimate the distribution,
all bets are off.  Now think about what happens if the secret input
includes any random values chosen by a human (e.g., a passphrase) to see
how hard this is.  In comparison, hashing of the secret input works even
when you don't know what the distribution is.

(2) Perfect compression assumes there is some information-theoretic
entropy in the secret input, which may not be true.  Suppose that the
secret input is a shared Diffie-Hellman g^{xy} key, where g^x and g^y
are public.  Then the perfect compression of g^{xy} is the empty string,
since it is (information-theoretically) already determined given g^x
and g^y.  Thus perfect information-theoretic compression might not
provide any useful key material at all.

(3) Perfect compression might be intractable.  Think about a shared
Diffie-Hellman key g^{xy} mod p where x,y are short exponents.  There is
a good compression, namely the value xy, but finding xy from g^{xy}
is intractably hard.

(4) No one knows how to build a perfect compressors for most
distributions, anyway, so the issue is pretty much moot.

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

---

From: Jack Lloyd <[email-masked]>
Date: Tue, 25 Oct 2005 20:19:21 -0400

> In theory, possibly, but there are many problems with this idea:

Your points 1/3/4 were implicit with my statement that it "doesn't exactly
ground the problem"; I'm well aware that creating a perfect compressor is
either nontrivial or impossible for any interesting input distribution. I
suppose a bit more formally, my speculation was that if one had an algorithm
that could create a perfect compressor for any input distribution, you could
create a secure KDF with it (assuming you could correctly characterize your
input distributions, itself a highly nontrivial problem).

[...]
> provide any useful key material at all.

Nicely put! I had not considered this at all, and you make a good argument here
for why a perfect compressor wouldn't suffice in this context.

Jack