init.d/urandom : saving random-seed

[John Denker]

Hi Henrique --

This is to answer the excellent questions you asked at
  http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=587665#81

Since that bug is now closed (as it should be), and since these
questions are only tangentially related to that bug anyway, I am 
emailing you directly.  Feel free to forward this as appropriate.

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

This property is a core design requirement of the PRNG, and has been
for ages.

Note that writing to /dev/random requires no privileges, which makes
sense in light of this property.

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

As is so often the case in the security / crypto business, the answer
depends on your threat model.  The demands placed on a PRNG vary wildly
from one application to another.  Interesting use cases include:
 a) low-grade randomness: For non-adversarial applications such as Monte
  Carlo integration of a physics problem, almost any PRNG will do.  Even
  a LFSR would do, even though a LFSR can easily be cryptanalyzed.  The
  point is that nobody is going to bother attempting the cryptanalysis.
 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
 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.

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
to help you play "battleship" or "go fish" against a ten-year-old opponent.
If you use the same 'random' numbers after every reboot, the opponent is
going to notice.  You are going to lose.  In more-demanding situations,
against an opponent with more skill and more motivation, you are going to
lose even more miserably.

> 3. What is the optimal size of the seed data based on the pool size ?

While we are on the subject, let me point out a bug in all recent versions
of init.d/urandom (including the current "sid" version as included in
initscripts_2.88dsf-11_amd64.deb) : 
  The poolsize as reported by /proc/sys/kernel/random/poolsize has units 
  of _bits_ whereas the random-seed filesize has units of _bytes_.  It is 
  a bug to directly compare these numbers, or to set one of them based on 
  the other.  There needs to be a conversion factor, perhaps something like
  this:
      (( DD_BYTES = ($POOLSIZE + 7)/8 ))

Now, to answer the question:  It suffices to make the random-seed file 
contain the same number of bits as the PRNG's internal state vector 
("poolsize").  Call this the BBJR size (baby-bear-just-right).

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

In contrast, using the size of the random-seed file to reset the PRNG's 
poolsize is a bad idea, especially if the random-seed file is (intentionally 
or otherwise) bigger or smaller than the BBJR size.

Semi-constructive pseudo-suggestion:  *IF* we want to keep track of the 
poolsize, it might make more sense to store it separately and explicitly, 
in its own file.  This would make the code simpler and more rational.

On the other hand, I'm not sure why there is *any* code in init.d/urandom
for saving or setting the poolsize.  Chez moi /proc/sys/kernel/random/poolsize
is read-only.  Indeed I would expect it to be read-only, since changing 
it would have drastic consequences for the internal operation of the PRNG, 
and looking at random.c I don't see any code to handle such a change.

So the real suggestion is to eliminate from the Linux init.d/urandom 
all of the code that tries to ascertain the size of the random-seed 
file and/or tries to set the poolsize.  (For non-Linux systems, the
situation may or may not be different.  I have no comment on that.)

> 4. How dangerous it is to have functions that need randomness (like
>    encripted network and partitions, possibly encripted swap with an
>    ephemeral key), BEFORE initializing the random seed ?

An unseeded PRNG is unsuited for any purpose except possibly the lowest
of low-grade non-adversarial applications.  It is grossly unsuited for 
any security-related application.

The security literature contains many examples of serious attacks based
on figuring out the state of the victim's PRNG.

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 meant to be used as an unseeded PRNG, it should be renamed to 
/dev/nonrandom so that users are not deceived.

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

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 
/dev/urandom but rather of /dev/random, to serve as a buffer in cases
where the incoming supply of entropy accumulates slowly but the outgoing
demand is subject to sudden peaks.

I recommend not messing with the built-in poolsize.

> a) Is it better to seed the pool as early as possible and risk a larger time
>    window for problem (2) above, instead of the current behaviour where we
>    have a large time window where (4) above happens?

Seeding should happen as soon as possible.  Seriously, any PRNG that makes
any pretense of security should block or throw an error if it is used before 
it is seeded.

I don't see how early seeding makes problem (2) any worse.  Late seeding
causes all sorts of problems.

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

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

Note that it should be considered an error to mount something else on top 
of /var, using /var as a mountpoint.  Ditto for the other directories in 
the path leading to random-seed, typically /var/lib/urandom/random-seed.  
Such a mount is bad because it makes it impossible to update the relevant
version of random-seed (unless somebody carefully unmounts the offending 
filesystem first, and there's no code to do that).

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.

> b) Is it worth the effort to base the seed file on the size of the pool,
>    instead of just using a constant size?  If a constant size is better,
>    which size would that be? 512 bytes? 4096 bytes? 16384 bytes?

Yes, the size of the random-seed file should be set according to the poolsize
(but not vice-versa).

> c) What is the maximum seed file size we can allow (maybe based on size of
>    the pool) to try to avoid problem (1) above ?

This is a non-problem.  Just use the poolsize to determine the file size.
This will never cause a problem for the PRNG.

At present the filesize should be 512 bytes i.e. 4096 bits.  This is likely
to remain so for the foreseeable future.  If the filesystem cannot handle a
file of this size, then we are talking about a highly specialized application,
requiring detailed engineering, quite outside the scope of the standard
initscripts.

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.

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.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com