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

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

Simon Blake-Wilson writes:
>"the thing that turns an unpredictable value into a pseudorandom value" [..]
>The only thing which does it that has come up so far is a random oracle ...
>
>But a random oracle assumption seems like a pretty unsatisfactory solution
>to the problem to me ... It feels like taking a heavy weight tool to solve
>a light weight problem.

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

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

---

From: Jack Lloyd <[email-masked]>
Date: Tue, 25 Oct 2005 17:52:56 -0400

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

-Jack

---

From: Daniel Brown <[email-masked]>
Date: Tue, 25 Oct 2005 18:41:37 -0400

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