[Cryptography] randomness +- entropy

John Kelsey crypto.jmk at gmail.com
Mon Nov 11 14:38:52 EST 2013


On Nov 10, 2013, at 9:27 AM, Theodore Ts'o <tytso at mit.edu> wrote:
...
> The main reason why most application programs tend not to want to use
> /dev/random is precisely because it will block --- but if you want
> hard randomness, and the system doesn't have any, what else can you
> do?

I can't think of many times when it's really appropriate to demand full entropy, rather than cryptographically secure bits.  It seems like having /dev/urandom be capable of *either* generating cryptographically secure bits *or* generating predictable bits forces application developers into either using /dev/random or crossing their fingers and using /dev/urandom.  And if lots of people are being security-conscious, they all have to use /dev/random, and it will block for a really long time.  

If you imagine a choice between:

a.  A secure cryptographic PRNG (say CTR_DRBG using AES256) which is catastrophically reseeded whenever it's convenient and the entropy pool is assessed at more than 256 bits.  (The pool is then reset to 0.)

b.  /dev/urandom and /dev/random as they are now.

I'm not clear on what situations there are where (b) provides better practical security than (a).  

> My suggestion would be to develop some tools that would help us give a
> "confidence score" for each entropy source that gets feed into an
> random number generator.  This may be a multi-dimensional score,
> though, since for some people, it might be enough to assume that the
> adversary can't monitor some kind of internal state (i.e., the network
> timing on your LAN), but for others, they don't want to make that
> assumption (after all, the NSA might have somehow figured out how to
> trojan your network switch, for sufficiently large values of tin foil)
> and so they want to the confidence score to be tied to physical
> quantuum or chaotic effects.  For yet others, they will be willing to
> trust that Intel, or some other hardware vendor, is honest in
> designing what they claimed, and for others, they aren't so sure.

Who will make use of this model?  I mean, it looks like a lot of real-world crypto developers now are using /dev/urandom (with crossing of fingers and rubbing of rabbits' feet) to generate their keys, rather than wait for /dev/random.  It's hard to imagine those guys trying to make use of a complicated multidimensional model of whom they want to trust and how much.  In practice, they're not even paying attention to your internal entropy estimates.  

> So the if we can't figure out how to award a "confidence score" to
> RDRAND, and some people are using rngd to feed fully credited entropy
> into /dev/random, how are you going award a objectively agreed upon
> "confidence score" to a system configuration which uses /dev/random
> and rngd to feed physical entropy from RDRAND?

This problem must come up with every entropy source, right?  If I can suspect the hardware RNG is hacked, I can also suspect the kernel or BIOS or drive firmware on which you're relying for entropy from drive access timings is hacked.

The nice thing about RDRAND is that if the hardware RNG isn't cooked, it can be used to initialize /dev/urandom and /dev/random to secure states before anyone needs any outputs from them.  (The only reason to suspect it could be cooked is, basically, because it would be really convenient for the bad guys if it were cooked.)  Since there's widely-used crypto code generating keys from /dev/urandom, closing the hole where /dev/urandom might not be securely initialized yet when the keys are generated seems like it's a couple orders of magnitude more important than addressing the possibility that RDRAND might also be cooked.  

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.  This would be annoying in the sense that /dev/random wouldn't get the speedup it should from having a fast hardware RNG on board, but it would represent a huge improvement in practical security.  

...

> Regards,
> 
>                    - Ted

--John


More information about the cryptography mailing list