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

[John S. Denker]

David Honig wrote yet another nice note:
> 
> So work in a Faraday cage...

Tee, hee.  Have you ever worked in a Faraday cage?
Very expensive.  Very inconvenient.

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

I'm not trying to be dense, but I'm totally not 
understanding the distinction here.  The following
block diagram is excellent for focussing the discussion,
(thanks):

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

OK, we have DES as an example of a whitener.  
-- Can somebody give me an example of a "simple hash" 
that performs "irreversible compression" of the required
kind?
-- Isn't the anti-collision property required of even
the simplest hash?  Isn't that tantamount to a very
strong "mixing" property?  If there's strong mixing in
the simple hash function, why do we need more mixing
in the later "whitening" step?
-- What is meant by "cryptologic strength"?  Strength
against what kind of attack?  If this means in particular
the one-way property, why do I need it?  I can understand
why a !!pseudo!! random symbol generator needs the one-way
property, to protect its internal state, but since my
generator has no secret state to protect, why do I need
any cryptologic properties other than mixing?
-- BTW note that the term "avalanche" is probably not
helpful to this discussion, because it is usually defined
(see e.g. Handbook of Applied Cryptography) in terms of
single-bit flips.  The anti-collision property of the hash
function demands resistance to multi-bit flips.

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

If you want to think of it that way, then we come
to the same final state.

I assume digestion means the same as distillation?

> You collect some representative raw data, and run a number of
> entropy measurements on that sample.  You find < 1bit/baud.

In particular you have found an upper bound.
To paraphrase Dykstra:  testing can find an upper bound
on the entropy density, but it can never find a lower bound.

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

No, you have just reached the limits of your chosen "number
of entropy measurements".  You cannot convince a skeptic that
a new test, discovered tomorrow, will not greatly lower your
new (1b/bd) upper bound.

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

I say again that I don't need the one-way property.  At
each iteration, the input to the hash function is unrelated
to all past and future inputs.

We agree that the belt-and-suspenders approach is a standard 
way of achieving high reliability.  It works in crypto and in
many unrelated fields
  http://www.monmouth.com/~jsd/how/htm/misc.html#sec-layers-safety

If you want to XOR the output of the HRNG with some nice
PRNG, that will give excellent error-concealment in the
case of a gross failure of one or the other.

But (minor opoint) I recommend we continue to call a belt a belt, 
and call a suspender a suspender.  Call a HRNG a HRNG, and call
a PRNG a PRNG.  Adding a strong one-way function to my HRNG seems
like a total waste of CPU cycles.

> Once you put it through DES, anything (eg the integers) appears random.
> That's why you measure before whitening, if possible.  

We agree that measuring after whitening is pointless,
given the current state of the art, namely that encryption
algorithms are incomparably stronger than automatic measurement
(pattern-finding) algorithms.

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

Measure what?  Measure how?  If I run diehard on my raw
data it will tell me that the data has entropy density
far less than 8 bits per byte -- but duh, I already knew
that.  Running standard compression algorithms (Lempel-Ziv)
or whatever will give me an upper bound that is much,
much, higher than my calculated lower bound -- so even
if I've overlooked something or made an error in the calculation
the measurement is not sensitive enough to catch it.

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

Gimme a break.  In particular, gimme an example of a crypto 
algorithm that will fail if it is fed with a random-symbol
generator that has "only" 159.98 bits in a 160 bit word.

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

I'm still needing an example of a distiller that has
the weakness being alleged here.  In particular, 
 -- either it wastes entropy (due to excessive hash collisions) 
in which case it isn't a good distiller, and whitening it won't 
improve things (won't recover the lost entropy), or 
 -- it doesn't waste entropy, in which case the output has entropy 
density of 159.98/160, in which case there is nothing to be gained
by so-called "whitening" or any other post-processing.

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

Use it how?  What can the adversary learn that she doesn't 
already know?

In particular, (proof by contradiction) consider the following 
scenario:  suppose she captures 100 bits of output, and wants 
to use it to make some predictions about the next 60 bits of 
output.  She uses the 100 bits to "see back into" the 
hypothetical simple-hash function, learn something about the 
input thereof, and then pushes that forward again through the 
simple-hash function to make the predictions.  But this scenario 
violates the most basic requirements of the hash function, even 
the simplest of simple-hash functions.
 -- First of all, it violates a basic property that any hash
function black-box must have:  The alleged correlations between
the first 100 bits and the next 80 bits means that less than
2^160 different hash codes are being produced.  Therefore there
are excess hash collisions.  Entropy is being wasted.  Bad hash
function.  Bad, bad, bad.
 -- I suspect there are other violations, but I haven't worked
out an ironclad proof, so I'll not mention them.


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

We agree that checking for missing ADC codes is something
that should be done.  I'm working on code to do some of
this but I haven't integrated it into turbid.c yet.

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