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

[Watson Ladd]

On Mon, Oct 21, 2013 at 5:07 PM, John Kelsey <crypto.jmk at gmail.com> wrote:
> A formal security model is exactly what the /dev/random paper had.
>
> Here's a much less formal one, from my paper with Bruce and David and Chris many years ago:
>
> An RNG is in a secure state if it is generating outputs that no attacker can predict or distinguish (up to some bounds on the number of outputs) from ideal random bits.  If it is not in a secure state, then it must be in an insecure state.  For most decent RNGs, being in an insecure state means the attacker knows or can guess the entire internal state.
>
> If an RNG is in a secure state, no additional input fed into it and no plausible amount of output from it should put the RNG into an insecure state.  (At some point, any deterministic rng must cycle, so there has to be a limit on the number of outputs, but that can be huge.).  The old DSA RNG and the RSAREF RNG both had problems with this.  In general, a good technique here is to hash the external input before combining it with the RNG state, or to generate a new RNG state using the RNG and then XOR the input into it.
>
> If an RNG was previously in a secure state, but has been compromised and now is in an insecure state, then the attacker mustn't be able to go backward and learn previous states or predict previous outputs he hasn't seen, even if he is given some previous outputs and asked to predict others.  This is ensured by periodically applying a one-way function to the RNG state.  The simplest one to use is the RNG itself--just use the RNG to generate a new RNG state.
>
> If an RNG is in an insecure state, it should be able to get to a secure state if given sufficient entropy (say 128 bits).  This is the reason for "catastrophic reseeding."  You want to put in 128 bits of entropy all at once, rather than trickling in a few bits, then generating another output, because an attacker who starts out knowing your state can guess the entropy input, and check his guess against your RNG output, and can iterate this process to keep you from ever reseeding.
>
> Let's consider a system that starts up for the first time today, and very quickly generates a high value keypair.  We are concerned with whether the RNG is in a secure state at the moment the randomness is used to generate the keypair.
>
> The attacker wants to guess the input to the key generation mechanism.  He buys several instances of the same device and reverse-engineers them and experimentally determines what entropy values they collect before the key generation is done.  He builds a predictive model.
>
> Now, to understand the security of this system, we need to know something about how often his predictive model guesses right.  This works very much like a password guessing attack--the attacker runs his model to generate huge numbers of predicted entropy inputs for the RNG, sort of like a John the Ripper for the system's entropy collection mechanism.
>
> Think of the RNG and the key generation mechanism as being a little like a password hash algorithm, with the public key (or the first prime factor of the RSA modulus) being the password hash.  The attacker has to run his entropy input guessing engine and check each guess against a given machine's public key.
>
> Suppose the RNG doesn't include stuff like a MAC address or IP address.  Then the attacker need only run his entropy guessing routine once, and precompute some huge table of possible keys or prime factors to try.  Perhaps he will do some clever time/memory tradeoff here as well.  At any rate, if 50% of the devices' entropy inputs can be guessed with 2^{40} work, then the attacker does one big 2^{40} precomputation, and he can break 50% of the devices' keys, whenever he sees them.  It's just like unsalted password hashes.
>
> Suppose the RNG hashes in a MAC address.  Immediately, the attacker has a worse life--now with the same amount of entropy, he must do a new 2^{40} search each time he encounters a new device with a public key.  It's like a salted password hash.
And with a wire that costs 25 cents connecting the wallwart to the
interrupt pin we've got 60 Hz (50 in Europe) uncorrelated to our local
clock. Measure the drift, and in 5 seconds we are done collecting 250
bits of entropy (one bit per interrupt).

2^40 is not a lot for your colleges in Fort Mead. Imagine this is host
key generation on hosts on large, important, networks. Piddling with
the MAC key won't keep out anyone who seriously wants to get in.

>
> Suppose the device pings a dozen hosts on the internet and times the returns of the packets, and hashes those into its RNG state before it generates its keys along with the MAC address.  Now, an attacker who wants to recover the key probably needs to have been observing the device's local network at the time the key was generated, or it won't have enough information to predict the RNG state.
>
> Supose the device has a factory-installed secret value of 128 bits, which is stored forever on the device.  If it hashes this secret into the RNG state before generating its key, then the attacker must compromise the device or the manufacturer to guess the key.
>
> And so on.  For the initial state of the RNG, you get about 90% of the right intuitions for thinking about the attack by thinking about a password cracking attack.
>
> --John
>
>
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin