[Cryptography] RNG design principles

[John Denker]

On 11/23/2016 08:28 PM, Theodore Ts'o wrote:
> If you are designing the whole product, and you have complete control
> over the supply chain and manufacturing process, *and* you are sure
> that you have control over the completed product from the assembly
> plant to where it is deployed (so a friendly neighborhood NSA TAO team
> hasn't intercepted the product while it is being shipped), then John's
> approach can work.
> 
> But otherwise, ***any*** hardware random number generator is almost by
> definition "squish". 

That's not a very persuasive argument, for the simple reason
that anybody who believes that, even a little bit, has long
since given up on the field of cryptography and found another
line of work, perhaps as a landscape gardener or as a pizza
deliverator.

That's because the argument applies to everything, not just
the RNG.  If the NSA has pwned the keyboard on which you
type the passphrase, it doesn't matter what you use as your
RNG, or operating system, or browser, or hash function, or
cipher suite.

This leads to:
   RNG Design Principle #0:  We should be just as fussy
     about our RNGs as we are about our ciphers.

I doubt many people on this list would say, "Golly, here
are three different ciphers we found lying around.  We
don't trust any of them, so let's just XOR them together.
That should be hunky dory."

We wouldn't tolerate that for an instant.  Why then should
we accept a similar approach to RNGs?

That's partly a rhetorical question, but partly not.  I
don't know the answer, but here are some possible partial
answers:
  a) Some people don't realize how important the RNG is.
  b) Some people think building a good RNG is easy.
   (It's not.)
  c) Some people think building a good RNG is impossible.
   (It's not.)
  d) Combining all the previous items, some people seem
   to think it "should" be trivial, and are not willing to
   do the work that is required.

Please let's stop with the fatalism and defeatism and start
doing what needs to be done.  If that requires a little bit
of support from farther down in the manufacturing chain,
then so be it.  If this requires declaring a few hardware
configurations to be hopelessly insecure, so be it.

As a separate matter, yes, manufacturers should make stuff
a lot more tamper-resistant.

OTOH before we use up all the world's tinfoil in our hats,
we should note that for every vulnerability implanted by
the NSA there are hundreds that result from plain old
mistakes in the programming.  First things first.

==========================================
In the context of

>> *) What to do with a newly-booted (or worse, newly-created) system that
>>  needs a RNG right away but has not had time to accumulate the adamance
>>  called for in item (1).


On 11/23/2016 08:54 PM, Ron Garret asked:

>  (and what does “right away” mean)?

As previously stated, it means before the system has had time
to accumulate the required adamance.  This could be quite a
long time, since the original item (2) asserted that

>>> it doesn't really matter how good your entropy source is

>  What is an example of a system that needs an RNG “right away”

Well, since the time is unbounded, almost any system will do.
It's hard to think of any operating system where this _isn't_ 
an issue.  So I suggest the original item (2) is not the best
way to frame the discussion.  It would be better to recognize
the need for a modest lower bound on the productivity of the
source.

Meanwhile, if you want a specific example, let's talk about
Linux.  The aforementioned tardy supply must be measured
against the demand, which includes the following:

Linux uses quite a bit of randomness so early in the boot
process that the root partition has not even been mounted
yet, using it for ASLR among other things.  (If that's not
early enough to make this issue seem relevant and interesting,
we can go into more detail.)

More generally, after / is mounted, systems booted from OEM
images need a substantial amount of high-grade randomness for
host keys, plus additional amounts of generic randomness for
ASLR and UIDLs and suchlike.  On top of that, they need session
keys and IVs before they can communicate with anybody else.

These problems are solvable, but it's a lot of work.  Generally
it is necessary to /store/ some randomness somewhere, which is
itself a tricky challenge.  A list of three or four brief items
gives a very misleading impression of how much work is required.