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

[John Denker]

On 12/27/2016 10:08 AM, Theodore Ts'o wrote:

> [...] 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.).

I have a suggestion that is architecture-independent and far simpler
than many of the other things that have been proposed.

The kernel image is already a fancy thing with internal structural
blocks.  So let's add another block, 512 bytes long, reserved for
a random seed.  Any platform that can read the image at all will
automatically bring the seed along.  The seed is available to the
RNG from time t=0 onwards.

To refresh the seed, read the System.map to see where it sits.  Or
add a pointer, at some fixed offset early in the file, pointing
to the seed.  (A few similar things already exist.)

The seed is excluded from the bzImage checksum computation.  It is
also excluded from the compression/decompression.

It will take some expertise to implement this, but even so, this
has a lot fewer moving parts than other schemes that have been
proposed.  It is more localized, with fewer dependencies and fewer
interfaces.  It does not require grub, or UEFI, or x86, or ARM,
or anything else beyond a BIOS that can read the boot image in
the usual way.

As a related benefit, the vmlinuz file is accessible at the top
level of a ISO-9660 image, without any additional layers of
compression or obfuscation, making it easy to refresh.

> people have been wringing their hands

Yes.  For years.  Building the seed into the boot image will
put a stop to that, once and for all.

Given proper care and feeding of the seed, this upholds the
principle that the RNG must never block and must always return
good randomly-distributed results.

This is an industrial-strength solution to a serious problem.

> an appropriately suspicious user can still easily run
> a crypto checksum on the entire ISO-9660 file system image. 

I completely agree with the goal:  We want to encourage users
to be meticulous in general, and about checksums in particular.
However, when I do the analysis, I come to a slightly different
conclusion about how best to promote that goal.

AFAICT the simplest approach is to follow the sequence:
  a) Download the ISO image to hard disk.
  b) Verify the checksum.
  c) Refresh the seed.
     If the old (downloaded) value is nonzero, save it somewhere.
  d) Burn to CDrom (if that's what you want)

Verifying before reseeding solves the problem with zero additional
time or effort.

On rare occasions, if somebody wants to verify the checksum ex
postfacto, they can restore the seed to its as-downloaded value
and then compute the checksum in the usual way.

This applies to a seed stored anywhere within the ISO filesystem,
whether in its own file or tucked inside the kernel image.

  In contrast, sticking the seed outside the ISO-9660 filesystem
  is not super-terrible, but it has no real advantages.  The user
  cannot checksum the entire file containing the combination,
  but instead needs a tool that will delve into the ISO-9660
  structure to find its size, and checksum only that much.  The
  required tool is no simpler than the one that finds the seed
  file and updates it in place.

  What's worse, the bits appended to the end will need some kind
  of structure.  (An unstructured pile of bits is not the sort of
  thing we ought to encourage.)  Suppose some day we want to append
  /two/ things.  Which is which?  How big are they?  Very soon this
  turns into a way of /partitioning/ the medium, with an ISO-9660
  partition followed by something else.  If we're going to do that,
  we ought to do it right.

Using files /within/ the ISO system is simple, structured, standardized,
guaranteed to work, and easy to document.