[Cryptography] randomness +- entropy

[Theodore Ts'o]

On Mon, Nov 11, 2013 at 02:38:52PM -0500, John Kelsey wrote:
> One thing to consider: RDRAND is probably fast enough that you could
> just request a new 128 bits of output and stir it into /dev/urandom
> or /dev/random whenever an output is requested.  So in principle,
> you could not account for RDRAND as having any entropy at all, but
> use it in this way, and the system would work just like it did
> without RDRAND, but with the difference that you would never again
> have a situation where /dev/urandom had 20 bits of entropy and was
> used to generate an RSA keypair.

We're doing this already.  See the call to arch_get_random_long()
(which abstracts RDRAND) in extract_buf() in drivers/char/random.c:

http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/tree/drivers/char/random.c?h=dev&id=392a546dc8368d1745f9891ef3f8f7c380de8650#n1025

We also use RDRAND to initialize the entropy pools, if it is available:

http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/tree/drivers/char/random.c?h=dev&id=392a546dc8368d1745f9891ef3f8f7c380de8650#n1236

So on modern x86 systems, using a reasonable recent kernel, we're in
pretty good shape.  My big concerns at the moment are on ARM and MIPS
platforms, which do not have RDRAND, and worse yet, which do not have
a fine-grained CPU counter, so get_cycles() doesn't work.  And using a
coarse grained timer, such as the jiffies lock, which typically has a
1ms or so resolution, is not going to produce quality entropy.  What
we have is good enough to avoid the embarassing "Mining your P's and
Q's" problem.  What I am not as sure about is whether we have enough
entropy to resist a determined attack by someone who is willing to
purchase specified popular handsets (i.e., the Samsung Galaxy S4, the
Nexus 4, etc.) and try to characterize the interrupt patterns for
specific hardware models, given the lack of a CPU cycle counter
register and the lack of a CPU-level HWRNG.

Regards,

						- Ted