[Cryptography] [RNG] on RNGs, VM state, rollback, etc.

[John Kelsey]

My understanding from Nadia Henninger's talks (and discussions with her) was that many of the appliance network devices that had duplicate primes in their RSA keys were drawing random numbers from /dev/urandom on machines that weren't collecting much entropy.  If this is right, it's a pretty clear demonstration of what can go wrong when /dev/urandom won't block.  (There must be many, many more cases where the machines are collecting too much entropy to get duplicate primes in their RSA moduli, but they're still getting little enough entropy that an attacker can guess the first prime they generated and thus factor their RSA modulus.)

I think the most critical moment in the operation of any RNG is the decision to start producing outputs.  There is no way for the RNG to know whether these outputs will be used for something unimportant, or to generate the high-value keypair that this device will use for the rest of its lifetime.  For devices that do some crypto, it's probably relatively common to have the system generate a high-value keypair very soon after starting up, so that first output needs to be very likely to be secure.  It's worth thinking about what might be done to ensure the best possible chance of this working.   

One other thing you can see from the duplicate RSA keys: many RNGs (I think instances of /dev/urandom drawn on by openSSL) do not incorporate any internal information that can work like a salt.  They should.  If my device has a device serial number, ethernet address, timestamp, etc., those should all be hashed into the entropy pool, with 0 entropy bits assessed.  An attacker trying to guess the state of the pool is in much the same position as an attacker trying to guess a password that was used to derive an encryption key, and any unique-to-this-instance information included works just like salt in a password hashing scheme.  In principle, you could imagine doing an expensive computation to reseed the RNG, but while that would make state guessing attacks a little harder, it would also have a pretty awful performance impact.  

--John