int random() { return 4; /* Good enough. */ }[NB: Not posted to blog.NetBSD.org, because I think it's too opinionated, and I haven't done enough to warrant talking about.]
Problem: Computers are very predictable. This is by design.
But what if we want them to act unpredictably? This is very useful if we want to secure our private communications with randomized keys, or not let people cheat at video games, or if we're doing statistical simulations or similar.
The traditional way is by faking it. We take various things that are considered "hard enough to predict", such as high resolution timings of when certain signals from the hardware are received, or the output of various sensors that might include environmental noise (e.g. temperature).
We feed them into a hash function, then we use the output of that hash function to provide an initial seed for a random number generator. Modern secure random number generators are defined by having statistically random output (with no detectable bias towards returning certain values), and promise you shouldn't be able to predict their future outputs.
More recent hardware has introduced facilities for the system to receive "true" randomness from the environment. This includes things like Intel's RDRAND instruction. Most operating systems have chosen not to rely on these entirely, and instead feed their output into the hash to introduce additional entropy.
Recently, randomness in NetBSD was reworked to bring it up to spec with some new expectations. This was mostly done by Riastradh, and was prompted by some nagging by me and various others.
The most important of these expectations is that 256 bits of "good as unpredictable" values in the entropy pool are enough to generate random numbers for eternity, and that you don't lose entropy by using it to generate even more random numbers when you're using a modern algorithm for secure RNG. This remains true even after someone's used a quantum computer to break most of the world's cryptography.
How to obtain those initial 256 bits is a subject of some controversy.
If you've rebooted a system a few times, you're probably in a fairly good position.
On shutdown (these days between shutdowns too, just in case power is lost), the current state of the entropy pool as collected during the lifetime of the system is saved into a file so it can be loaded on next boot. This should include enough sufficiently unpredictable data to give you a pretty good security margin.
When the file is loaded, it's combined with additional entropy collected during the boot process.
The first time the system is booted, and early in the boot process, things get more difficult.
On modern AMD/Intel systems, and soon ARMv8.3, you can use the "random" instruction extremely early in the boot process. This is one of its main selling points - few setup requirements.
As far as we know, on normal systems RDRAND is secure.
We can run statistical tests on it to ensure that it's a quality source of randomness.
Right now, the kernel needs randomness early in the boot process - so early that it can't rely on many other sources. It takes the output of RDRAND, a high resolution timer, hashes them together, and uses them to seed the "early stage" random number generator.
A bigger concern is the idea that the instruction can be backdoored to influence the state of the random number generator, or even leak it.
A few people have demonstrated proof-of-concept attacks on virtual machines by introducing such a backdoor.
That's very scary.
In NetBSD, we support a wide range of hardware.
Some of this hardware sucks.
Recently, Riastradh committed a driver for the "true randomness" device on Allwinner-based ARM boards, and ran some statistical tests on it. He found it produces highly biased output. The output is still fed into the entropy pool, but now, we know we can't rely on it.
Some of this hardware might be small embedded systems that don't have many sensors, no source of hardware RNG, and only a few clock timings from something like a network interface controller. A problem Riastradh raised is that an attacker might be able to feed packets into the system and produce a predictable initial state.
Is this a realistic threat model? Would an attacker be able to influence network timings down to the microsecond/nanosecond to ensure a predictable initial RNG state?
You might want to wait during the boot process for enough entropy to be collected from decent sources, but in some cases, on the very worst of terrible hardware, you might be waiting forever. So, in a worst case scenario, you might want to generate a seed file on another machine.
Some systems are very picky over what they consider "high quality randomness".
Sometimes, this includes hardware RNG and nothing else, with no concern for whether that hardware RNG is backdoored.
Sometimes, this includes basically everything, like the name of the hardware you're using. Apparently, that's valid entropy - if your goal is to increase the size of the pool with no regard for actual randomness.
[NB: I'm not naming the operating systems described here to avoid diluting any of my points by shit-talking anyone. You can probably guess, though.]
One of the recent changes to the kernel include the removal of a mechanism that attempted to evaluate the quality of the samples fed into it (this was deemed too unscientific). Instead, it's the responsibility of each driver to report the value of the entropy it's providing.
In most cases drivers are considered to provide 0 bits of entropy, unless the quality of the randomness they're providing can be proven.
I fought for a compromise here: Just as userland is initialized, before any daemons are started, we consolidate any entropy fed into the pool, and reseed the random number generators in the kernel.
My goal was to ensure that we have collected from as many potential sources of randomness as possible to ensure a quality initial seed for userspace random number generators. So, it includes everything, including sources considered "low value", like interrupt timings.
Even on terrible hardware, we don't want it to be possible to generate weak keys on initial boot. The kernel will be very noisy if it suspects this might happen.
I'm just some hacker chick and not a security expert or cryptographer (but I play one online).
Here's my take: we're all screwed. Hopefully, exploiting that is hard enough that nobody figures it out.
If you feel like being a NetBSD lawyer, you can read rnd.4. It references some interesting papers.
2020-05-08