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

David Wagner wrote on 10/25/2005 05:39:20 PM:

> The random oracle model is a heavyweight tool -- but this is heavyweight
> problem.  I'm not sure why you feel it is a lightweight problem. Indeed,
> 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.
> 
> (For others who are reading, by 'this problem' I mean the problem of
> taking a secret input that is known only to have high min-entropy and
> turning it into a pseudorandom value that can be used as a key.  A 
random
> oracle solves this problem, as long as we assume that the distribution
> that that the secret comes from is efficiently samplable and has high
> min-entropy and its distribution is independent of the random oracle.)
> 

I proposed an informal argument to ANSI X9F1, who were dealing this very 
same issue.  I'm not sure if it's rigorous, or even if it is, whether it 
would be tight enough to give a useful result.

* * * *

Let H be a collision-resistant hash.  (Maybe this is too informal or too 
unlikely for some people.)

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, as 
follows. 

Obtain t samples s_1, ..., s_t of S, for a choice of t to be determined, 
and check for a collision among H(s_1), ..., H(s_t).

This sequence is more likely to have a collision a sequence of random bit 
strings H_1, ..., H_t of length hashlen, for the following reasons.

Let T be the set of bit strings of length hashlen, that D reports are from 
H(s) and not a random string R.  The set T is smaller than the set of all 
bit strings, for otherwise D would always report H(s) and have zero 
advantage.

Because D has a positive advantage the outputs H(s_1), ..., H(s_t) are 
more likely to be in T, than not.  These sample values therefore have some 
bias towards T, which increases the likelihood of finding a collision 
compared to random strings.

Some examples may illustrate.  Suppose that the last bit of H was 0, if 
given an input from S.  Then D could distingish H from random with 
advantage 1/2. (Computing this as (1/2 + 1/4)*2 - 1, so advantage ranges 
from 0 to 1.)  Algorithm C can finds a collision in H as though the 
hashlen were one bit shorter.  If D is a more powerful distinguisher, then 
C may be a better collision finder. For example, that the last 10 bits of 
H are 0 given an input from S, then D has advantage 1 - 2^(10), and 
collision-resistance of H is 10 bits less than expected.  Generally, if D 
has advantage d, then C finds collisions lg(1-d) bits better than 
expected.  Admittedly, for small d, then this is insignificant.

Of course, an adequate amount of min-entropy in S is of course required to 
make much less likely that there is no collision in the set s_1, ..., s_t 
than in the set H(s_1),...,H(s_t), for otherwise the collision in the 
latter set may not be a collision in the hash.