Newsgroups: sci.crypt
From: (Philip Zimmermann)

Subject: Re: IBM-PC random generator, source included
Message-ID: <>
Sender: (USENET Maintenance)
Organization: Climate and Global Dynamics Division/NCAR, Boulder, CO
References: <> <>
+           <>
Date: Sat, 27 Jun 1992 00:58:17 GMT
Lines: 57

In article <> (Terry Ritter) w rites:
> In <>
> (Philip Zimmermann) writes:
>>Suppose we assume that Nico's generator produced 1 bit of "true" randomness
>>for every, say, 3 bits of actual output.  In other words, the output is
>>impure randomness, with 1/3 of true randomness buried somewhere in the
>>output stream, with the other two thirds of output bits being predictible
>>by some highly sophisticated modeling of the physical system.  (my ratio
>>of 3-to-1 is just an arbitrary assumption for this example).
>>Okay, so let's collect 384 bits of Nico's output and reduce it to 128 bits
>>by running it through MD5.  We have thus captured the true randomness
>>that is holographically smeared through his output and distilled it down
>>with MD5 to the essential undiluted randomness.  We aren't just using
>>MD5 to mix it up-- we are using it to distill it down.
> Phil is apparently somewhat less jaded than myself.
> 1. I see no reason to assume that Nico's generator produces
>    any bits of "true" randomness whatsoever.
You may be right-- I must confess I haven't carefully reviewed
Nico's method-- I just assumed it had at least a modicum of randomness
somewhere smeared through it.  Perhaps not.  Two oscillators on the same 
printed circuit board may have some physical coupling that is not 
obvious.  I tend to trust thermal noise more than alledgedly uncoupled
oscillators.  But the PC lacks such a feature. 

> 2. Simply because some complex process somehow converts 384
>    bits to 128 bits is no reason to believe that it has somehow
>    captured the "essential" randomness in any special way.

This is the nature of the avalanche effect of a perfect hash function--
I was using MD5 as an example.  You can replace it with any other stronger
hash.  If your hash is perfect, there is indeed reason to believe that
the essential randomness will be avalanched throughout the output, regardless
of which bits were the random bits in the input. 
>    If we want every bit of the output to depend on every
>    bit of the input we could use CRC's.

I wouldn't trust a CRC for this.  If your hash is one-way, and
cryptographically strong, it would hide any patterns in the imperfect 
noisy input.  CRC is not as good as MD5 for this. 

Since this will be used in a cryptographic application, you have to trust 
a crypto algorithm to protect your message anyway.  Why not trust one
to distill your randomness that is dissolved in your impure bit stream
from your noise source?  If you don't like MD5, pick one you trust as much
as the rest of your cryptography.  If you don't have a crypto algorithm
you can trust to generate a hash, then you probably don't need the random
numbers anyway, because they are mostly needed for crypto applications.