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

David Wagner wrote on 10/25/2005 07:17:28 PM:

> 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.

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.)

> 
> 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.

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.