[Cryptography] randomness +- entropy

[Theodore Ts'o]

Relying to a number of messages on this thread, not Dan's post in
particular.

For x86 desktops and laptops, I'm not that concerned about
/dev/urandom getting fully intiailized early enough.  Using Linux
v3.12 with the random.git changes that will be merged into mainline in
the next week or so, for the v3.13 release, running on my T430s latop:

...
[    4.446047] random: nonblocking pool is initialized
[    4.542119] usb 3-1.6: New USB device found, idVendor=04f2, idProduct=b2da
[    4.542124] usb 3-1.6: New USB device strings: Mfr=1, Product=2, SerialNumber=0
[    4.542128] usb 3-1.6: Product: Integrated Camera
[    4.542131] usb 3-1.6: Manufacturer: Chicony Electronics Co., Ltd.
[    4.575753] SELinux: initialized (dev tmpfs, type tmpfs), uses transition SIDs
[    4.653338] udevd[462]: starting version 175
...
[    6.253131] EXT4-fs (sdc3): re-mounted. Opts: (null)

So even without adding device attach times, and without fixing the
rc80211 minstrel initialization code, which is wasting two dozen bits
of entropy (it only needs non-cryptographic PRNG numbers for their
machine learning algorithm) --- both of which are on the todo list ---
the /dev/urandom pool is getting initialized with at least 128 bits of
(estimated) entropy almost two seconds *before* the root file system
is remouted read/write.

What I am more woried about is ARM and MIPS platforms, where we don't
have the high-resolution CPU cycle counter (I *am* working on pushing
on ARM CPU vendors such as Samsung and Qualcomm to try to get this
addressed for future products).

My current thinking about adding a boot-time blocking to /dev/urandom
reads for a maximum of N seconds (where N would be something like five
minutes by default).  If the timeout occurs without /dev/urandom
getting initialized with M bits (where M would probably be 128 bits by
default), then after N seconds, we would log a kern.crit message and
then let the /dev/urandom read succeed.  The idea behind this is that
if there is a system configuration issue such that /dev/urandom isn't
getting initialized, we don't want to completely break a user's
system, especially when previously with older kernels their boot
wouldn't have, perhaps inexplicably (especially in the case of a
cloud-hosted VM where ssh is the primary way sysadmins can get into
their virtual machine) hang during the middle of the boot sequence.

People who don't like the defaults will be able to specify overrides
on the boot command-line, so people who want /dev/urandom to block
forever in the absense of sufficient amounts of entropy can get that
behaviour --- it just won't be the default.  So, too, can people who
don't like the five minute hang will be able to configure their system
to not do this.  But hopefully, with a five minute delay plus the
kern.crit log message, system administrators and product engineers
will get nudged to do the right thing.  It was similar thinking which
has led me to introduce this printk for 3.13:

[    4.446047] random: nonblocking pool is initialized

also, if a process does try to read from /dev/urandom before it is
fully initialized, they will get a warning like this:

random: ssh-keygen: urandom read with 56 bits of entropy available

The main thing to remember here is that I don't get to dictate to
system administrators and software engineers at HTC, Samsung, Red Hat,
SuSE, etc., how they configure and patch their kernels, and how they
set up their boot-time init scripts.  Nor can I force application
programmers to change how they write their programs.  What I can do is
to try to "nudge" them to try to do the right thing, by making it be
obvious when they are reading from /dev/urandom too early, instead of
lazily generating ssh host keys as late as possible.

Cheers,

							- Ted

P.S.  Yes, there is a separte question about how accurate the entropy
estimation algorithms are, especially on ARM and MIPS platforms, which
haven't been as well studied as on x86.  But that's a separable
problem, and one which I hope to get some embedded engineers to work
on.  One of the things which I'm doing at the Korea Linux Forum this
week is to try to influence various Linux industry engineering groups
to be interested in tackling this problem, both by putting RFP
requirements on the CPU/SOC vendors, and by doing some studies about
how well entropy can be collected on mobile/embedded linux platforms.