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

[John Kelsey]

On Nov 6, 2013, at 8:11 PM, John Denker <jsd at av8n.com> wrote:
...
> 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.

Yes, you're right.  I was thinking of each instance here, but for some reason wrote about distributions instead.  

...
> 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 we update the stored seed before we generate outputs for anything else, then repeating RNG outputs won't happen.  

There's a nicer way to think of this, though.  Consider the persistent state as the state of a PRNG.  That PRNG is used *only* to provide inputs to other PRNGs.  Use CTR-DRBG or HMAC-DRBG from 90A and you have processing of additional inputs built in.  

Then, each time you want to get some bits to add to the system PRNG, you make a Generate call to the persistent-state PRNG, and that updates the persistent state in a way that doesn't allow backtracking or repeated outputs.  Then, use the persistent PRNG's output as additional input for the system PRNG.   

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

I hadn't really thought about how the seedfile or persistent PRNG would affect the /dev/urandom ready flag.  I'm still not sure what the right answer to that is.  On one hand, assuming the starting value of the seed file is unknown to the attacker, /dev/urandom outputs will be secure.  On the other hand, if the starting value of the seed file is known to the attacker (via insider attack, incompetence on the part of the manufacturer, or national security letter), we gain no security from it.  It seems like this works better as a safety net.   

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

If we're talking about /dev/urandom, it should be getting new entropy from the OS over time.  

I'm not a great fan of the /dev/random vs /dev/urandom model, to be honest.  I'd prefer to see everything go through a PRNG--perhaps CTR-DRBG with AES256, or HMAC-DRBG with SHA512.  The OS gets entropy from time to time, and queues it up, and eventually catastrophically reseeds the PRNG.  If there's a high speed hardware entropy source, then that can be done very quickly--perhaps even fast enough to provide full entropy outputs in principle.

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

A PRNG needs an entropy source, but that doesn't have to be a hardware RNG.  It doesn't even have to be on-board.  A smartcard with some persistent storage that can be updated over time can be initialized from a good entropy source once, and then keep running and generating pseudorandom outputs for a very long time.   

--John