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

[John Denker]

On 07/31/2010 09:00 PM, Jerry Leichter wrote:

> I wouldn't recommend this for high-value security, but then if you're
> dealing with high-value information, there's really no excuse for not
> having and using a source of true random bits.

Yes indeed!

> On the question of what to do if we can't be sure the saved seed file
> might be reused:  Stir in the date and time and anything else that might
> vary - even if it's readily guessable/detectable - along with the seed
> file.      [1]

>  This adds minimal entropy, but detecting that a seed file has
> been re-used will be quite challenging.  A directed attack can probably
> succeed, but if you consider the case of a large number of nodes that
> reboot here and there and that, at random and not too often, re-use a
> seed file, then detecting those reboots with stale seed files seems like
> a rather hard problem.  (Detecting them *quickly* will be even harder,
> so active attacks - as opposed to passive attacks that can be made on
> recorded data - will probably be out of the question.)

I've been thinking about that.  That approach might be even *better*
than it first appears.

By way of background, recall that a good design for the central part
of a PRNG is:
   output = hash(key, counter)         [2]
where
  -- the "hash" is your favorite cryptographically strong hash function;
  -- the "counter" is just a plain old counter, with enough bits
   to ensure that it will never wrap around; and
  -- the "key" is unique to this instance of the PRNG, is unknown to
   the attackers, and has enough bits to rule out dictionary attacks.
  -- There should be some scheme for reseeding the key every so 
   often, using real entropy from somewhere. This is outside of what
   I call the "central" part of the PRNG, so let's defer discussion
   of this point for a few moments.

Note that this works even though the counter has no entropy at all.
It works even if the attacker knows the counter values exactly.

This is crucial to an analysis of idea [1], because I am not sure
that the date/time string has any useful amount of entropy.  Let's
be clear: if the attacker knows what time it is, the data/time
string contains no entropy at all.

Now, if all we need is a /counter/ then the merit of idea [1] goes
up dramatically.

I reckon "date +%s.%N" makes a fine counter.

Note that date is /bin/date (not /usr/bin/date) so it is usable
very early in the boot process, as desired.

This requires that all boxes have a working Real Time Clock, which
seems like a reasonable requirement.

Security demands that the key in equation [2] be unique on a
machine-by-machine  basis.  This means that if I want my "live CD" 
to be secure, I cannot simply download a standard .iso image and 
burn it to CD.  I need to
 -- download the .iso image
 -- give it a random-seed file with something unique, preferably 
  from the output of a good TRNG, and
 -- then burn it to disk.

I have very preliminary draft of a script to install a random-seed
file into an Ubunto live-CD image.  
  http://www.av8n.com/computer/randomize-live-cd
Suggestions for improvement would be welcome.

=========

So, let's summarize the recommended procedure as I understand it.
There are two modes, which I call Mode A and Mode B.

In both modes:

 *) there needs to be a random-seed file.  The contents must be
  unique and unknown to the attackers.
 *) /dev/urandom should block or throw an error if it used before
  it is seeded
 *) early in the boot process, the PRNG should be seeded using
  the random-seed file _and_ "date +%s.%N".  This should happen
   -- after the random-seed file becomes readable
   -- after the Real Time Clock is available
   -- as soon thereafter as convenient, and
   -- before there is any need to use the output of /dev/urandom
 *) This is all that is necessary for Mode B, which provides a
  /modest/ level of security for a /modest/ level of exposure.  
  As a first rough guess I suggest limiting exposure to 1000 
  hours of operation or 1000 reboots, whichever comes first.
 *) Mode A is the same as Mode B, but has no exposure limits
  because the random-seed is replaced before the Mode-B limits
  are reached.  
 *) It is "nice" to update the  random-seed on every reboot.  
  This should happen
   -- after the random-seed file becomes writable
   -- as soon thereafter as convenient, to minimize the chance
    that the system will crash before the update occurs.
 *) The random-seed file should be updated again during shutdown.
  This allows recovery from a situation where the random-seed
  file might have been compromised.
 *) Updating fails if some wiseguy mounts a filesystem in such a
  way that the random-seed file that gets updated is not the one
  that will be used for seeding the PRNG.  AFAICT Mode A depends
  on having the random-seed file in local writeable persistent
  storage, not on (say) a networked remote file system.  In some
  cases the init.d/urandom script would have to be customized to 
  locate the random-seed file on a suitable storage medium.  It
  seems like a step in the wrong direction to use /etc or /lib
  as the routine/normal location for the random-seed file, since
  there are many machines that operate with permanently readonly
  /etc and /lib.  I recommend /var as being most likely to be
  routinely read/writable and persistent.
 *) If updating fails, it is not a tragedy, but it means we are
  operating in Mode B not Mode A.
 *) There should whenever possible be a way of introducing real
  entropy into the PRNG and into the random-seed file.  This is
  important, but the details are outside the scope of the present
  discussion.  Entropy can come from a local HRNG such as Turbid,
  or from a networked random-number oracle if necessary.  Note
  that Mode B is sufficient to allow a system to come up and 
  establish a secure connection to the oracle.
 *) Note for hard-core experts:  I can improve the security of 
  the "emergency boot CD" that I carry in my bag of tricks if I
  also carry a USB memory stick containing a seed file.  After 
  the machine is booted, I can feed that file into the PRNG, and 
  then update the file.  If I do this before exposing the machine 
  to attack, it minimizes the exposure of Mode B.  I call this 
  approach "Mode B+".  I don't expect this to appeal to the general
  public.
 *) Always remember that anybody who is serious about security
  should be using a TRNG not a PRNG anyway.


Also, to summarize earlier messages:
 -- when saving the random-seed file, it is appropriate to save
  the same number of bits as in the PRNG's poolsize
 -- the factor-of-8 bug in init.d/urandom ought to get fixed
 -- the code in init.d/urandom that tries to set the poolsize
  should be removed.