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

[Jason Cooper]

Hi John!

On Mon, Dec 26, 2016 at 08:25:32PM -0700, John Denker wrote:
...
> 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.

Almost.  The exception is encrypted disks.  In that scenario, grub can't
read the /var/lib/*/random-seed until after the kernel and init are
launched.

My proposal [1] has been to store it in /boot, since random-seed is at
least as sensitive as the kernel and initrd images.  Then, the
bootloader has access to it *before* kernel load.  This allows us to
load random-seed into RAM and pass the addr,size to the kernel.  That
should be sufficiently simple enough for the decompressor to leverage
when setting up KASLR.  Once random.c initializes, it can consume the
remainder of the seed for the normal entropy pools (non-credit).

I've also been looking at how to do this on embedded systems (no grub,
devicetree, etc).  It's pretty easy, but for the currently deployed
systems out there with legacy bootloaders (don't understand devicetree),
we need to make sure we don't require a bootloader upgrade.  It's
easiest to have the bootloader scripts read random-seed into a
pre-determined address and size, then set those parameters once in the
devicetree.  On these legacy systems, the devicetree blob is appended
to the kernel image, so we can boot modern kernels on older hardware.

Newer embedded systems could read data from the hwrng as well and
provide it as a separate seed passed via the devicetree.

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

I have a proposal [2] to fix this problem (read: make it suck less).
As you have discovered, getting a *unique* random seed onto each CD-ROM
or other install medium is rather byzantine.  At best, it will be
difficult to maintain.

My idea is to leverage the fact that on boot up, the Installer OS
creates many TLS connections to the distros package servers.  Iff those
TLS connections were DHE or ECDHE, then there is an opportunity to
gather some randomness.

Basically, take the (EC)DHE shared secret, run it through an hkdf with
some data from /dev/urandom, and use the output to do a no-credit seed
of /dev/urandom.  The first connection or two will still have crappy
entropy, but after a few connections, the kernel entropy pools will be
in a significantly stronger state.

The difficulty is that it's impossible to quantify.  We don't know how
strong the peer's DHE random key is.  We hope it's strong, but shouldn't
assume a strength.

The shared secret is a) ephemeral, b) short lived, and c) known to only
two devices.  We could trust the peer, but it makes sense to mix in some
crappy data from /dev/urandom so that even the peer doesn't know the
output of the hkdf.  This assumes that the Installer OS was able to
gather a *little* bit of randomness during boot up.  Which isn't too
unreasonable.  A few interrupts, mac addresses, pci config spaces, etc
means there is at least greater than zero once TLS connections start
opening up.

The reason that I like this approach is that there are no changes to
make to the peers.  No changes to the TLS protocol.  The client just
needs a little extra code to accomplish the task.

Once the installer has done it's job, it can just read 512 bytes from
/dev/urandom into /var/lib/*/random-seed and another 512 bytes into
/boot/random-seed.

It should also be noted that this idea would be helpful on embedded
systems where the kernel typically takes 400 to 600 seconds before it
has 128 bits of entropy.  By that point, many TLS connections have been
created.

VMs would benefit as well from the non-deterministic stirring.

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

Here's a hitherto un-addressed problem.  Currently, system init scripts
read 512 bytes from /dev/urandom and write it to random-seed during
_startup_.  This is in case of a hard shutdown.  Iff there is a clean
shutdown, then the shutdown script reads 512 bytes from /dev/urandom and
writes it to random-seed.

Unfortunately, in the embedded world, clean shutdowns rarely happen.
And, as is well established, the entropy pool sucks at boot time.  This
means that the random-seed used at the next boot up was most likely
sampled at the worst possible time. :-(

It would be great, while taking into account flash wear, to have a
process doing a series of samples.  e.g. one per minute for the first 10
minutes, 1 per hour for the next ten hours, then exit cleanly.

This way, the quality of the random-seed used at each subsequent boot
has a much higher chance of being strong.

thx,

Jason.

[1] "Increase Early Randomness for Deployed Embedded Devices" proposal
submitted to the Linux Foundation's Core Infrastructure Initiative.
Status: On ice.  I owe them a response, but day job work has rapidly
overwhelmed me. :-/

[2] "Entropy Pool Stirring with Ephemeral Diffie-Hellman Key Exchanges"
proposal submitted to the Linux Foundation's Core Infrastructure
Initiative.  Status: On Ice.  Same as [1].
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161227/5cf94572/attachment.sig>