[Cryptography] where shall we put the random-seed?

[John Denker]

This is in some sense a progress report, indicating how far I
have gotten toward answering the questions that Rich Salz and
others have been asking about how to provide practical, usable
randomness.

AFAICT the only winning strategy is to store a random-seed file
somewhere, make sure it is properly initialized, make sure it
is properly protected, and make sure it gets loaded very, very
early.  This raises a number of questions, including:

/Where/ should we put the random-seed file?

   If it's not obvious why I'm asking, see the background <*>
   section below.

I think I know the right answer in some cases, but not in others.
Let's proceed with a case-by-case analysis:

1) On an ordinary full-featured desktop, laptop, or server system,
the obvious choice is
    /var/lib/systemd/random-seed  (for recent Ubuntu systems), and
    /var/lib/urandom/random-seed  (for everybody else)

That is where the system startup and shutdown scripts expect to find
it.  The plan is to teach grub to look for it there, and to pass it
to the kernel, so that it is available from time t=0 onwards during
the boot-up process.

Open issues include:

1a) Obviously it is imperative that the random-seed file be properly
initialized, even on newly-installed systems that are about to boot
up for the first time.
  ++ The Debian installer does initialize the random-seed.  Kudos!
  -- The Ubuntu installer does not.  I filed a bug report:
        https://bugs.launchpad.net/bugs/1651947
     It will be interesting to see what comes of this.

1b) Initialization of the newly-installed system assumes that the
installer system itself had some decent randomness to give out.
This is "slightly" less critical in the sense that the installer
might be able to gather some randomness from a HRNG, using time
and hardware resources that might not be available to the installee
at the time when its RNG is most needed.


2) Let's consider a typical "Live CD" setup.  Note that "Live"
image and "Installer" image are essentially synonymous these days.

In particular, let's start by imagining it embodied on an actual
CDrom.  In my part of the world, such things are about as scarce
and impractical as penny-farthing bicycles.  However, the major
distros seem committed to supporting this format, so let's play
along and see what happens.

For now we assume no persistent storage.  Persistence schemes
will be discussed later.

The distributed image actually contains three filesystems:  The
top-level ISO-9660 filesystem, the initrd.lz, and the squashfs
filesystem.

The only reasonable usage scenario I have been able to think of
goes like this:  The user
  a) Downloads the image from the distro site in the usual way.
  b) Runs a very simple script that randomizes the random-seed
   file in the image.
  c) Burns this one-of-a-kind image onto the physical CD.

It does no good to download a "Live CD" image if it has a built-in
«secret» that can't be modified.  As Ben Franklin pointed out, a
shared secret is no secret at all.  On the other hand, this scheme
requires "some" random-seed file to be present in the downloaded
image, as a plain file of the appropriate length (or longer) in
the top-level ISO-9660 filesystem.  Rationale: such a file can
easily be updated in place, in the image as it sits on the hard
disk, just prior to being burned to CD.  In contrast, a file
inside the squashfs would be prohibitively inconvenient for
Joe First-Time User to update.

To protect against replay attacks, the device driver stirs the
seed using the real-time clock.  The point is, a RTC (or even
a counter) stirred into a 512-byte random seed is a lot harder
to crack than either one separately.

2a) Open issue:  On hardware without a RTC, I'm not sure what
to do.  Some such systems may end up on the list of platforms
that are not secure and cannot be made secure.

2b) The system init scripts need to be taught to look for the
file on the outer ISO-9660 system.  It's readily accessible
at runtime via /cdrom.

2c) Or perhaps some more specialized script could append bits
from the CDrom file onto the end of the file at the normal
location.  There are two issues here: we need the specialized
append script itself, and we need the init script to be smart
enough to use the *entire* initialization file.  Right now
some versions only look at the first 512 bytes -- don't ask
me why -- so appending stuff to the end wouldn't do any good.

Question:  Does anybody have a preference for (2c) over (2b)?
My guess is that (2b) is cleaner;  fewer moving parts.

2d) One more issue:  You have to guard the CD from now until
the end of time.  You don't want the bad guys to learn the
random-seed that you used.


3) Now consider a "Live CD" image embodied on a flash drive.
This requires some sort of chain loader.

If we don't do anything fancy, such a setup has no built-in
notion of persistence, so it reduces to the case previously
considered, with one major exception:  The flash hardware does
actually permit persistence.  It is physically possible to
update the random-seed file from time to time, whether the
software realizes it or not.
  ++ The "Live" system could do this by writing to the device
   where the ISO image is sitting, updating the file in place.
  ++ If necessary, the flash drive can be carried to another
   machine, so that the random-seed can be updated that way.

In such a situation, putting the random-seed file in the
top-level ISO filesystem is the only thing that makes sense
AFAICT.

Open issues include all the issues mentioned in item (2).

In addition, we need the distribution to include a script
that will update the random-seed.  The existing scripts
have no clue about this;  they tend to assume that anything
they need to do can be done within the normal filesystem.

On the other hand, it may be that some people actually want
(or think they want) absolutely no persistence, even on a
drive that would permit some.  Would anybody actually object
to a persistent random-seed?  Should we make it optional?
Note that it's hard to configure options on a read-only
filesystem.


4) It is possible to have a flash drive with a "Live CD" image
in one partition, plus an additional "persistence partition"
that gets mounted, as part of a unionfs, at the root of the
"Live" system.  This is supported by Ubuntu;  I don't know
about the other distros.  This is similar to the file structure
used in a lot of network appliances and IoT objects.

As far as the software is concerned, the result looks essentially
like a normal system [case (1) above].

One issue is that if you're not careful, such a setup could
cause a lot of wear and tear on the flash medium.   Other than
that, AFAICT there "should" be no new security issues.  Even
so, it's hard to make anything foolproof, because fools are so
ingenious.


5) Here's another scheme:  An ISO image on flash requires
a chain-loader.  It could be a very simple 440-byte thing
stuck into block 0 of the drive, or it could be something
very much fancier, such as grub.

If we assume grub is present, we can put the random-seed file
almost anywhere, e.g. in a tiny security-only persistence
partition.  This is in some ways simpler than imposing
persistence on the entire filesystem from the root on down
... and less likely to cause wear and tear.

Open issue:  It would be nice to standardize the location
for such a thing, and then teach the system init and shutdown
scripts to update the random-seed there.


=========

Questions:  Does any of this make sense?  Does any of it
not make sense?  Does anybody have any better ideas?  Are
there any other use-cases that need special consideration?


=================================

<*> Background, Motivation, and Philosophy <*>

Here are some more principles that all-too-often get left off
the lists people make:

 *) Three may keep a Secret, if two of them are dead. 
			-- Benjamin Franklin (1735)

   In other words, a shared secret is no secret at all.  If
   multiple system have the same random-seed, it just creates
   an incentive for the bad guys to steal one of the systems
   and lift the seed.

Also:

 *) Having a good source of randomly-distributed numbers is
   important.

   If you don't believe me, just look at the enormous efforts
   the NSA put into subverting the Dual_EC_DRBG.  They wouldn't
   have bothered, if it wasn't going to open up important lines
   of attack.

Also:

 *) The RNG that is offered to ordinary users must never block and
   must never return low-quality results.

   To say the same thing another way:  If you find yourself worrying
   over the design decision as to whether to block or whether to return
   not-very-random results, you have already lost the game.  Go back
   to the drawing board and fix it so that question never comes up.

   The typical linux /dev/random doesn't meet this criterion, because it
   very commonly blocks.  The typical linux /dev/urandom does not (at
   present) meet this criterion, because it is a PRNG and there is no
   guarantee that it has been properly initialized.  The new getrandom()
   function adopts the lose/lose strategy of requiring the user to answer
   a question that cannot be answered and should never have been asked.

And that leads us to the grandest principle of all.  As previously
mentioned:

 *) The grand principles don't do you a bit of good unless you take
   care of a whole lot of grotty details.

   I am reminded of the famous question:
     What's the difference between theory and practice?

   To which the answer is:
     In theory there is no difference, but in practice there is.

   In that spirit I would say that in theory it doesn't make much
   difference where we store the random-seed, but in practice it does.