[Pkg-sysvinit-devel] init.d/urandom : saving random-seed

[Henrique de Moraes Holschuh]

On Sat, 31 Jul 2010, John Denker wrote:
> This is to answer the excellent questions you asked at
>   http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=587665#81

Thanks.  I also got another reply, and your answers mostly match it.

> > 1. How much data of unknown quality can we feed the random pool at boot,
> >    before it causes damage (i.e. what is the threshold where we violate the
> >    "you are not goint to be any worse than you were before" rule) ?
> 
> There is no possibility of making things worse.  It is like shuffling
> a deck of cards:  If it is already shuffled, shuffling it some more
> is provably harmless.

[...]

> > 2. How dangerous it is to feed the pool with stale seed data in the next
> >    boot (i.e. in a failure mode where we do not regenerate the seed file) ?

[...]

>  b) current /dev/urandom: The consensus among experts is that /dev/urandom
>   is routinely used in ways for which it is not suited.  See my previous
>   email, or refer to
>     http://www.pinkas.net/PAPERS/gpr06.pdf

We could well audit Debian for this.  But the best way of fixing a Debian
system to be more secure as far as the quality of the randomness used by a
random user application will be, AFAIK, is to simply get a medium or high
bandwidth TRNG, and use rng-tools to constantly reshuffle the pool, doing
batched large entropy credits (to cause as many catastrophic reseeds as
possible).  That improves the quality of /dev/urandom output.

I don't have a proper TRNG at the moment, but if I manage to get one (lost
the opportunity to get one a few months ago :-( ), I will improve rng-tools
(the one used in Debian and Ubuntu) to be better suited to that application,
move it to /sbin, and provide an one-shot mode suitable for initramfs usage
to do high-quality early seeding.

>  c) high-grade randomness: For high-stakes adversarial applications, 
>   including crypto and gaming, you really ought to use a TRNG not a
>   PRNG.  In this case, no state is required and no seed is required, 
>   so the question of how to preserve the state across reboots does not
>   arise.  Constructive suggestion:  for high-grade applications, use
>   Turbid:    http://www.av8n.com/turbid/
> 
> To repeat:  For serious applications, I wouldn't trust /dev/urandom at all, 
> and details of how it gets seeded are mostly just re-arranging the deck 
> chairs on the Titanic.  The question is not whether this-or-that seed
> preservation policy is "safe".  The most you can ask of a seed preservation
> policy is that the PRNG after reboot will be _not worse_ than it was before.
> 
> Now, to answer the question:  A random-seed file should never be reused.
> Never ever.

Ok.  Let's differentiate writing to /dev/urandom WITHOUT credit (write to
that device) and with entropy credit (what rng-tools does using IOCTLs).

Writing without credits is supposed to be always safe, even if you write
twice the same data.  If the kernel got any entropy from anywhere else, you
won't dilute the pool and you're not worse off, correct?

So, if you can never be worse off, why shouldn't we allow for a
*failure-mode* where we could possibly reuse the random-seed file?

After all, userspace CANNOT completely seed the Linux kernel RNG, we can
never reset its state using writes (it just shuffles the pool without any
entropy credit), and even a very large entropy credit using IOCTLs will
cause just a catastrophic reseed, which STILL uses the some of the current
state of the pool anyway AFAIK.

If we cannot tolerate this failure mode, we will never be able to use
anything but a TRNG to do early pool shuffling, and must retain what we have
right now (we shuffle after we have write access, so that we can immedialely
remove the seed file).

> Reusing the random-seed file makes the PRNG very much worse than it would
> otherwise be.  By way of illustration, suppose you are using the computer

See above.  Note that in this thread we are concerned only with writes to
/dev/urandom, not PRNGs in general.  /dev/urandom, as far as we've been told
(and as far as I could understand from the Linux kernel code) CANNOT be
truly reseeded, it can only be shuffled.

> On the other hand, it is harmless to make the random-seed file larger than
> it needs to be.

Let's just use a static size of 512 bytes at late init time, and of 2048
bytes at shutdown time, then.  Makes for easier scripts, that only need dd
and nothing else.  We get those bits from /dev/urandom, so it doesn't matter
at all if we will drain 4096 bits or 16384 bits from it when we're about to
shutdown/reboot any normal system (and Debian isn't suitable for stuff that
needs to reboot in less than a second anyway).

We will have a lot of shuffling seed data available at the next boot for the
common case without failure modes, and we will close the "use same seed file
twice" window during late boot, by switching the (already used) seed file
with a new seed file without draining more entropy than the strictly needed
during boot.

That should sort-of future proof us if the kernel increases the pool size.

Alternatively, we could just use 512 bytes for everything by default, and
have that parameter configurable in /etc/default/random.

> Sometimes /dev/urandom is advertised as a "cryptographically secure PRNG".
> If that's what it is supposed to be, it should block or throw an error if
> it is used before it is seeded.  To say the same thing the other way: if 

It is considered to be always seeded, I think. Its seed (the primary pool)
gets a few bits of entropy right away, from disk activity and other sources.
It doesn't matter for this discussion how disputable the randomness of these
bits are, because unless you're going to remove such entropy contributions
from the kernel, the pool will *always* already have something inside when
control is handled to userspace.

So, unless one is going to do kernel surgery, urandom will be already
"initialized" when control is handled over to userspace.  We cannot trust
the quality of any random numbers at that time, except (*maybe*) in very
specific platforms and setups.

> > 5. Is there an optimal size for the pool?  Does the quality of the randomness
> >    one extracts from the pool increase or decrease with pool size?
> 
> If the poolsize is too small, all sorts of bad things happen.

It can hold less entropy, for sure.  But I am certainly NOT going to
advocate increasing pool size over the default 512 bytes (which would help
the kernel handle sudden spikes of entropy requests), because a smaller size
probably helps protects you from overestimation of the entropy entering the
pool (as we keep adding data to it even after it is full, thus eventually we
will really have that much entropy in the pool, and the larger the pool, the
more time it will take for that to happen).

In other words, I don't know enough math and RNG theory to prove that a 8192
or 16384-bit pool would not, in fact, have worse performance quality-wise
because we are NOT sure of the quality and real entropy inside the data we
will feed it, and also if we wouldn't be worse off at early system lifetime,
where the quality of the pool state is really dubious.

One could always have a init pool (small), and swap it with a large pool
later, but I doubt people would accept such a change in the kernel unless it
is backed up by some serious research that proves it is well worth the
complexity on scenarios for which "get a real TRNG" isn't an answer.

> The built-in poolsize is 512 bytes i.e. 4096 bits which is plenty big
> enough for PRNG purposes.  This size is not based on the needs of 

It is not just used for PRNG, though.  It is used (through /dev/random and
internal kernel interfaces) to generate session IVs and keys.

> I recommend not messing with the built-in poolsize.

In that, we agree.

I would appreciate if someone from academia did a throughout study of the
entire random subsystem in Linux and FreeBSD, based on *recent* kernels :-)

Maybe someone already did and I don't know about it.  I still need to read
that paper you mentioned.

> Seeding should happen
>  -- after the random-seed file becomes readable, i.e. after the
>   relevant filesystem is mounted.
>  -- as soon thereafter as possible

Agreed, but that DOES mean we have a failure mode where the seed file can be
used twice to stir the pool, should we crash/reboot before filesystems are
mounted read-write.

And that failure mode is not rare.  It will happen when fsck finds anything
wrong in the / partition, and that is not nearly as uncommon as one would
hope it to be.

So, I'd like to get an confirmation about it, since there was apparently
some contraditory information on your reply about this issue (I probably
misunderstood what you mean, but still, please clarify).

> Note that the filesystem can be readonly at this point.  Read/write is 
> OK too.

And we should move the seed file to somewhere inside /etc or /lib.  It is as
simple as that.  /var cannot be used for any data you need at early
userspace.

> Updating the random-seed file should happen during boot
>  -- after the random-seed file becomes writeable
>  -- as soon thereafter as possible
> 
> Updating should happen again during shutdown, if possible.

Agreed.

> Embedded systems, if they want to have any pretense of security, need to
> have either:
>  a) enough persistent local storage to hold the random-seed, or
>  b) a hardware TRNG that collects real entropy, so that no seed is needed.

Any embedded system worth its price has a TRNG inside somewhere.  Servers
and workstations can add TRNGs to their internal USB ports, or you could
also use that PoS called a TPM if you're going to trust black-box unreviewed
designs from potentially hostile sources, and a complex and very annoying
userspace software stack to get your hands on the random bits.

> For systems that boot from read-only media, such as diagnostic and emergency
> maintenance CDs, there is a serious problem, with no entirely satisfactory
> solutions that I know of.  Suggestions would be welcome.

Well, nowadays datacenters would boot an hypervisor, do all the proper RNG
initialization for the hypervisor (over the network from an entropy source
box, if needed), and have the hypervisor provide a suitable way for the VMs
to ask for initial random data to seed themselves during kernel
initialization.  I believe Linux already allows that on very recent kernels.

What I could do to help other scenarios is move rng-tools to /sbin.  Other
suggestions are welcome.

-- 
  "One disk to rule them all, One disk to find them. One disk to bring
  them all and in the darkness grind them. In the Land of Redmond
  where the shadows lie." -- The Silicon Valley Tarot
  Henrique Holschuh