[Cryptography] suggestions for very very early initialization of the kernel PRNG

[John Denker]

On 11/06/2013 04:40 PM, John Kelsey wrote:

> If the distribution can ship with a unique secret seed value, then
> that resolves the uninitialized rng problem against any attacker who
> doesn't know that seed value.

That's the right general idea, but things are half a step trickier 
than that.

We agree there are steps that need to be taken at the time the 
"distribution" is shipped, but that's not the whole story.  A
great deal of responsibility falls on device manufacturers who 
must /provision/ a unique seed into each instance of the device, 
even though the "distribution" is the same across all devices.
Similarly, a VM operator much /provision/ each VM instance.

The folks who put together the "distribution" need to provide the
tools to make it easy to do the provisioning properly, but they
cannot do the whole job.  

--> Provisioning is a reeaaaally big deal.

> To update the seed, I think it's sufficient to initialize
> /dev/urandom from the seed file and write the first 256 bits of
> output back to the seed file before any outputs are generated for
> anything else.  That guarantees that /dev/urandom never gets seeded
> the same way twice.

Again, that's the right general idea, but there are a few 
devilish details that must be attended to.

We need to think separately about
  a) Initializing the PRNG using the stored seed, and
  b) refreshing the stored seed.

Separation is necessary, because part (a) needs to be done so 
early that in all likelihood, the disk is still mounted read-only.  
Part (b) absolutely needs to be done, but it will have to wait.

Now, this opens up a weird attack, if the attacker can force the
machine to reboot after it has started using the PRNG but before
it can refresh the stored seed.  To defend against this, it pays
to /stir/ the seed using the RTC.  The RTC contains no entropy,
and we assume the attacker knows what time it is, so the RTC
/by itself/ would be utterly useless.  It does, however, serve
as the source of non-repeating values, different from boot to
boot, and when *combined* with a stored seed it can produce a 
different set of randomly-distributed numbers on each boot.
A non-volatile counter would work just as well, but the RTC
is nice because it is almost-universally available.  All this
assumes the stored seed is large enough, random enough, and 
secret enough,

> If possible it would also be nice to have some process wait for the
> /dev/urandom ready flag to be set (assuming one is added), and then
> get another 256 bits from /dev/urandom and write those to the seed
> file.  That ensures that the seed file eventually can become
> unpredictable even to someone who knows the starting value of the
> seed file.

Perhaps that meant to say /dev/random flag, rather than urandom?

If we take /dev/urandom literally, I don't understand the suggestion.
The /dev/urandom ready flag will be raised as soon as the PRNG is 
seeded, which under my proposal will happen "at birth" ... so there 
is nothing to wait for.  The newborn dophin knows how to swim, and 
the newly-hatched rattlesnake is already venomous.

We agree that it is HIGHLY desirable for the PRNG to eventually
recover from compromise, but as I understand it, that happens
when the PRNG is re-seeded from the HRNG.  Asking the PRNG to
reseed itself doesn't make sense to me.  I don't see how that
ever recovers from compromise.

As I understand it, a properly-seeded PRNG is great for meeting 
high demands, including sudden high peak demands.  The PRNG
cannot exist without a HRNG somewhere in the mix, to provide
the initial seed and to provide for recovery from compromise.
However, the coupling between the PRNG and the HRNG does not
need to be particularly close.

I've been gradually collecting a summary of the situation at
   http://www.av8n.com/computer/htm/secure-random.htm

On 11/06/2013 05:08 PM, John Gilmore wrote:

> You're right -- but this conflicts with "secure boot" schemes that
> want to know the image is "authentic" (i.e. signed by a private key
> that isn't on the local machine) before it is permitted to run.

Yup.  Storing the seed in the boot image requires teaching the 
checksum routine to skip the seed section.  This requires work,
but it is entirely doable work.

> It would be unsound to make [read-only] systems fail -- since
> there are millions already in use, and if putting a newer
> OS release on them would cause them to fail, people won't
> bother putting a newer OS release on them.  So, if they don't
> fail, what should we do to declare them "unsound" in a way
> that the system user can detect (and ignore or fix)?

Almost every "read-only" system I've ever seen has some 
non-volatile memory somewhere.  So ... it boils down to 
a configuration problem, i.e. teaching the system how
to store the required seed in the right place ... or how
to get the hypervisor to provide a seed, or whatever.

There will not be a one-size-fits-all solution for these
"read-only" devices.

I see no reason why updating the software on such a system 
would "make it fail".  The worst that will happen is that 
some init script will try to refresh the seed and will be 
unable to do so.  This will leave the system insecure, i.e. 
just as insecure as it already is!