building a true RNG

[Ben Laurie]

David Wagner wrote:
>>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.

1024m not 10m, surely?

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

Your point appears to be that its hard to justify in the standard 
"infinite computing power" model that maths likes to use, not that its 
generally hard to justify.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

Available for contract work.

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff


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