[Cfrg] Fwd: Hash-Based Key Derivation

Dan Brown writes:
>Let H be a collision-resistant hash.
>
>Let D be an adversary that defines a distribution S, efficiently 
>sampleable, with some requisite level of min-entropy, such that D has a 
>signficant advantage of distinguishing H(s) from random R, where s is 
>drawn from S and R is a random bit string of the same length as R.
>
>Use D in algorithm C that finds a collision in H faster than expected, [..]

Unfortunately, this proof doesn't really prove anything.  The flaw
in the proof is that you failed to account for the time to generate
samples from S.  Consequently, while D might find a collision, it won't
necessarily be any faster than expected.

Let's take an example.  Suppose S is a source that repeatedly picks
a random 256-bit string x until it finds one with H(x) having its low
bit zero, then outputs x.  Then your construction leads to a totally
insecure way of generating a pseudorandom key: the output of your
construction will always have its low bit zero, and thus will be
trivially distinguishable from uniform random.  Does C find a collision
faster than expected?  No, it doesn't.  It halves the number of values
you need from S, but each output from S takes two hash computations
(on average), so everything equals out and there is no contradiction
to the security of H.

Here's another example.  Suppose H(x) = 0^256 || SHA256(x).  Then H
is collision-resistant, but it's output is useless for generating keys,
since these keys will not be pseudrorandom.

Bottom line: Even if H is collision-resistant, this construction may
be insecure for some choices of S, specifically S isn't independent of
H.  Collision resistance alone does not suffice to ensure that this
hashing will yield secure keys.

Notice how the random oracle model that I described avoids this problem.
In my formulation, the source S does not depend on the random oracle:
the distribution on S is chosen before the random oracle is chosen, and
consequently you cannot have these bad interactions.

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