building a true RNG

[David Wagner]

> David Wagner wrote:
> > Actually, there is not much hope for such a property.  It is pretty easy
> > to see that, if we make no assumptions on the entropy inputs other than
> > they have sufficient entropy, then no single deterministic algorithm can
> > ever be good at extracting randomness.  If we fix any single extraction
> > algorithm A, there exists a distribution D on the inputs which make it
> > give non-uniform output (for example, D might be the uniform distribution
> > on the set {x : A(x) has its first ten bits zero}).
> 
> That's the kind of thing mathematicians like to say - but how much does 
> it apply to the real world? For example, you can't produce your example 
> set for SHA-1 or MD5, can you?

Nitpick: You can sample from such a set.  You can generate m randomx
values from this set with about 10m computations of SHA-1: simply pick
a random x, check whether SHA-1(x) has its first ten zeros, and if not
go back and pick another x until you find one that works.

However, your general point is correct.  I make no claims about whether
this is a serious problem in practice.  In practice, we would find it
pretty surprising if our entropy sources generated entropy samples that
happen to interact badly with SHA-1.  Normally, we'd expect our entropy
sources to be somehow "independent" of the details of SHA-1.  However,
there is no proof that such a thing can't happen, and the only way I know
to formalize this assumption is using the random oracle model.

In other words, my point is merely that this stuff is very hard to
justify in any rigorous, formal, or precise way.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com