How does generating random numbers "remove entropy from your system"?

Question

In a previous question, I quoted the --gen-random entry in the GPG Man Pages. At the end it says:

PLEASE, don’t use this command unless you know what you are doing; it may remove precious entropy from the system!

How does that work? I understand entropy to be the "randomness" of a system (i.e. the amount of information it contains). How can generating random numbers steal randomness from your computer such that it noticeably hurts the computer's ability to perform cryptologic operations in the future?

I'm no mathematician, so plain english answers would be appreciated.

Answer 1

As others have stated, the problem is the entropy pool. The operating system maintains a count of entropy in the pool that it decreases every time random numbers are generated from it and increases when it adds some timing or other information that is assumed to have entropy.

Requesting numbers does not actually remove randomness from the pool in practice, unless it is severely broken. The state will still be unknown and the numbers received cannot be used to derive future numbers.

However, the /dev/random interface on Linux blocks if the count is zero. This means that requesting a lot of random numbers from the OS may starve any programs that use the blocking interface. This is the practical issue with using the command, since especially on server machines that have no input devices the entropy count can be slow to increase.

The usual advice is to use the non-blocking pool in most applications so that they cannot get starved, but not every program out there does that.

Answer 2

Others have described the difficulty in harvesting entropy, and how little entropy there really is available inside a computer, so I won't cover that.

What you might want to be aware of is the existence of a sponge function. A sponge is a way of soaking up just a few bits of random entropy from a limited source, then squeezing out many "pseudo-random" bits by using a generating function. This sponge function feeds the original random bits into an encryption or hash algorithm, then recycles some of its pseudo-random output back into the generator, and this loop is repeated no more than a specified number of times. The output is a stream of bits that functionally exhibit most of the properties of randomness. However, because they are related by the initial state of the entropy pool used when they were generated, they're considered pseudo-random bits, and not truly random bits.

NIST has published a guideline, NIST SP 800-90Ar1 on various ways to securely generate random numbers using this method. The document also includes a table that shows how many random bits you can safely generate given a limited amount of entropy as input. (NIST refers to the sponge function as a "derivation function", and lists a few different candidate algorithms they support.)

Moving to a real world example, Microsoft provides cryptographically secure pseudo random numbers via the CryptGenRandom() API. The way Microsoft implemented it originally was very weak, but starting with Windows Vista, they replaced the implementation with one of the NIST algorithms above. They draw something like* 256 bits from the entropy pool to generate 128kb random bits, then after those 128kb have been delivered to the callers they draw another 256 bits from the entropy pool and repeat. Once the entropy pool is exhausted of random bits, though, the CryptGenRandom() API blocks until the entropy pool has been refilled; this is why requesting millions of random bits in a steady stream can cause performance issues with servers. Servers require cryptographically secure pseudo random numbers to establish TLS connections with their clients, and if the pool is empty, the servers will hang until the pool is refreshed.

* I apologize as this part is from my memory of a presentation, and I'm having a hard time locating the original Microsoft document that describes the actual sizes, quantities, and limits.

Answer 3

I'm going to attempt to summarize everything I learned about this subject, thanks to the information and references provided by previous answers, as well as the research they spawned.

Ultimately, the logic behind the warning is twofold (and mostly specific to Linux -- see "Another NOTE" below):

1. The main crux of the issue stems from the way the Linux operating system in particular implements it's /dev/random pseudorandom number generator (PNG) as a "blocking device". A "blocking device" means it will not give you any output if the entropy pool is depleted, which can be a serious problem if your system is relying on output from that device (see below for explanation of Linux entropy pool). Your server could lock up and stop replying to page requests until the pool is replenished, which could be a very long time on "headless", diskless systems (like servers) because they have very few external sources of entropy.

2. The second issue is that this function pulls directly from /dev/random, and it is implemented in such a way that it draws a significant amount of entropy, particularly when set to use the quality level of 2. An email cited in a previous question implies that using a quality level of 2 draws 19x more bits of entropy than commanded from /dev/random. Therefore, it can cause your system to deplete its entropy pool very quickly, causing /dev/random to block, and causing /dev/urandom to output not-so-random numbers.

So, ignoring this warning can be like doing a DoS attack on yourself.

The Linux Entropy Pool and /dev/(u)random:

(For another great explanation on this subject, read this)

In Linux, you have two cryptographically-secure PNGs: /dev/random and /dev/urandom. Both of them draw from the "entropy pool", which gets "filled" by things considered random for all intents and purposes: system events, mouse clicks, device drivers, and other environmental noise. The pool is "emptied" when it is used to create pseudorandom numbers. An estimator keeps track of how much entropy is in this pool. Here's an analogy that might help: the system events and environmental noise are sort of like rolling a pair of dice, and the entropy pool is where you write down the numbers you rolled. The estimator is sort of like a count of how many times you've rolled the dice. From there, both /dev/random and /dev/urandom use hashing functions and other functions to "stretch" the entropy in the pool to be able to generate a lot more numbers than what is actually in the pool. (see @JohnDeters post where he explains the "sponge function").

NOTE: The term "entropy" here is being used somewhat loosely compared to the theoretical idea of "true" randomness/entropy, which is probably only found in quantum physics. For the purposes of computing, "entropy" tends to refer to things that seem random, and are extremely hard to predict. A closed software environment (i.e. the Linux operating system) must rely on things like environmental noise to "feed randomness" into the closed system. These environmental events are very hard for an attacker to observe, let alone predict, so they are considered sufficently "random" to fill the entropy pool. The closest thing to pure randomness for computers comes from a hardware random number generator. It uses measurements of things like electrostatic noise and even radioactive decay to seed your entropy pool.

The difference between the two devices is that /dev/random is considered theoretically stronger because it will not let you get any output if there is no entropy stored in the system. In contrast, /dev/urandom will use a hash function (SHA1, seeded from /dev/random) to continue to generate pseudorandom numbers even after it has depleted the pool, and there is no warning when the pool is empty. At that point, you are relying on the security of the hash function to prevent attackers from being able to reverse engineer the last random seed, and thus be able to predict the next pseudorandom number. However, they can only accomplish this if they can keep the pool exhausted until the next number is generated. In practice, using /dev/random is often viewed as overkill, although this is a hot-button issue.

Another NOTE: This construct (having /dev/random as a blocking device) is specific to Linux. BSD and Mac OS X both feature implementations that don't allow it to block. In those implementations, /dev/random is basically the same thing as dev/urandom, with some other special algorithmic features that keep it secure as long as it continues to be seeded somewhat regularly. So use whatever makes you happy, because it's the same either way. The developers of those systems are obviously of the camp that their implementation of the entropy pool is secure enough for all applications, present and future, and it's not worth the cost of dealing with the denial of service caused by blocking.

Bottom Line: Heed the warning when using the gpg --gen-random function, particularly if you are on a Linux system that relies on cryptographic security for other users. Furthermore, it's best to use /dev/urandom for almost everything with the exception of initial seeding of a fresh installation of the Linux kernel, and maybe cryptographic keys being used to guard national secrets for decades.

Answer 4

Your system accumulates a certain amount of entropy over time (in Unix systems, this randomness can be accessed at /dev/random). You, the user, is one source of randomness, but there are others too. It generally takes a while for considerable amount of entropy to accumulate.

From the Linux man page of random:

The random number generator gathers environmental noise from device drivers and other sources into an entropy pool. The generator also keeps an estimate of the number of bits of noise in the entropy pool. From this entropy pool random numbers are created.

Once any of those random bits are read, they can't be used anymore because they aren't fresh, and actions could have been performed based on those bits. You would ideally want these random bits to be independent of anything you have seen so far.

--gen-random is particularly tricky because, unless you specify the number of bits to output, it will keep printing all the random bits in the system, which reduces the pool of entropy in your system for future random number generations. This pool will replenish itself, but may take considerable time. In particular, if you try to generate secure key immediately after you have just printed all random bits, you may find yourself waiting for a long time until the entropy pool is replenished from environmental noise.

Answer 5

You can read about this at Wikipedia: Entropy.

Basically, computers are not capable of true randomness, the best they can do is to start with a seed value and roll it around a bunch of equations to get an output that looks random, but if an attacker knows your starting seed then it's not random at all.

The problem then is in collecting sufficiently "random" seeds. And of course, once you've used a seed you should really throw it out and collect another one. Most Operating systems (Windows, Linux kernel, etc) take care of this for you by maintaining a system-wide "entropy pool", ie a collection of as-random-as-possible bits. It collects these bits from timing of network packets, timing of keyboard and mouse events, etc. While not "random" in a philosophical sense, they are still hard for an attacker to guess.

I'm gonna simplify a bit here (I'm choosing explanability over correctness); an OS typically keeps around 512 bits (= 64 bytes) in its Entropy pool, so if you request 64 characters' worth of password then your OS will be "out of randomness" and any other program that needs random numbers will either have to wait, or start recycling seeds - very bad for crypto. The worst case is if you do this on a headless server with no mouse or keyboard input, and limited network traffic because it can take a very long time for the entropy pool to replenish.