building a true RNG (was: Quantum Computing ...)

David Honig dahonig at cox.net
Mon Jul 22 18:39:30 EDT 2002


At 04:24 PM 7/22/02 -0400, John S. Denker wrote:
>
>For the humor-impaired, let me point out that the lava 
>lamp is a joke.  What it conspicuously lacks is a proof 
>of correctness -- that is, a nonzero lower bound on the 
>entropy rate of the raw data.  

Yes, it is a joke.  However, it is also a viable if low-bandwidth
entropy source.  I disagree that you need to be able to model
the lava (etc) well enough to give a lower bound on the entropy.
(Though its nice if you have such a model).  You should be able
to use any source which you know is not a PRNG as the entropy-source
in a true RNG.  You should be able to use entropy (and stat tests)
to measure the source entropy after digitization.

The "lava" could turn out to 
>have a not-very-complicated periodic pattern.  Secondarily, 
>the pattern changes so slowly that there must be rather strict 
>upper bounds on the entropy rate, small out of all proportion 
>to the cost of the contraption.

Yes, thus the humor.


>A detuned FM card is a bad idea, because it is just
>begging the opponent to sit next door with an FM
>transmitter.

So work in a Faraday cage...


>A microphone causes users to worry about privacy, and
>in any case doesn't add much beyond what you'd get with
>the same input circuitry open-circuited, i.e. everything
>except the microphone itself.

The advantage of a microphone, I suppose, is that you can
hear any jamming attempts..


>Radioactive decay has a poor price/performance ratio, and
>isn't nearly as random as neophytes might think, when the
>data-acquisition hardware is taken into account.

Its a joke/hack of the 'finesse' form.. 


>> which is likely whitened anyway, 
>
>Depending on what "whitening" means;  see below.

You can imagine simple-hashing (irreversible compression) 
as distinct from whitening which is
related to cryptographic strength, avalanche, mixing, etc.

Source --> Digitizer --> Simple hash --> Whitener (e.g., DES)

In this view, SHA combines the compression (aka digestion) 
function with the crypto-strength whitening


>That's the point where I would like some more detail.
>If "measuring" means applying statistical tests, then
>I've never seen such measurements done in a way that is
>really convincing.  Constructive examples would be welcome.

You collect some representative raw data, and run a number of 
entropy measurements on that sample.  You find < 1bit/baud.
You run the data through an algorithm which produces fewer bits.
You measure the entropy of the result.  When successive (or
'stronger') runs measure at 1b/bd, you have distilled
entropy from that sample.  To use this in crypto, you'd
put it through a whitener --feed blocks to DES-- for
belts-and-suspenders assurance.  And because you don't
want someone "looking through" your simple-hashing logic
back to your source.

Once you put it through DES, anything (eg the integers) appears random.
That's why you measure before whitening, if possible.  If
you use SHA you can only measure the input entropy and make
sure you hash enough bits down to produce your output stream.
Since utter crap coming in will look perfectly white coming out.

>I recommend _calculating_ the entropy from physics principles,
>rather than trying to "measure" the entropy using statistical
>tests.  The calculation is based on a handful of macroscopic
>physical parameters, such as temperature, gain, and bandwidth.

You measure because your model may have overlooked something.


>The output of a good distiller has virtually 100% entropy 
>density, i.e. 8 bits per byte.  I say "virtually" because
>perfection is impossible, but 159.98 bits in a 160 bit
>word ought to be good enough for most applications :-).

I agree with the first statement (by definition), I think in crypto you have
to be dubious (paranoid?) of the second.

>I see no point in "whitening" the output of such a
>distiller.

So the adversary can't look back into your logic.  A 'distiller'
which produces quality entropy (after digesting an arbitrary
number of bits) needn't be as opaque as a crypto-secure hash is.


>If whitening means encrypting the output of the distiller,
>I consider that just a more-complicated hash function ...
>just another few rounds.

That's a fine implementation.  Others may wish to separate
the phases (e.g., hardware to do simple-hashing can be high-speed
on the entropy-source-side, and feed slower crypto-hashing (whitening) 
logic on the other side).  But using software to distill your entropy its
easy enough to run a few more iters.  And there are very few users of high
bandwidth entropy.



>> Of course, no one
>> outside the box will know, since you're whitening, but it yields resistance
>> to (albeit difficult) attacks (e.g., your hash turns out to be attackable).
>
>I assume that means "know [that I'm using a distiller]"

No one outside the box can tell the difference between simply
hashed 'noise' and crypto-hashed 'noise'.  Or between those
and a long-sequence PRNG.

Now, if the adversary knows things about your simple-distiller, he
may be able to use that.  If a whitener protects that logic,
he can't see into the distiller.  

If the whitener (your SHA) is broken (eg analytically) then 
its transparent to the adversary.   You could, if you worried
about SHA geting broken, put a structurally different whitener 
after that.



>One random symbol stream looks a lot like another :-).  

Yet like snowflakes they are all unique :-) 


>> I also fail to see harm in measuring/monitoring entropy 
>> as the RNG operates.
>
>Certainly there's no harm.  It's like kicking the tires
>on the used car.  It gives some people a warm fuzzy, but 
>it's far from sufficient for establishing any reasonable 
>level of confidence.
>
>I recommend monitoring the aforementioned macroscopic
>(non-statistical) physical parameters, both to detect
>gross hardware failure and to detect attempted jamming.

Sure, a low-voltage light will alarm faster than an entropy test,
since the latter needs a window of samples to look at.  But 
gross monitors won't detect drift, ADC codes that drop out over 
time, etc.  Particularly if you go directly into a function
whose output will look white even if an input bit changes
infrequently.



CryptoBarTending: Some like to taste the distillation before adding it to
the mix..




 






  





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



More information about the cryptography mailing list