[mikeash]

The problem is that /dev/random is too paranoid. It refuses to work if there isn't enough entropy in the pool, yes. But when it produces numbers, it subtracts that amount from the supposed amount of entropy in the pool. Thus it will refuse to work again pretty soon in a lot of circumstances where it's still completely safe to proceed.

For a concrete example, you start out with zero bits in the pool. /dev/urandom will produce a predictable stream of bits. This is extremely bad. /dev/random will block. this is good.

Now you add 1024 bits to the pool. Both /dev/random and /dev/urandom will produce good numbers.

Now let's say you read 1024 bits from /dev/random. This will reduce the entropy counter back to zero. If you then try to read another 1024 bits from /dev/random, it will block.

But this is nonsense! Those 1024 bits you added before aren't depleted just because you pulled 1024 from /dev/random! It is perfectly safe to proceed generating more numbers at this point (or at least it's as safe as it was before), but /dev/random refuses to.

Many systems don't add entropy to the pool very quickly so it's entirely possible to "deplete" it in this way. Then your code using /dev/random wedges and you have a problem. However, few systems are ever in a state where they have zero entropy. Thus the advice to use /dev/urandom.

Ideally, you'd want a device which blocks if and only if the entropy pool hasn't been properly seeded yet, but which never blocks again after that point. Apparently this is what the BSDs do, but Linux doesn't have one.

[zackelan]

> Now you add 1024 bits to the pool.

A further complication - you don't actually add 1024 bits to the pool. Instead, you add N bits to the pool (N > 1024), estimate its entropy as 1024, and increase the overall entropy estimate by that much.

Estimates are always pessimistic, because it's better to be cautious and under-estimate the entropy than the alternative. So you might have 2048 bits or more of real entropy, but that can still be "depleted" by a request for 1024 bits.

The paper that describes Fortuna [0] goes into greater detail on this. Yarrow, the CSPRNG that preceded Fortuna, attempted entropy estimation. Fortuna rejects entropy estimation, and tries to build a CSPRNG that is secure without needing estimates:

"...making any kind of estimate of the amount of entropy is extremely difficult, if not impossible. It depends heavily on how much the attacker knows or can know, but that information is not available to the developers during the design phase. This is Yarrow’s main problem. It tries to measure the entropy of a source using an entropy estimator, and such an estimator is impossible to get right for all situations."

"Fortuna solves the problem of having to define entropy estimators by getting rid of them."

0: https://www.schneier.com/fortuna.pdf

[zeveb]

> Fortuna rejects entropy estimation, and tries to build a CSPRNG that is secure without needing estimates

What really annoys me is that a Fortuna-based CSPRNG was contributed to Linux eleven years ago this month, but died on the vine, IIRC because the Linux kernel team were so fond of the entropy-estimation approach.

[tveita]

> Ideally, you'd want a device which blocks if and only if the entropy pool hasn't been properly seeded yet, but which never blocks again after that point. Apparently this is what the BSDs do, but Linux doesn't have one.

The getrandom() call added in Linux 3.17 does this. By default it reads from urandom, but it blocks until it estimates that urandom has been seeded with "a sufficient number of bits", which seems to be around 128 bits of randomness.

http://man7.org/linux/man-pages/man2/getrandom.2.html

When available getrandom() should probably be preferred over both /dev/random and /dev/urandom.

[lsh123]

"But this is nonsense! Those 1024 bits you added before aren't depleted just because you pulled 1024 from /dev/random!"

An observer of the produced random numbers can potentially deduce the next numbers from the first 1024 random numbers. This is the reason why /dev/random requires more randomness added -- to prevent the guessing of the next number.

[tptacek]

No, they can't. That's not how crypto DRBGs work. If you could do that, you'd have demonstrated a flaw in the entire /dev/random apparatus, not a reason not to use urandom.

Think of a CSPRNG almost exactly the way you would a stream cipher --- that's more or less all a CSPRNG is. Imagine you'd intercepted the ciphertext of a stream cipher and that you knew the first 1024 plaintext bytes, because of a file header or because it contained a message you sent, or something like that. Could you XOR out the known plaintext, recover the first 1024 bytes of keystream, and use it to predict the next 1024 bytes of keystream? If so, you'd have demolished the whole stream cipher. Proceed immediately to your nearest crypto conference; you'll be famous.

Modern CSPRNGs, and Linux's, work on the same principle. They use the same mechanisms as a stream cipher (you can even turn a DRBG into a stream cipher). The only real difference is that you select keys for a stream cipher, and you use a feed of entropy as the key/rekey for a CSPRNG.

It's facts like this that make the Linux man page so maddening, with its weird reference to attacks "not in the unclassified literature".

[mikeash]

In theory yes. In practice you're talking about a massive cryptographic break, to the extent that it's not worth worrying about if you're going to be using those random numbers for anything that involves real-world cryptography. If you can't trust your CSPRNG to be secure when your attacker gets ahold of 1024 bits of output then you can't trust anything you're going to do with the output of your random number generator anyway.

[rsy96]

> An observer of the produced random numbers can potentially deduce the next numbers from the first 1024 random numbers.

By definition, a cryptographically secure pseudorandom number generator cannot be predicted like that by a computationally bounded attacker.

Thus if any attacker could deduce the next number from /dev/random by observing the numbers before, the algorithms they adopt is fundamentally wrong, and nothing could the save the security in that case.

[Tomte]

http://www.2uo.de/myths-about-urandom/#computationally-secur... together with http://www.2uo.de/myths-about-urandom/#low-entropy refutes that point.

(That's why I've chosen this structure for the essay, and have included anchors)

[cxseven]

It should be roughly as hard as cracking a hash of 1024 bits, i.e. very hard.