Re: [PATCH] random: add regrand

[Jörn Engel]

On Sat, Nov 11, 2017 at 01:22:38PM -0500, Theodore Ts'o wrote:
> On Fri, Nov 10, 2017 at 04:23:21PM -0800, Jörn Engel wrote:
> > On Fri, Nov 10, 2017 at 06:52:12PM -0500, Theodore Ts'o wrote:
> > > Couple of quick comments.  The code as it exists is horrifically x86
> > > specific.  For example: it uses rdtsc().
> > 
> > Sorry, I should have changed that to "#if 0".  The rdtsc() exists only
> > as a means to estimate entropy and is not meant for production.
> 
> But that means you've only done estimates on x86 and are blindly
> extrapolating to all other architectures?

Correct.

I would claim that regrand and dakarand are near-identical twins.
Dakarand seems to have survived all attempts so far, which gives me a
bit more confidence.  Then again, it is questionable how many people
actually tried to attack dakarand on non-x86.

> > - add_interrupt_randomness() mostly depends on a high-resolution timer,
> >   and has to use jiffies on many architectures.
> 
> It samples from registers as well, at which point it's actually not
> that different from your proposed regrand.  The main difference
> ispurel that you are trying to do the bulk of sampling in very early
> boot, which means before we've started using any of the devices.  So
> regrand is purely dependent on there being separate oscillators in use
> between the CPU clock and the timer interrupt.  If there is a single
> master oscillator which is then downsampled to obtain the other
> "clocks" --- how well do you think regrand works in that environment?
> 
> At *least* with the current system, at least some of the interrupts
> will be from the off the SOC chip.  Such as the network interrupt, for
> example.

Regrand continues to collect entropy later on.  That is pretty important
for another reason: snapshot and restore of VMs.  In theory we could get
by with a well-seeded PRNG most of the time - except for boot and VM
restore.  We can detect boot, but we cannot detect VM restore.  So
sampling at some reasonable rate is the best we can do.

The reason I sample "enough" entropy at early boot is basically this:
https://factorable.net/weakkeys12.extended.pdf

If there is a way to mess up by reading from /dev/urandom, I would blame
the kernel and not the users.  If I have to delay bootup to initialize
the random pool, so be it.  The alternative, imo, is worse.

Now the only question is whether we can actually sample enough.  I have
demonstrated that I do when booting VMs on x86.  Not perfect, but a
starting point.

> > Your concern may still be right.  If it is, I think we have lost and
> > there is nothing we can do.
> 
> There is definitely more than we can do.  In particular, I dispute
> your counsel of hopeless over at a number of items you have rejected,
> but definitely this one:
> 
> > - Storing entropy across reboot requires a writeable filesystem and
> >   script support.
> 
> Funny thing; most systems have at least *some* amount of stateful
> store; they wouldn't be terribly useful computers if they didn't!

I have worked on systems that didn't.  Once you go to the cheap end of
embedded systems, you either have no writeable filesystem or a very
limited amount of flash.  Storing entropy at shutdown wouldn't work
because shutdown typically means yanking the power cord.  Storing
entropy every hour/day/whatever will quickly dominate the write load on
those systems and wear out your flash.

I also have limited faith in everyone working on those systems to get
the entropy save/restore script right.  Maybe 90% of them will, but
definitely not 100%.  "You cannot get it wrong" is much stronger than
"carefully read the documentation, write some code of your own and you
probably won't get it wrong".

> What I would do is to make it the responsibility of the bootloader, so
> we can get the entropy early enough that it can be used to seed the
> KASLR.  It may be that on different architectures we will have to
> store entropy in different places; I wouldn't put in the file system
> in most cases, if we can at all help it.  For example, on x86 systems,
> the best place to put it might be an explicit (but small) GPT
> partition if the GPT partitioning scheme is used, or immediately after
> the MBR and GRUB Stage 1.5 at offset 20 sectors from the beginning of
> the disk.

Some kind of bootloader is probably necessary for stackprotector.  You
have to somehow exclude a set of functions from stackprotector and use
only that set of functions to sample the initial entropy for your canary
value.  It would be nice if none of those functions would be reused
after stackprotector is turned on, which would imply something like a
bootloader.

I would prefer not using the regular bootloader, because there are just
too many of them and making sure every last one of them gets it right is
near hopeless.  But if the regular bootloader starts a mini-kernel that
only gathers entropy and then starts the regular kernel, that would be a
good design.

> We would have to do something different on ARM and MIPS systems, sure.
> But eventually we could definte that part of the standard Linux
> environment is a 512 byte random seed state which must be available to
> the boot loader, and passed to the Kernel much like the boot command
> line and initrd are passed to the kernel today.  There must also be a
> standard function which allows root to update the random seed.
> 
> For bonus points, the random seed state could be available for reading
> only during the boot session (for example, it will no longer be
> readable once UEFI boot services are terminated, for example), and
> after that point, the random seed state can only be updated by root
> (and perhaps the trusted hardware would hash the passed-in random seed
> state with the existing seed state).  This would optional and would
> require hardware support, but we already have custom SOC support for
> in-line crypto support, and in some cases, custom support to store
> crypto keys to keep them safe against state-level attackers (like the
> FBI, if you are Apple :-).  In any case, I'm fairly confident I could
> talk to at least one Android handset manufacturer and get them to at
> least consider such an implementation.  :-)

My goal is a bit more audacious.  I don't want a minimum of one system
to have good entropy, I want all systems to have that.  Which means I
cannot require hardware changes.

The existing requirements for Linux are pretty basic.  You need a 32bit
CPU, memory and (I think) interrupt support.  So the goal is to extract
enough entropy from just those basics.  If we cannot do that, we have to
admit that millions of Linux systems cannot have good entropy.

Regrand is the only thing I know that has a chance.  Naturally I cannot
prove that it would work on any system - including those I have never
seen.  We cannot prove the security of AES or SHA3 either.  But we can
try to break those systems and, given a long enough string of failures,
be reasonably confident that breaking those systems is at least pretty
hard.

> > My hope is that it is simply too hard to
> > have an accurate system clock and such tight synchronization between
> > interrupts and the CPU that we cannot extract entropy.
> 
> It's not a question of "accurate system clock" --- it's just a matter
> of hardware manufacturers following the KISS principle.  Especially on
> a system-on-a-chip design, why have two clocks when using one would
> do?  Especially when BOM costs are measured in millicents...

I would love to see an example and try it out.

Jörn

--
My second remark is that our intellectual powers are rather geared to
master static relations and that our powers to visualize processes
evolving in time are relatively poorly developed.
-- Edsger W. Dijkstra