[Cryptography] [RNG] /dev/random initialisation

Sandy Harris sandyinchina at gmail.com
Mon Oct 28 16:38:45 EDT 2013


John Kelsey <crypto.jmk at gmail.com> wrote:

> On Oct 27, 2013, at 6:17 PM, John Denker <jsd at av8n.com> wrote:

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

We all agree here, at least for /dev/urandom

My understanding, though is that /dev/random uses a different
model requiring a one-to-one relation between (estimated) input
entropy and output size. This makes it safe even if the crypto
used is flawed. That is clearly a desirable property. Whether it
is essential seems debatable, but this is not the place for that
discussion.

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

Yes.

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

In the worst case the attacker has subverted a network switch or router
so he or she knows all packet timings down to the resolution of that
device's clock. There might still be some tiny amount of entropy in
that case due to things on your machine like cache & TLB misses or
having to wait for a lock and lack of sync between your clock and
the attacker's, but basically, you are screwed.

> Now, let's partition the attacker space into two different categories--those
> who eventually get hold of your machine, and those who do not.

We may also need to distinguish between an attacker who can get
root privilege on the running machine (with any sane configuration
non-root access will not pose a threat) and one who steals or seizes
the machine later.

Using an encrypted file system blocks seizure attacks, but that is
inconvenient in many situations and in some jurisdictions there
may be heavy pressure to give up the password.

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

As I see it, the current recommended Linux system of saving 4K bits of
/dev/urandom output for this purpose is a fine answer to this except for
new installs that have no history to get the file from.

> though it's not clear whether or not the previous PRNG states
> will be recoverable.

This should be clear; PFS is a design requirement here. Given the
machine including the saved file, it should be impossible to infer
previous state. Since all output goes through SHA-1 which is
generally thought to have pre-image resistance, it seems clear
enough to me.

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

How about pushing /etc//shadow into /dev/random? Except for a
fully automated install that gives exactly the same accounts and
passwords on every device, that is bound to have some variation
that is unknown outside.

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

Exactly.


More information about the cryptography mailing list