[Cryptography-dev] Upon the Distinction Between the Entropy of the Various Cryptographically Secure (Or Not) Pseudo (Or Not) Random Number Generators - A Monograph

[Glyph]

At the risk of being redundant with lvh, I'll try to summarize as well.  Mostly I'm doing so because I'd very much like it if the learned participants in this discussion would correct any misconceptions I have; I have been trying to get my head around the _real_ properties of practical portable random number generation for a couple of months now, and I keep heading down blind alleys and understanding things incorrectly.  I think I've finally got it here, so this is a good opportunity to find out ;-).

Maybe some of these thoughts will even be useful in the documentation.

On Jan 20, 2014, at 2:11 PM, Jean-Paul Calderone <jean-paul at hybridcluster.com> wrote:

> Sorry, I think I was unclear here.  I don't care about the blocking vs non-blocking nature of urandom and random.  I used "/dev/random" to represent the idea of a higher-quality random source (as compared to /dev/urandom).

Assuming that by "blocking vs. non-blocking" what we are actually talking about is "slow vs. fast" (since /dev/random's documentation seems to imply that you can happily set it to O_NONBLOCK and it will give you EAGAIN as normal), the slowness versus the fastness of the source is intimately tied to the level of quality.

After all, if there were such a thing as an always-instantly-available high-quality random source, and a slow-so-you-might-have-to-wait high-quality random source, there's no reason I can imagine why you would prefer to use the slow one that might run out, if the other were instantly replenished.

My understanding at this point is that we can have such a thing; that a "real" CSPRNG (in the form of the Yarrow and Fortuna algorithms, with appropriate periodic re-seeding, which everyone seems to think is fine on the platforms where they're implemented) gives us such a thing in software, and RDRAND can do it in hardware.

On platforms using the yarrow and fortuna algortihms there does not appear to be a "pool" of entropy in the sense we're talking about here; as physical entropy becomes available, it is just used to further re-seed the algorithms immediately.  Certainly there's no pool whose exhaustion you can detect from user-land.

> I care about the idea that reading a lot of entropy from either device (again, it doesn't matter which) results in "draining the entropy pool".

When we were discussing this earlier, I assumed that Linux had implemented a similar CSPRNG, that it was seeded from the hardware entropy sources used to populate /dev/random, and that /dev/random itself must be something of a relic.

But, rather than rely on these solutions, it seems that Linux instead implemented some homegrown, weird PRNG for /dev/urandom; and, instead of assuming that the one-way hash functions in this PRNG are, you know, one-way, it still considers "real entropy" to be "used up" by seeding the urandom device and has it removed from the pool so it won't show up on /dev/random, as you suggest; making lots of reads from /dev/urandom can in rare cases cause /dev/random to block.

The only paper I could find, from Wikipedia, <http://www.pinkas.net/PAPERS/gpr06.pdf>, suggests that this PRNG has known weaknesses.  However, this paper was from 2006, and I know that the algorithm has been changed somewhat recently; I would like to believe that Linux has been modified to be more in line with the security community's consensus assessment of what constitutes a CSPRNG; but I can't find any indication of that.

> It sounds like some responders think that "draining the entropy pool" isn't a real thing that can happen and should be ignored.

I was hoping that the conclusion of my investigation would be that one can ignore the distinction between /dev/random and /dev/urandom (or equivalent) entirely on all platforms; instead, I appear to have discovered that it's probably still unwise to use /dev/urandom on Linux for any persistent key materials.

However, there appears to be consensus that the data from /dev/urandom is suitably random for seeding the CSPRNG in OpenSSL.

Going back to the original issue we were originally discussing though, the practical down-side of this particular change to Cryptography is that, on a server (A) being used under heavy load in production, (B) where every request consumes more entropy than it produces, (C) which does not have RDRAND or any other hardware entropy source and (D) running linux, it will be slow to generate persistent key materials because those should be generated from /dev/random and that device may block when its pool is exhausted.

This only applies to persistent-key-material generators, because any application using /dev/urandom already needs to be prepared for it to be at this hard-to-qualify slightly-lower-than-random level of randomness anyway, so it isn't a problem if that pool isn't being reseeded as quickly as it should be, and it's apparently "random enough" for almost any other application.

The operator of such a system has many possible avenues of attack, without disabling this feature of Cryptography:

Stop generating persistent key materials at such a rate on a production server, maybe do that somewhere else, like, once, in advance, seriously, why the heck would you do this
Switch to FreeBSD
Switch to OS X
Buy an external hardware random number generator
Upgrade to hardware that has RDRAND

Given the peculiar obscurity of this use-case and also the multiple avenues open to the operator, it seems reasonable to me to proceed with the change.

>   Fine, that's a coherent response.  It's somewhat in contrast with (well, directly contradicts) the /dev/urandom man page for Linux but I can accept that the people who wrote that may have been mistaken. :)  If that's really what people are saying here?

I am trusting them to make accurate statements about their own implementation - entropy pool depletion is in fact a real thing that happens sometimes on Linux.  However, it appears to be something of a bug, and I'm a bit confused as why they are intent on keeping this feature when it has pretty much disappeared or never existed on other platforms, for many, many years.

Plus, perhaps more importantly, entropy pool deletion is purely a performance concern.  Correctly-written code will select the appropriate source of randomness, and /dev/urandom is apparently good enough for almost everything but long-lived secret key generation.  Which means that the only thing that might happen if you deplete the pool is that something demanding a high degree of randomness might have to wait for a little while; and even this performance concern is only an issue in configurations where there is no further readily-available source of entropy to replenish the pool; such sources can be reasonably easily acquired if an application requires it.

> Also, this makes me curious - which device did the people on this list use to generate their private GPG/SSH/SSL/etc keys?  /dev/random or /dev/urandom?

After this little survey of the literature, I'm going to declare this question to be poorly phrased and say that I generated it with securityd and Yarrow, since apparently the name of the device is meaningless ;-).

-glyph

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/cryptography-dev/attachments/20140120/8263f91e/attachment-0001.html>