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

[John Kelsey]

On Jan 29, 2014, at 7:38 PM, John Denker <jsd at av8n.com> wrote:
...
> 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.

I very strongly disagree with this.  There is a tradeoff between purpose-built crypto hardware, and off-the-shelf computers and devices pressed into service to do crypto.  The purpose-built crypto hardware and software is a bigger target for very high end attackers, but it is also almost certain to be designed to be harder to tamper with in the field, and it's probably designed with security in mind to a far greater extent than general-purpose hardware and software.  Worse, if some commonplace software or hardware component becomes the thing everyone bases their entropy collection on, that will become a tempting point for a targeted attack, but the sound card manufacturer or whatever won't think they're primarily building a security product.  

A dedicated crypto device can be designed to try to resist a lot of attacks that will pretty trivially compromise most off the shelf hardware and software devices, like side-channel attacks.  It normally will be resistant to compromise by someone who takes over the computer it's installed in or connected to.  It can have an entropy source that's purpose-designed and analyzed as an entropy source, reasonably resistant to intentional or accidental outside interference, etc.  For whatever it's worth, it can also be tested by some organization that validates hardware crypto devices.  Those validations all have problems, but they're probably better than no validation, which is the practical alternative.  

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

How do you recognize when your source is no longer behaving according to the model you so carefully built of its behavior, if you aren't doing some kind of ongoing health testing?  

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

That's something you are going to measure to try to build a model of your source.  But when someone else is trying to check to see if your model makes sense, they're probably going to do statistical testing.  Ideally, that would be carefully tuned to the best model of your source, but in reality, it will probably largely be off the shelf statistical tests, because that's what you can quickly lay your hands on, and expertise is expensive and rare.  

> 
>> 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.
> 
> Let's be clear:  You can have a HRNG without a PRNG but not
> vice versa.

Right.  The goal of your entropy source really needs to be to generate an impossible to guess seed for your PRNG, and then to periodically reseed it.  That means you can probably accept a relatively low rate of entropy produced per second, if you can know how much you are getting.  

--John