New Linux kernel bolsters random number generation

Bigger changes are afoot in the next release, too

A significant rewrite of the Linux kernel's random-number generator is underway, ensuring Linux-based cryptography is a bit more secure, particularly in virtual machines, and some software a bit smoother to run.

As outlined by the author of the changes, Jason A Donenfeld, the newly released kernel 5.17 contains the first stage of the big rewrite, but more will follow in 5.18. Among other changes, the /dev/random and /dev/urandom devices now do exactly the same. This brings the Linux kernel in line with FreeBSD and macOS.

The code is contained in a module called random.c, originally written by Ted T'so for kernel 1.3 in 1994. It implements a Unix-style special character device called /dev/random which gives a stream of pseudorandom data. Building this into the kernel was a big deal, and the /dev/random device was adopted into DEC/Compaq Tru64, FreeBSD, HP-UX, IBM AIX, NetBSD, macOS, SGI IRIX, and Sun Solaris. This might make it one of the single most widely influential new features from Linux onto the broader Unix world.

Generating truly random numbers in pure software is non-trivial. If you run the same code repeatedly with the same inputs, it should produce the same results. Thus if you write a program to output random numbers, it'll produce a predictable, pseudorandom stream of values. If you can predict the output, you can figure out how software using it is going to work and, for instance, break encryption based on it. Researchers managed this for Windows 2000, for instance.

One way round this is to seed the random-number generator (RNG) with some truly random data – something like mouse movements, keyboard activity, and the timing of network packets and disk activity. In computer science terms, this is called entropy, and the Linux kernel maintains a pool of it to seed its RNGs.

When this entropy has all been used up, the RNGs will start to give random numbers that could be predictable, so programmers had to make a choice: go ahead with not-really-random-but-always-available numbers produced by /dev/urandom, or wait until some unpredictable ones were available from /dev/random. So, either block on /dev/random but be happy with the results, or don't block on /dev/urandom but don't use the numbers for anything sensitive. Blocking on entropy can introduce latency and delays in processing.

Another way is to use a hardware random-number generator (HWRNG), but there are problems with these, too. Sometimes they don't work right, for instance AMD's one in the Ryzen 3000 at launch. Sometimes they are merely suspect, as with Intel's after the Snowden revelations – which led FreeBSD to stop trusting them at all.

Linux eventually let you choose which HWRNGs to trust.

There have been previous big improvements in the kernel RNG. In kernel 4.8, /dev/urandom became cryptographically secure: a new algorithm, ChaCha20, made it resistant to analysis and prediction of forthcoming values. Kernel 5.6 made random and urandom devices similar. In 2020, /dev/random was tweaked to only block while waiting to be initialized. And now, both devices behave the same so you can use either without worry of processes stalling on an entropy drought nor worries about predictable randomness.

The changes in 5.17 eliminate use of the SHA-1 algorithm, which was cracked in 2005 and was being gradually replaced for years. Now it's gone, replaced by BLAKE2, a descendant of ChaCha20.

An important change is that the kernel can detect if it's running in a virtual machine that has been copied. A duplicate VM would contain an identical entropy pool as its parent, meaning that their RNGs would generate identical output.

Now, the kernel checks a new VM ID called vmgenid using ACPI. If the ID changes, the kernel mixes the ID into the entropy pool, changing it and thus making it unique. This may in time be exposed to programs via a new entry in /proc/sys. ®