[146929] in cryptography@c2.net mail archive
[Cryptography] auditing a hardware RNG
daemon@ATHENA.MIT.EDU (John Denker)
Mon Sep 9 18:45:53 2013
X-Original-To: cryptography@metzdowd.com
Date: Mon, 09 Sep 2013 07:40:21 -0700
From: John Denker <jsd@av8n.com>
To: cryptography@metzdowd.com
In-Reply-To: <20130908165117.4a6c94e4@jabberwock.cb.piermont.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
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
dictum:
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
detected.
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.
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography