Hacker News Reader

Comment by tptacek | Hacker News Reader

This presentation makes very little sense to me.

It appears to revolve around the idea that Linux servers "produce" entropy at an unexpectedly low rate over time, and "consume" entropy quickly.

But that's not how CSPRNGs work. A CSPRNG is a stream cipher, keyed by whatever entropy is available to seed it at boot, and, for purposes of forward secrecy, periodically (or continually) rekeyed by more entropy.

Just as for all intents and purposes AES-CTR never "runs out" of AES key, a CSPRNG doesn't "run out of" or "deplete" entropy. The entire job of a CSPRNG, like that of a stream cipher, is to take a very small key and stretch it out into a gigantic keystream. That's a very solved problem in cryptography.

I am automatically wary of anyone who discusses "entropy depletion", even moreso when they appear to be selling "entropy generators".

View on HN

So you're saying that Linux's /dev/random should go away, /dev/urandom or getrandom is always what you want as long as the system has collected enough entropy (even for key material), and Linux could stop "collecting entropy" once it has enough to seed the CSPRNG?

Correct. If the entropy is say 256 bits, then the attacker has to try 2^256 combinations. It's quite like encryption; you can encrypt a 1 TB file with a 256 bit key. (And indeed some stream ciphers like RC4 are just a PRNG xored with plaintext).

AES-CTR keystream is also a CSPRNG xor'd with plaintext and is a better example because it's the recommended encryption mode (AES-GCM is AES-CTR + GMAC and is what everyone recommends).

Pedantic: there are better modes to use than GCM, for a couple reasons. GCM is the most performant widely available AEAD though.

> there are better modes to use than GCM, for a couple reasons.

What are the better modes, and the reasons?

The authentication mode for GCM is sort of fragile. While nonce reuse is always bad, it's particularly disastrous in GCM in that it immediately leaks the authentication key. Similarly, using GCM with a truncated authentication tag makes forgery easier than you'd expect and again leaks the authentication key in the process.

GCM is also difficult to implement in software for the same reasons AES is: the high-performance implementation strategies tend to rely on precomputed tables. This puts memory pressure on servers that handle a large number of keys concurrently. Table-based implementations also tend to expose cache-timing side channels. Fortunately, modern Intel machines have instructions (e.g. PCLMULQDQ) that aid implementations, though I'm not sure how widespread their use is in practice.

To be very clear, GCM is still a fine choice, and much safer than composing authentication and encryption yourself.

If you have access to it, NaCl's Secret Box is a good choice that avoids these problems. Libsodium implements NaCl and is pretty widely available, I think. OCB is also a good choice, though I haven't seen many implementations of this.

EDIT: For those interested, Niels Ferguson's criticism of GCM (http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comment...) is a great read. Lots of minor practical issues (e.g. specifying bit strings rather than byte strings, performance measurement across platforms, etc.) along with the aforementioned attack on short authentication tags.

Yes.

Any useful citations that could be used if one wanted to submit a patch doing exactly that and have it taken seriously? Something that would spell out exactly why it makes sense to rip out the entire runtime entropy estimator mechanism beyond making sure there's enough entropy to begin with?

I believe any such patch is doomed; the Linux randomness maintainer appears to be thoroughly convinced of the utility of /dev/random, which is unfortunate.

Many people have tried pointing out this design flaw to him.

That's exactly what I had in mind when I was asking for any specific citations you might have that address this. Random patch versus self-appointed "expert" won't go nearly as well as supporting evidence versus lack of supporting evidence.

I have a little bit of hope due to this quote from the getrandom(2) manpage: "Unless you are doing long-term key generation (and perhaps not even then), you probably shouldn't be using GRND_RANDOM. The cryptographic algorithms used for /dev/urandom are quite conservative, and so should be sufficient for all purposes." The parenthetical and the second sentence give me some hope.

(Related question: is Linux using the most sensible CSPRNG it could be using?)

But even if that doesn't work, I can see a few ways around that. Most notably, /dev/random and its associated ongoing accounting could become optional. (This is already something I'd like to do for size reasons.) Then, for compatibility, random could be a symlink to urandom.

And yeah, between that and the ongoing battle against the Great Evils of hardware random number generators, the potential of Linux's randomness mechanism seems rather maintainer-limited.

Making /dev/random blocking optional doesn't help; in fact, it probably hurts, because it allows more Linux code to "safely" use /dev/random, and that code is dangerous on platforms where /dev/random does the old Linux thing.

I'm not saying /dev/random's blocking would be optional; I'm saying the driver backing /dev/random would be entirely optional. Making it a link to urandom rather than having it entirely missing just avoids breaking old (misguided) userspace that still uses it; breaking userspace would make the proposal less likely to be accepted. Convincing various userspace components to switch to urandom, and for that matter fixing the documentation to stop recommending /dev/random, is a separate battle.

Perhaps you can clear something up: my understanding is that linux /dev/urandom will drain the entropy pool first and then use a CSPRNG when it is empty.

This is what I was told back in the 2.6 days, and it always seemed to me that you would want to stretch your entropy out more.

That has never been true, but it is for reasons passing understanding a very popular urban legend.

/dev/random and /dev/urandom use the same CSPRNG code. There are only two differences: there are separate state pools for them, and /dev/random includes logic to block on requests that exceed an estimator number.

And to make it even more clear: the notion that /dev/urandom first does "the right thing" and then (after entropy has been exhausted) falls back on the "worthless thing" (the CSPRNG) is absolutely and categorically wrong.

Both /dev/urandom and /dev/random always do "the worthless thing".

What people consider "the right thing", namely handing out raw collected random bits without any postprocessing, would even be catastrophic.

Reply on news.ycombinator.com