[Cryptography] cheap sources of entropy

[Dennis E. Hamilton]

Regarding dan at geer.org message
Sent: Wednesday, January 29, 2014 20:12
Subject: Re: [Cryptography] cheap sources of entropy


[ ... ] My understanding
is that a mix of N bit streams will be truly unpredictable if any 1 of
the N bit streams is truly unpredictable.

If that is incorrect, what am I missing?  (RTFM is entirely acceptable
and even gracious if accompanied by a pointer to TFM to R.)

--dan

 -- Reply --

I fear that may be an over-generalization.

The comfortable case is that if you have a truly unpredictable source (e.g., stream of uniformly-random 0/1-s) and it is xor-ed with another source of some distribution, the result consists of uniformly-random 0/1-s.

But that is with just one other source and you have to know which one is "truly unpredictable"  (and they both need to be secrets if we're making a security argument).

Of course, if you *know* what the other stream is, you can completely recover the truly unpredictable one.

So the mixing that assures a truly unpredictable result from multiple sources only one of which may be truly unpredictable (and not necessarily known) is clearly more involved than that treasured simple case.  There are more complex transformations in proposed "mixings."  I confess ignorance to how there can be generalization without attention to the specific mixing methodology and what the threat model is against the contraption.  

I'm not suggesting there are not ways to locally mitigate uncertainty of the quality of sources, but how that is accomplished depends on adherence to some important conditions.  I think it's good not to assume that suitable mixings are easily come by and that the assurance of unpredictable results is absolute.

For example, the Fortuna accumulator design depends on there being a least one unpredictable source and there is a complex mixing strategy.  It does not promise unpredictability when the state is compromised, only that there is a mitigating recovery in some period of time.  Protection of seed files across shutdowns/restarts is a related higher-order problem in the case of Fortuna.  There are many implementation delicacies and complexification considerations.

I notice, between the treatment of Fortuna in Practical Cryptography chapter 10 [Ferguson & Schneir, Wiley (2003) ISBN 0-471-22357-3 pbk], and the later Cryptographic Engineering chapter 9 [Ferguson, Schneier & Kohno (2010) ISBN 978-0-470-47424-2], there are a few additional caveats and considerations.  The situation is more nuanced and there is much context to consider, especially in establishing that the effort and implementation doesn't lead to an actual reduction in cryptographic security in the presence of a determined adversary.

 - Dennis