[Cryptography] auditing a hardware RNG

John Denker jsd at av8n.com
Mon Sep 9 10:40:21 EDT 2013

On 09/05/2013 05:11 PM, Perry E. Metzger wrote:

>  A hardware generator can have
> horrible flaws that are hard to detect without a lot of data from many
> devices. 

Can you be more specific?  What flaws?

On 09/08/2013 08:42 PM, James A. Donald wrote:

> It is hard, perhaps impossible, to have test suite that makes sure
> that your entropy collection works.

Yes, it's impossible, but that's the answer to the wrong
question.  See below.

On 09/08/2013 01:51 PM, Perry E. Metzger wrote:

> I'll repeat the same observation I've made a lot: Dorothy Denning's
> description of the Clipper chip key insertion ceremony described the
> keys as being generated deterministically using an iterated block
> cipher. I can't find the reference, but I'm pretty sure that when she
> was asked why, the rationale was that an iterated block cipher can be
> audited, and a hardware randomness source cannot.

Let's assume she actually said that.

-- The fact that she said it does not make it true.  That is,
 the fact that she didn't know how to do the audit does not 
 mean it cannot be done.
-- We agree that her claim has been repeated "a lot".  However,
 repetition does not make it true.

So, if anybody still wants to claim a HRNG cannot be audited,
we have to ask:
 *) How do you know?
 *) How sure are you?
 *) Have you tried?
 *) The last time you tried, what went wrong?


Just to remind everybody where I'm coming from, I have been saying
for many many years that mere /testing/ is nowhere near sufficient 
to validate a RNG (hardware or otherwise).  You are welcome to do 
as much testing as you like, provided you keep in mind Dykstra's 
   Testing can show the presence of bugs;
   testing can never show the absence of bugs.

As applied to the RNG problem:
   Testing can provide an upper bound on the entropy.
   What we need is a lower bound, which testing cannot provide.

If you want to know how much entropy there is a given source, we
agree it would be hard to measure the entropy /directly/.  So, as
Henny Youngman would say:  Don't do that.  Instead, measure three
physical properties that are easy to measure to high accuracy, and 
then calculate the entropy via the second law of thermodynamics.

You can build a fine hardware RNG using
 a) A physical source such as a resistor.
 b) A hash function.
 c) Some software to glue it all together.

I rank these components according to likelihood of failure
(under attack or otherwise) as follows:
  (c) >> (b) >> (a).
That is to say, the hardware part of the hardware RNG is the
/last/ thing I would expect to exhibit an undetectable failure.
If you want the next level of detail:
 a1) Electronic components can fail, but this is very unlikely
  and an undetectable failure is even more unlikely.  The
  computer has billions of components, only a handful of which
  are in the entropy-collecting circuit.  Failures can be
 a2) The correctness of the second law of thermodynamics is 
  very much better established than the correctness of any
  cryptologic hash.
 b) The hash in a HRNG is less likely to fail than the hash
  in a PRNG, because we are placing milder demands on it.
 c) The glue in the HRNG can be audited in the same way as 
  in any other random number generator.

Furthermore, every PRNG will fail miserably if you fail to
seed it properly.  This is a verrry common failure mode.
You /need/ some sort of HRNG for seeding.  "Anybody who uses 
deterministic means to obtain random numbers is, of course, 
living in sin."  (John von Neumann)

  Tangential remark:  As for the Clipper key ceremony,
  that doesn't increase the credibility of anybody 
  involved.  I can think of vastly better ways of
  generating trusted, bias-proof, tamper-proof keys.

Bottom line: As H.E. Fosdick would say: 
  Just because you find somebody who doesn't know 
  how to do the audit doesn't mean it cannot be done.

More information about the cryptography mailing list