Blog

Linux entropy woes


The canary in the coal mine

A lesser known but growing problem is PHP 7.2+ failing to initialise following a reboot on some VPS servers, cloud instances, and  virtual machines in general, from homegrown installations to major providers including; Digital Ocean, Amazon EC2, Linode, Vultr, Cloud A, and Scaleway. Our own experiments confirm taking 3-5 minutes after the boot process has completed to get any output from “php -v” on a single core VPS, which is in general agreement with other reports. Well before this time the init system will have killed the startup script.

The immediate cause is the inclusion of libsodium in the PHP core since 7.2, which hangs while waiting for the /dev/urandom CSPRNG to be initialised with sufficient entropy. The underlying cause is a lack of entropy at boot time, and this is a problem for any service which reads from /dev/random or /dev/urandom, or uses the getrandom() system call.

How the Linux kernel generates random numbers

A CSPRNG (cryptographically secure pseudorandom number generator) is an algorithm that operates on an initial value (seed) to generate a deterministic series, the seed is also known as the internal state of the CSPRNG. Determinism means that the next value in the series can be predicted provided that the seed is known. As long as the seed remains unknown however, the series is unpredictable, which gives the series the desired ‘randomness’. CSPRNGs create output that is computationally secure.

To seed the CSPRNGs, the kernel uses ‘true’ random numbers obtained from a variety of hardware sources, such as timings between keyboard and mouse input events, network packets, disk interrupts and so forth. These sources are processed and combined to form the input entropy pool.

Entropy is a measure of ‘unpredictability’. An entropy pool is data whose entropy is estimated by the kernel. The kernel estimates the entropy of the input pool, and provides a certain number of bits of entropy from the input pool to seed the CSPRNGs. The kernel also keeps track of the entropy of the internal states of the CSRPNGs, increasing the estimates when the CSPRNGs are seeded and decreasing them as and when the CSPRNGs generate output. Entropy estimation is said to be unreliable, perhaps for this reason the kernel estimates are (claimed to be) highly conservative.

For all intents and purposes, once a CSPRNG has been seeded with sufficient entropy it can create an indefinitely long random series that is computationally secure. ‘Sufficient’ entropy is currently defined by the kernel as 256 bits. Nevertheless, the kernel periodically reseeds the CSPRNGs ‘just in case’ an attacker were to obtain information about the internal state.

The number of CSPRNGs, entropy pools, and the relationships between them has changed over the years. Since kernel 4.8, the input pool feeds a primary CSPRNG, whose output is both read by /dev/random and is also used to initialise a secondary CSPRNG. Output from the secondary CSPRNG is read by /dev/urandom and the getrandom() system call. “Linux Random Number Generator - A New Approach” describes all of this in some detail. Decent schematics of previous versions are also available here and here.

Differences between /dev/random and /dev/urandom

Both /dev/random and /dev/urandom output pseudorandom numbers. The common myth that /dev/random provides ‘true’ random numbers and is therefore more secure than /dev/urandom is entirely false. Actual differences include the rules that govern the reseeding of their respective CSPRNGs and whether they block requests when entropy is low. See “Myths about /dev/urandom”.

The primary CSPRNG only provides as many bits of random output as there are bits of entropy in its internal state. The internal entropy is reseeded from the input pool (if possible) as it depletes. But if there is not enough entropy to satisfy a request, the primary CSPRNG blocks. Therefore, for every random bit that /dev/random produces, one bit of entropy is required and subtracted from the entropy ledger. Since gathering entropy from hardware sources is a relatively slow process, this makes /dev/random unsuitable for most applications, and since a CSPRNG only needs to be seeded once with 256 bits of entropy to provide a computationally secure series of random numbers of arbitrary length, using /dev/random usually provides no security benefits over /dev/urandom. As a result, almost all services use /dev/urandom.

/dev/urandom has the opposite problem, it doesn’t block at all. The secondary CSPRNG will provide output even if it has never been seeded. By contrast, FreeBSD does the right thing and blocks /dev/random and /dev/urandom if the CSPRNG has never been seeded, but when it has been seeded once it never blocks again. The getrandom() system call provided since version 3.17 of the Linux kernel also does the right thing, but it’s unfortunate that no userland device exists to take advantage of this, and that Linux is stuck with retaining the behavior of /dev/random and /dev/urandom for legacy support.

Detecting when /dev/urandom is safe to use

At boot time, the kernel prioritises the seeding of the secondary CSPRNG due to its non-blocking behaviour, sending all output from the primary CSPRNG to the secondary CSPRNG until the secondary CSPRNG has been seeded with 256 bits of entropy (source: “Linux Random Number Generator - A New Approach”.) Until the seeding is complete, no output is available to /dev/random. This leads to the standard approach for detecting the seeding of the secondary CSPRNG, described here and here and implemented in the libsodium source code, which is to attempt to read from /dev/random. Another approach uses getrandom(0) to the same effect.

The boot-time entropy hole

Headless devices and virtual machines typically lack abundant hardware sources of entropy, and during boot may fail to gather sufficient entropy to seed the CSPRNGs, necessitating the type of checks described above. This is compounded on VPS servers, which are both headless and virtual, especially when the number of CPU cores is low. “Mining Your Ps and Qs” uncovered widespread existence of weak or duplicate cryptographic keys, and coined the term “boot-time entropy hole” as the likely cause.

To address the issue, most if not all Linux distributions transfer entropy between boots by saving a seed file, usually 512 bytes, from /dev/urandom at shutdown, hopefully by which time the system has gathered enough entropy to seed the secondary CSPRGN. This file is read into /dev/urandom early in the boot process, causing the secondary CSPRNG to be immediately reseeded (on kernel 4.8+ at least, the timing for other kernels may vary). The procedure and an example implementation is described in the random(4) manpage and the random.c source code.

This approach works well on servers, where the time between reboots will almost always exceed the time taken to seed the secondary CSPRNG (e.g. the 3-5 minutes mentioned earlier). One issue not resolved though is that of cloning virtual machines, under which circumstances both machines may share similar internal states.

If Linux distributions are seeding the CSPRNG from file at boot, why then does PHP fail to start?

It’s an accounting problem. The kernel has no way of knowing what process generated the bits that are being written to /dev/random or /dev/urandom, and therefore no way of estimating their entropy. Therefore the entropy estimates are not updated. Therefore the tests described above are entirely uninfluenced. Do not pass go, do not collect £100. The random(4) manpage describes the situation:

Writing to /dev/random or /dev/urandom will update the entropy pool with the data written, but this will not result in a higher entropy count.  This means that it will impact the contents read from both files, but it will not make reads from /dev/random faster.

The “boot-time entropy hole” and the lack of a secure kernel facility to transfer entropy between boots creates a perfect storm.

Python 3.5.0+

A storm also erupted over Python, with Debian distributions failing to boot when running Python 3.5.0. This was due to making os.urandom() blocking by relying on the getrandom(0) system call, causing Python initialisation to hang under conditions of low entropy. As a result, a Python script in the Debian init process would be terminated by systemd causing the boot process to come crashing down. In 3.5.2, the behavior was reverted to non-blocking. Much discussion ensued.

A new security-sig mailing list, subtitled “os.urandom rehab clinic”, was created just to take a decision on os.urandom()

In 3.6.4 (PEP 524), os.urandom() blocking behavior was reintroduced, except during Python initialisation when the non-blocking behavior was retained. So if your PHP is hanging, you’ll probably find that os.urandom() hangs too, but at least Python might start!

The problem with blocking

People need their servers and services to work, and will do anything to make them work.

It inherently runs counter to availability. So your system is not working. It’s not doing what you built it to do. Obviously, that’s bad. You wouldn’t have built it if you didn’t need it. I’m working on safety-related systems in factory automation. Can you guess what the main reason for failures of safety systems is? Manipulation. Simple as that. Something about the safety measure bugged the worker. It took too much time, was too inconvenient, whatever. People are very resourceful when it comes to finding “inofficial solutions”.

But the problem runs even deeper: people don’t like to be stopped in their ways. They will devise workarounds, concoct bizarre machinations to just get it running. People who don’t know anything about cryptography. Normal people.

One proposed solution, seen a few times in various places, is the suggestion to download a 100Mb file from an external server to generate entropy from network and disk activity. Aside from depending on network availability, it gives outsiders some predictive power over the internal state of the system, and control over that state if they have access to the external server.

Other solutions seen include removing libsodium which is a useful security library, symlinking /dev/random to /dev/urandom, and feeding the output of the CSPRNG into itself.

In essence, trading an accounting problem for a security problem.

Solutions?

The most widespread recommendation is to use haveged. There are also widespread warnings not to do so, not because haveged is known to be insecure, but because, allegedly, its security is unknown, and possibly unknowable. The central contention is uncertainty over how much entropy the physical processes measured by haveged are providing, presumably due to insufficient modelling/understanding of the processes themselves. The output of haveged passes standard suites of statistical tests, but this is to be expected since the output comes from a CSPRNG. Statistical tests for randomness test for serial correlation, that is, whether knowledge about future values in a series can be obtained from observing previous values. But if the physical sources used to seed the CSPRNG provide little real entropy, thus allowing the internal state to be guessed, then the series can be predicted despite passing any and all statistical tests for randomness.

A host system should have plenty of entropy. It may be that the host kernel is already making entropy available to guests and activating a virtio-rng module on the guests is all that is required. This would probably be the ideal solution.

rng-tools is also widely recommended. This package provides the rngd daemon to detect hardware RNGs, such as the RDRAND instruction present in modern Intel and AMD processors, pass their entropy into the input pool, and update the entropy estimates. Unless the possibility that the closed source RDRAND has an NSA backdoor is a major concern, this can be a good solution. Following Linus Torvalds’ advice, the kernel mixes many sources of entropy and this is a good thing, so don’t swamp the input pool, mix just enough entropy for the initialisation tests to pass using the --fill-watermark=[XXXX] option.


By Spritely Design