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

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

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
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Daniel Brown <[email-masked]>
Date: Wed, 26 Oct 2005 11:43:28 -0400

> necessarily be any faster than expected.

I agree: for my argument to have any chance of saying something 
meaningful, the cost of sampling S is must negligible compared to hashing. 
 Such cheap entropy sources are not necessarily realistic, so the argument 
is very limited in its applicability.  (Your first example, not copied 
here, illustrates the point nicely.)

> since these keys will not be pseudrorandom.

This H has only 128 bits of collision resistance for an output length of 
512 bits. Recall that my argument was to show that non-pseudorandomness 
implies collision resistance less than half the output length.  This 
example has collision resistance at most one quarter of its output length. 
 In fact, if you plug in the lg(1-d) formula, everyone is as predicted.

* * * 

Aside, if H fails to be collision-resistant (for its length), isn't there 
an argument that it isn't pseudorandom?  I suppose that depends very much 
on the definition of PRF, of course.  But let's say collision-resistance 
fails severely in that hashes of random messages collide signficant sooner 
than random strings.  Then a collision  distinguishes the H output from 
random.    This may need a huge amount of H output, and does not at all 
cover the possibility of custom designed collisions.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg