[Cryptography] randomness +- entropy

[John Denker]

I have a /constructive/ suggestion, followed by a /specific/
constructive suggestion.  But first, some background:

On 11/05/2013 08:18 PM, Theodore Ts'o wrote:

> I'm not against providing a programtic way for programs to determine
> whether /dev/urandom has been initialized, or even blocking until it's
> been initialized.  I just disbelieve that the critical applications
> will use such an interface. 

Exactly.

We have seen that even the /unfounded/ rumor that the PRNG
might block causes users to shun the PRNG, substituting
something that is no better and almost certainly worse.
If the rumor were true, the user behavior would be even
worse.

On 11/05/2013 04:09 PM, Theodore Ts'o wrote:

> I could add an ioctl which returns the state of the pool initialized
> flag, or which blocked until the pool is considered initialized, but
> I'm not convinced that enough programs would really use it.  And if I
> made /dev/urandom reads block until the pool was initialized, I
> suspect that product managers would just tell the engineers to patch
> out the check, as opposed to doing something intelligent,

Exactly.

Here's a suggestion:

--> Make sure the kernel PRNG is initialized very, very early.
 *) Then the question of whether or not to block does not arise.
 *) Then the users have no temptation to evade the block.

In more detail:  What we have now is an insidious failure, i.e. a 
PRNG that sometimes provides an insufficiently-random distribution
of bits.  This is a problem.  This is a Bad Thing.  The main goal 
should be to fix the problem ... and to fix it such a way that it 
/stays/ fixed.

Some applications cannot afford to wait.  For these applications,
if the PRNG blocks, we have converted an insidious failure into
a manifest failure.  It could be argued that this is a step in
the right direction ... but it is only a /small/ step, and it
does not really fix the problem.  It could be argued in political
terms that this would make users so angry that they would demand a 
real fix, but creating demand for a fix without actually providing
a fix is bad politics, bad marketing, and bad engineering.

So this brings us back to the main point:  The main goal should 
be to implement a PRNG that is up and running very, very early.
In engineering-management terms:  this is in the critical path.

  By way of contrast, blocking is not in the critical path,
  because even if you implement blocking, you *still* need
  to fix the problem.

====

Here is a specific suggestion for how the problem could be 
fixed.

--> Incorporate the stored seed into the kernel boot image 
 (zImage or bzImage).  That ensures that the PRNG is "born" 
 ready to go, just as a newborn dolphin knows how to swim, 
 and a newly-hatched rattlesnake is already venomous.

I have looked into this a little bit.  Although I don't 
yet understand all the details, it looks like there is a
straightforward path.

Actually there are two complementary requirements:
 -- the stored seed must be available very, very early
 -- it should not be unduly difficult to refresh the
  stored seed from time to time.

Refer to the following for a simplified view of the structure
of the boot image:
  http://en.wikipedia.org/wiki/Vmlinux
  http://www.faqs.org/docs/kernel_2_4/lki-1.html

Actually things are somewhat more complicated than item
12 in the faqs.org document suggests.  The actual lines
from the relevant x86 Makefile include:

VMLINUX_OBJS = $(obj)/vmlinux.lds $(obj)/head_$(BITS).o $(obj)/misc.o \
        $(obj)/string.o $(obj)/cmdline.o $(obj)/early_serial_console.o \
        $(obj)/piggy.o
...
$(obj)/vmlinux: $(VMLINUX_OBJS) FORCE
        $(call if_changed,ld)

(and even that is a simplification).  Unless I am missing
something, it should be No Big Deal to add $(obj)/urandom-seed.o
to the list, somewhere ahead of $(obj)/piggy.o.

Next step:  It should be straightforward to write a tool
that efficiently updates the stored seed within the boot
image.  Updating MUST occur during provisioning, before
the device gets booted for the first time ... and also
from time to time thereafter.  Updating the boot image
isn't be quite as simple as 
  dd of=/var/lib/urandom/random-seed
but neither is it rocket surgery.  The cost is utterly
negligible compared to the cost of a security breach, 
which is the relevant comparison.

I have considered a *lot* of alternatives.  This is the
one that gives the most bang for the buck.

If we do this, many of the issues that we have recently
been discussing just melt and disappear.

========================

Sometimes the system is booted from read-only media.
This must be handled as a special case.  In the case
of a "live CD" or "install CD" I recommend passing a
seed via the kernel boot cmdline.  We could teach
grub to demand a key from the user.

  If the machine is air-gapped and will not have
  any persistent consequences, then this step can
  be skipped.

Suppose we have something that boots from read-only media 
-- booting repeatedly, unattended, with no HRNG, with no 
hypervisor, with no non-volatile memory, and yet no air-gap.  
This must be declared an unsound design.  Get a clue.  Get 
some persistent memory, get a HRNG, get the hypervisor to 
provide a seed, or whatever, so as to ensure that the PRNG 
is up and running very, very early.