building a true RNG

[David Honig]

At 11:24 AM 7/25/02 -0400, John S. Denker wrote:

>And most particularly I do not
>care if the analog threshold of my soundcard shifts slightly 
>(as a function of recent history, temperature, phase of the
>moon, or whatever).

A change in the analogue threshold of your digitizing step
will change the variability (aka entropy) of your samples.

The practical solution is wide engineering margins and monitor
your raw input.  (And, if you can (SHA users can't), 
measure the data just before it goes into any whiteners you use, 
for belts-and-suspenders assurance that you've compressed it sufficiently.)


>This is the central conceptual point of my paper.  It is
>more important than any particular implementation.  The point
>is that a Random Symbol Generator can be proved correct using
>fairly mild assumptions and premises.

Based on a detailed model of the noise, grounded in physics.
Yep.

Have you seen RNGs based on arrival times of network packets,
or disk accesses, etc.?  I'd extrapolate that you'd not trust
them much given their distance from physics.  (And I'd
agree that a soundcard (or RF card) is preferred and 'free')


>The turning point of the argument is statistical: if I have
>enough entropy at the input of the hash function, and if the
>hash function doesn't waste entropy (by having unnecessarily
>many hash collisions) then the statistics takes over and 
>covers a multitude of sins.  

I don't think "collision" is the right word; you're not doing
a search on hash values which might "collide".


For example, if I have 165 bits
>of entropy at the input of the hash function, the output will
>have 159.98 bits of entropy in a 160 bit word.  

I don't understand this.  If you have 165 bits of entropy in, you should be
able to generate 160 binary symbols with a bit of entropy each.
(You are conserving total entropy, only concentrating it by reducing
the number of symbols.)


>You can shift
>the threshold all you want.  

Shifting thresholds changes entropic content.


>You can add something to the input.

DC doesn't matter, capacitors are cheap :-) 


>If the alleged threshold
>shift is so large as to decrease the variability of the raw
>data, then all bets are off... but that wasn't the question
>that David asked.  The rhetorical question suggested that if
>the threshold shifted "at all" I would have a big problem, and 
>I loudly assert that I don't.  Specifically:  If you give me
>any halfway-reasonable upper bound on the magnitude of the shift, 
>I can design the generator to accomodate that, producing 
>industrial-strength randomness despite such a shift.

This hinges on the definition of "large" and "small"... anyway
generous margins & monitoring work both for steel bridges and RNGs.





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