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

[Theodore Ts'o]

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

Technically, it's /var/lib/systemd/random-seed for systems using
systemd, and /var/lib/urandom/random-seed for older systems.  I think
you were generalizing based on a small sample set.

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

This is only good enough if you only care about user-space
applications that start up after the system is fully initialized.
It's not good enough for people who are worried about KASLR
(Kernel-level Address Space Layout Randomization), which happens in
very early boot, before the root file system or initrd is
mounted/loaded.  There are kernel people who are looking at this,
though, and the solutions tend to require architecture-specific
solutions (e.g., involving the bootloader, or trying to leverage the
UEFI BIOS, or device tree on embedded ARM systems, etc.).

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

Certainly during the installation process there is a lot of I/O, and
if you believe that this will result in uncertainty that won't be
known by an external attacker that can be harvested while copying
files from the CD and the network onto the disk drive or SSD, that may
be good enough in most cases.

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

This is *not* true.  Certianly not for debian, where the Debian
installer and Debian Live CD are two different things.  You can
install using the Debian Live CD, but there is also the Debian
Installer image which is faster and more flexible in terms of
installation options compared to the Devian Live CD.

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

If you are dependant on an installation image which you are
downloading from some central source, you might as well trust it to
generate a random key which can be appended to the end of the
top-level ISO-9660 file system for you.  And the reason why I suggest
appending it onto the *end* of the top-level ISO-9660 file system is
because that way an appropriately suspicious user can still easily run
a crypto checksum on the entire ISO-9660 file system image.  The .iso
file might contain an extra bit of random key that can be used to
encrypt a combination of the RTC plus the MAC address of the system to
be installed, so the program which calculates the crypto checksum
would have to understand the difference between the ISO-9660 file
system image versus the the .iso file, but that's achievable.

The rest is all engineering details.

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

Nah, just have the installer script look to see if there is a random
key at the end of the ISO-9660 file system, and if so, use it plus the
time from the RTC plus the MAC address(es) to create a random-seed
file file in the appropriate place.

> <*> Background, Motivation, and Philosophy <*>
> 
> Here are some more principles that all-too-often get left off
> the lists people make:
> 
>  *) 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.


In practice, getrandom(2) is fully initialized before the root file
system is mounted.  For example, on my laptop:

Dec 19 14:46:34 callcc kernel: [    0.000000] Linux version 4.9.0-00090-g3a45c5c (tytso at tytso-ssd) (gcc version 4.9.2 (Debian 4.9.2-10) ) #5 SMP Tue Dec 13 04:59:15 UTC 2016
Dec 19 14:46:34 callcc kernel: [    2.563665] random: fast init done
Dec 19 14:46:34 callcc kernel: [   12.693192] random: crng init done
Dec 19 14:46:34 callcc kernel: [   13.039601] EXT4-fs (dm-1): mounted filesystem with ordered data mode. Opts: (null)

OK, so this is a little unfair since my root file system uses LVM on
top of dm-crypt, so I had to type my passphrase before the root file
system could be checked, let alone mounted.  But in that scenario, in
practice getrandom(2) *never* blocks for normal userspace programs.

So as a more fair demonstration, let's use a KVM system (which has
even less entropy available to be collected than a physical laptop):

[    0.000000] Linux version 4.10.0-rc1-12302-g7ce7d89f4883 (tytso at callcc) (gcc version 5.4.1 20161202 (Debian 5.4.1-4) ) #115 SMP Mon Dec 26 09:54:17 EST 2016
[    4.363243] random: fast init done
[    4.366114] random: crng init done
[    5.073506] EXT4-fs (vda): mounted filesystem with ordered data mode. Opts: (null)

So in practice, non-boot-time callers of getrandom(2) can and should
assume that it will never block.  If it does block, it means something
has gone terribly wrong.  During boot-time, some care may be needed,
on some classes of hardware.  But to the extent that your analysis
assumes that the random number generator will be initialized from the
random-seed file during the boot sequence, that assumes the root file
system is mounted and before that point, the random state can't be
guaranteed.  So even in your design, you are assuming that some care
needs to be taken for programs running during the boot sequence, some
of which may be happening before, or in parallel with, the root file
system being mounted, and the random-seed file being used to
initialized the random pool.

The design goal of for /dev/urandom and getrandom is to make sure that
by the time the boot sequence is complete, in practice both will be
fully initialized, and for the most common VM and PC class hardware,
that they be initialized before the root file system is mounted.

This doesn't completely solve the problem for KASLR, but for the class
of problems most people have been wringing their hands over, it does
take care of most of the cryptographic concerns that people might
have.

The only reason why getrandom(2) blocks is as belt and suspenders for
those people who are concerned about what happens in the case when
/dev/urandom is not fully initialized by the time the boot sequence is
over.  (And for insane designs that generate long-term public keys
during the boot sequence, of course.  Ssh init scripts as commonly
deployed on many systems, I'm looking at *you*.)  But on most systems,
we try to make sure we can grab enough uncertainty that won't be known
by an external attacker so that we are reasonably proof against these
sorts of attacks by the time the root file system is mounted.

> 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 certainly agree with this.

Cheers,

							- Ted