[Cryptography] Hard Truths about the Hard Business of finding Hard Random Numbers

[ianG]

Hi John,

thanks for comments!  I know we're opposed philosophically on this, so
it helps more than normal to have holes poked.


On 30/01/14 03:38 AM, John Denker wrote:
> On 01/29/2014 03:14 PM, ianG wrote:
> 
>> As many have noticed, there is now a permathread
> 
> One reason there is a permathread is that people keep saying wrong
> things.


:) indeed.  That is why I had a stab at writing down the things.  I
think we're at a point where we can do that now.


>> i. Entropy can be objectively analysed as long as we do not have
>> an attacker. An attacker can deliver a faulty device, can change 
>> the device, and can change the way the software deals with the
>> device at the device driver level. And much more...
> 
> That's a red herring.  The attacker can also bugger the BIOS, 
> bugger the keyboard scanner, et cetera.  Supply-chain trust is a
> problem.  This problem does not affect entropy-sources any more
> than it affects a hundred other things.  If you're going to give up
> on entropy because of supply-chain trust issues, you ought to give
> up on everything.


Well, that's just it.  The people who manage the supply chain will
give up far faster than you.  However, our job as programmers still
goes on, and we have to deliver software that eliminates problems, not
comes with instructions like "don't give up!"


> Also:  One point that the web page doesn't mention:  It helps to
> use general-purpose components.  Using special-purpose crypto chips
> (including RNG chips) is like putting a "kick me" sign on your own
> back.  In contrast, a sound card can be put to lots of different
> uses, and it is relatively hard for the bad guys to mess with it in
> a way that subverts the crypto without making the device unusable
> for other purposes.


Good point, I copied that in almost as is.


> This doesn't solve all the world's problems (angry birds) but it
> helps.
> 
>> No Test.
> 
> That's imprecise and overstated.


Yes, that's an inevitable result of trying to compress our knowledge
into enough of a story and enough of a plotline to get people to the
end, before they get bored and wander away.

As a practical pedagogical technique, we must be bold and state hard
truths.  Subtleties will be lost and should only be introduced where
essential.


> Not all measurements are created equal. a) We agree that
> statistical tests on the output are mostly window-dressing.  As
> Dykstra said, testing can show the presence of bugs, but it can
> never show the absence of bugs.
> 
> b) On the other hand, there are some things that do need to be
> measured, such as the impedance, gain, and bandwidth of the source.
> These physical measurements are not even remotely in the same
> category as statistical tests on the outputs.
> 
> Statistical tests on the output are mostly pointless but harmless. 
> The real point should be twofold: a) Do not rely on statistical
> tests on the output.


I agree with what you state, but this is why context is important.  It
is fine when we are in the 'hardware' domain to talk about calibration
and measurement, but in the 'software' domain we don't really have
that luxury.

Most developers in this area are in two worlds:  one is the world of
Ted and John who are developing a tool that is used, as is.  So it is
modelled to a 'perfect' design and delivered to a wide unsuspecting
unwashed audience.  Ted gets to lean on CPU RDRANDs and Johm gets to
lean on FIPS...  (This is not written for them.)

The other world is people like myself who write applications and have
to build a component that does the job.  So the requirement (audience)
is very precise, but the platform is highly variable.

In my field, today, I'm using android and bsd.  In order to do a
calibration I have to look through the app, through Java (and past JCE
of course) to the OS.  Then I have to look past the sandbox / VM.
Then I have to look at the devices to see what I can get from them.

Yet, I can't predict what phone my software will run on.  I can't see
what Oracle/SUN have done with Java.  I can't see what the Android
team has done with their OS (Linux, another black hole of wisdom) or
hook-up to sandboxes and Jave and whathaveyou.  Androids typically
have a sensors API but the sound is a very different proposal -- it's
supposed to be a phone!  The BSDs typically have a soundcard by no
sensors API.

There is no common hardware available, 'cept maybe the CPU and RAM.


> b) Do the calibration.  Do the /right kind/ of measurements. An
> ounce of calibration is worth more than a ton of wishful thinking.


Point, I made a note.

>> ii. This approach is complete if we have control of our 
>> environment. Of course, it is very easy to say Buy the XYZ RNG
>> and plug it in. But many environments do not have that
>> capability, often enough we don't know our environment, and the
>> environment can break or be changed. Examples: rack servers
>> lacking sound cards; phones; VMs; routers/firewalls; early
>> startup on embedded hardware.
> 
> Yeah, different machines will have different peripherals. So what?
> We have for decades been dealing with different graphics hardware,
> different disk hardware, different networking hardware, even
> different math coprocessors. We deal with this by loading different
> drivers and different libraries.
> 
> When faced with the equivalent problem in RNG space, it would be
> ridiculous to just give up.


Not giving up, clearly :)  Going to an engineering solution.  I can't
buy or specify any form of hardware at all.  So I go redundant.  What
choice do I have?


>> . In conclusion, entropy is too high a target to reach.
> 
> Nonsense.  It is definitely reachable.  Yeah, it's hard, but lots
> of things in cryptography are hard.  We don't just give up when we
> see something that requires a bit of work.


It's reachable *if we can control the environment*.  Otherwise...


>> Cryptographically secure random numbers (or CSRNs) are numbers 
>> that are not predictable /to an attacker/.
> 
> I assume that refers to something involving a PRNG.  The problem 
> with all such things is that they require a seed ... whereupon we
> need a HRNG anyway.


Yes, this is a good point.  I've made a note to stress that.


> Let's be clear:  You can have a HRNG without a PRNG but not vice
> versa.
...
> To summarize:  Giving up on the HRNG is neither necessary nor 
> possible.


I think in a sense this is true.  But it is also a fact that people
like myself are too far from the hardware.  It matters not how we
strive to touch it, it's still too far away.

Rather than giving up, what is left then is the old engineer's trick
of redundancy.

Thanks again for comments!

iang