[Cryptography] [RNG] /dev/random initialisation

[John Kelsey]

On Oct 27, 2013, at 6:17 PM, John Denker <jsd at av8n.com> wrote:
...
> On 10/24/2013 07:59 AM, John Kelsey wrote:
> 
>> a.  Get 256 bits of entropy from the OS.
>> b.  Get 256 bits of entropy from the hardware entropy source.
>> c.  Ping several hosts on the internet and measure the response time, and fold that into your seed.
>> d.  Fold your ethernet address, IP address, and serial number into the seed.
>> e.  Fold the installed-at-birth secret 128 bit value from your device into the seed.
>> 
>> Initialize a PRNG with all that, and the attacker is in an extremely
>> hard place, as he has to be able to guess all five elements. (d)
>> isn't all that hard to guess, but the rest will in general be very
>> hard to guess.
> 
> Some comments:
> 
> a) If you have 256 bits of honest-to-goodness entropy from
> /any/ source, OS or otherwise, then that's more than enough
> to seed the PRNG, and nothing on the list matters.

Right.  My point is that we want to consider the possibility that one or more of our sources aren't good, but we don't know which.  For any minimally decent PRNG, if we feed it 128 bits of entropy plus a million bits the attacker gets to choose, we should still get a secure PRNG state.  

So, we get 256 bits of entropy from the OS.  If the OS can actually find that much entropy, then we're done--we are now in a secure state.  If not, though, the hardware entropy source can come to our rescue.  But suppose the hardware RNG is cooked or broken, and the OS isn't able to collect enough entropy.  Then, what should we do?  

Well, let's think about our attacker.  What we really care about w.r.t. PRNG seeding is not the ultimate question of how unpredictable the seed is.  We care about how unpredictable it is to the attacker.  

So, let's partition the attacker space into two categories--some attackers are watching your network traffic at the time you generate your key, and some aren't.  If we are sampling the high-speed counter every time a packet arrives and folding that into our PRNG seed, then it seems almost certain to me that an attacker who isn't watching your network traffic right then is going to be unable to reconstruct exactly when each packet arrived.  Attackers that are not monitoring your network traffic right then are just ruled out.  To make this work even better, do some kind of broadcast on the local network, asking any other devices to respond with 256 bits from /dev/urandom or the system PRNG.  An attacker who is eavesdropping will see this and you won't benefit from it, but attackers who aren't eavesdropping on your network traffic just don't know what was sent, and so you have a secure PRNG seed with respect to those attackers.  

Now, let's partition the attacker space into two different categories--those who eventually get hold of your machine, and those who do not.  If there is a fixed 128 bit random number installed on your machine (different for every one), and you feed that into your PRNG seed, then the attackers who don't eventually get hold of your machine are lost--they simply don't know those 128 bits, and can't guess them, so your PRNG is secure w.r.t. them.  (A stored seed is even better, though it's not clear whether or not the previous PRNG states will be recoverable.  In its absense, I'm not sure if there's anything else that could be used to get some unique information from the machine that only someone on the machine could get.)  

What we can get from this is that, even if the OS and hardware RNGs are weak, the only attackers who can exploit this are those who were eavesdropping on your net traffic right before you generated your keypair, and who got hold of your machine afterward.  Other attackers simply can't get anywhere.  

I'd love to think of some more classes of attacker we could rule out entirely.  Even a high precision timestamp doesn't do much good, since there are only so many times this particular device could have generated their key.  

Now, at last, we come to the "salt" inputs--ethernet address, IP address, serial number, etc.  (Timestamp is good here, too.)  These aren't intended to provide any entropy.  Instead, their goal is to work like salt in a password hashing scheme.  

Let's suppose the attacker has a predictive model that lets him guess a lot, but not all, of our entropy.  By including the "salt" inputs, he is forced to rerun his attack on each machine with the same configuration, rather than being able to run his attack once and then look for matching keypairs from every machine with the same configuration.  

--John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131028/29cbf997/attachment.html>