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

[John S. Denker]

David Honig wrote:

> The thread here has split into "QM & True Randomness" and
> "what do you need to build a true RNG"...

Yup.

> >Specifically:  The "executive summary" of the
> >principles of operation of my generator is:
> > -- use SHA-1, which is believed to be resistant
> >    to collisions, even under chosen-input attack.
> > -- use it under conditions where the adversary
> >    cannot choose the input.
> > -- the rest is just physics and statistics.
> 
> Sure.  There are many examples of this kind of generator,
> using physical sources from video'd lava lamps to radioactive decay
> (incl. semiconductor junctions, resistors, microphone,
> detuned FM radio cards).  

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

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

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.

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.

> >2) Vetting a generator by trying to "detect" patterns
> >in the output is like kicking the tires on a used car
> >... go ahead and do it if you want, but it is far from
> >sufficient for establishing any reasonable standard of
> >correctness.
> 
> You can't vet a RNG by looking at its output, 

We agree.

> which is likely whitened anyway, 

Depending on what "whitening" means;  see below.

> but you can gain confidence by looking at its design 

Yes!

> and measuring the entropy in the raw-physical-source derived bitstream.

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.

Just saying "Joe Schmoe applied all the tests he could 
think of and couldn't compress it more than XY%" isn't
going to convince me.

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.

> If the raw source has < 1 bits/symbol (and it will), 

Commonly but not necessarily < 1 bit/symbol.
Depending on what you mean by "symbol", a 24-bit 
audio card provides a low-cost counterexample.

> it'd be nice if a later stage
> distilled this to near 1 bit/symbol, before whitening.  

We need to be more specific about what the symbol
alphabet is.  If the symbols are ASCII characters,
1 bit per symbol is not nearly good enough.

More importantly, I don't know what whitening means in 
this case.

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 see no point in "whitening" the output of such a
distiller.

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

> 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]"

Well, in principle nobody outside the box knows _anything_
about the mechanism (unless they read the documentation).
One random symbol stream looks a lot like another :-).  
Attackers can always check to see whether the generator 
is broken or not.  But if it's not broken, all they can 
do (from outside) is measure the output-rate.

> 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.
But that's very different from the traditional (and
hereby deprecated) procedure of "measuring" the entropy
using statistical tests.

For lots more detail, see
  http://www.monmouth.com/~jsd/turbid/

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