[Cryptography] RNG design principles

[Theodore Ts'o]

On Sat, Nov 26, 2016 at 11:20:24AM -0700, John Denker wrote:
> Thanks!  That sounds like a big step in the right direction.
> This is really important, because it is one of precious few
> ways of getting randomness into the system /early enough/.
> 
> There remain a couple of points where it might be nice to get
> some clarification:
> 
> What happens if there is /not/ some on-chip RNG peripheral, or
> not one that the firmware knows about?

One approach which might work is if you have some way of storing a
static secret --- for example, UEFI has a way you can store a UEFI
variable where access is removed after boot services are teriminated
--- and a reliable realtime clock, or some kind of guaranteed
monotonically increasing counter.

If you had that, then you could encrypt the clock or the timer by the
secret key in early boot, before the Linux kernel has terminated the
UEFI boot services, and use that to seed the CSPRNG.  This could be
done before KASLR kicks in, and once the early boot services are
terminated, even if ring 0 protections get violated, you won't be able
to get access to the secret key.

The secret key could be regenerated each time the system is installed
or the kernel gets upgraded --- the UEFI variables are typically
stored in NOR flash or some other non-volatile storage that doesn't
allow for a large number of write cycles.  That's why we can't store
the counter using a pre-boot UEFI variable.  But it should be good
enough that we can regenerate the key each time the kernel gets
installed, even if there is a security upgrade every month, ala the
Android security release model.

This doesn't completely solve the "out of the box problem", of course
--- but past a certain point, you really do want an on-chip RNG
peripheral, and fortunately, most x86 systems will have a TPM chip.
The trick is what to do with those ARM systems, and there we're at the
mercy of the SOC manufacturers.

>   1) There are situations where it would be a big win to have
>    grub pass a seed, taken from the grub configuration file,
>    updated between one boot and the next via:
> 	grub-editenv /boot/grub/grubenv set randomseed=0:yBwrcLYCLept2GTvVyRQmnGikarfOmZ3
> 
>   2) There are situations where the best option is to literally
>    roll the dice and feed a seed to grub by hand.
>     2a) Passing it on the kernel command line is one option,
>      which has some charm because grub already fully understands
>      the command line.

The kernel command line is available at /proc/cmdline, so it becomes
visible.  Also, /boot/grub/grub.cfg is also normally a publically
readable file (although that could be fixed).

>     2b) Passing it via the EFI configuration table is also fine
>      but might require changes to grub.  Note that changing grub
>      may be easier than changing the kernel, so as soon as we get
>      a kernel that knows what to do with the configuration table,
>      this option (2b) might be the way to go.
> 	https://www.gnu.org/software/grub/manual/grub.html#Command_002dline-and-menu-entry-commands

Since you have to change the kernel to prevent /proc/cmdline form
leaking the key, you might as well pass it as a binary extension to
the boot-time protocol, which is how the boot loader passes the
command line and initrd information to the kernel.  For an example of
the x86 boot command loader, please see:

	https://www.kernel.org/doc/Documentation/x86/boot.txt

This is something that I've thought about quite a lot, but I haven't
had time to really try and execute on it.  The bottom line is that the
step requires changes in a multiple components --- in the kernel, the
boot loaders, the distribution installers, etc. etc.  The kernel piece
isn't too hard (at least for me).  Making changes to grub, the distro
bootloaders, etc. --- that's what makes this problem more complicated.

Cheers,

					- Ted