Uniting the Linux random-number devices
Please consider subscribing to LWN Subscriptions are the lifeblood of LWN.net. If you appreciate this content and would like to see more of it, your subscription will help to ensure that LWN continues to thrive. Please visit this page to join up and keep LWN on the net. |
Blocking in the kernel's random-number generator (RNG)—causing a process to wait for "enough" entropy to generate strong random numbers—has always been controversial. It has also led to various kinds of problems over the years, from timeouts and delays caused by misuse in user-space programs to deadlocks and other problems in the boot process. That behavior has undergone a number of changes over the last few years and it looks possible that the last vestige of the difference between merely "good" and "cryptographic-strength" random numbers may go away in some upcoming kernel version.
Random history
The history of the kernel RNG is long and somewhat twisty; there are two random-number devices in the kernel, /dev/random and /dev/urandom, that can be read in order to obtain the random data. /dev/urandom was always meant as the device for nearly everything to use, as it does not block; it simply provides the best random numbers that the kernel can provide at the time it is read. /dev/random, on the other hand, blocks whenever it does not have sufficient entropy to provide cryptographic-strength random numbers. That entropy comes from sources like interrupt timing for various kinds of devices (e.g. disk, keyboard, network) and hardware RNGs if they are available. /dev/urandom will log a warning message (once) if it is called before its pool is initialized (from the random pool once it has been initialized using gathered entropy), but it will provide output from its pseudorandom-number generator (PRNG) and never block.
In 2014, for Linux 3.17, the getrandom() system call was added to provide a reliable way for user-space applications to request random numbers even in the face of file-descriptor exhaustion or lack of access to the random devices (as might happen for an application running in a container). getrandom() was designed to use the urandom pool, but only after it has been fully initialized from the random pool. So, while reads to /dev/urandom do not block, calls to getrandom() would until the requisite entropy is gathered. getrandom() callers can choose to use the random pool via a flag, which makes the call subject to the full entropy requirements for data coming from that pool.
In 2019, an unrelated change to the ext4 filesystem led to systems that would not boot because it reduced the number of interrupts being generated, so the urandom pool did not get initialized and calls to getrandom() blocked. Since those calls were made early in the boot process, the system never came up to a point where enough entropy could be gathered, because the boot process was waiting for getrandom() to return—thus a deadlock resulted. The ext4 change was temporarily reverted for the 5.3 kernel and a more permanent solution was added by Linus Torvalds for 5.4. It used CPU execution time jitter as a source of entropy to ensure that the random pool initialized within a second or so. That technique is somewhat controversial, even Torvalds is somewhat skeptical of it, but it has been in place, and working as far as anyone can tell, for several years now.
In 2020, the blocking nature of /dev/random was changed to behave like getrandom(),
in that it would only block until it is initialized, once, and then
would provide cryptographic-strength random numbers thereafter. Andy Lutomirski, who
contributed the patches for that change, said: "Linux's CRNG
generates output that is good enough to use even for key generation. The
blocking pool is not stronger in any material way, and keeping it around
requires a lot of infrastructure of dubious value.
" Those patches
also added a GRND_INSECURE flag for getrandom() that
would return "best effort" random numbers even if the pool was not yet
initialized.
As can be seen, the lines between the two devices have become rather blurrier over time. More of the history of the kernel RNG, going even further back in time, can be found in this LWN kernel index entry. Given that the two devices have grown together, it is perhaps no surprise that a new proposal, to effectively eliminate the distinction, has been raised.
No random blocking (for long)
Jason A. Donenfeld, who stepped up
as a co-maintainer of the kernel's RNG subsystem a few months back, has
been rather active in doing cleanups and making other changes to that code
of late. On February 11, he posted
an RFC—perhaps a "request for
grumbles
" in truth—patch proposing the removal of the ability for
/dev/urandom to return data before the pool is initialized. It would mean that
the kernel RNG subsystem would always block waiting to initialize, but always return
cryptographic-strength random numbers thereafter (unless the
GRND_INSECURE flag to getrandom() is used). Because of
the changes made by Torvalds
in 5.4, which Donenfeld calls the "Linus Jitter
Dance
", the maximum wait for initialization is minimal, so Donenfeld
suggested the change:
So, given that the kernel has grown this mechanism for seeding itself from nothing, and that this procedure happens pretty fast, maybe there's no point any longer in having /dev/urandom give insecure bytes. In the past we didn't want the boot process to deadlock, which was understandable. But now, in the worst case, a second goes by, and the problem is resolved. It seems like maybe we're finally at a point when we can get rid of the infamous "urandom read hole".
There are some potential hurdles to doing so, however. The jitter entropy technique relies on differences in timing when running the same code, which requires both a high-resolution CPU cycle counter and a CPU that appears to be nondeterministic (due to caching, instruction reordering, speculation, and so on). There are some architectures that do not provide that, however, so no entropy can be gathered that way. Donenfeld noted that non-Amiga m68k systems, two MIPS models (R6000 and R6000A), and, possibly, RISC-V would be affected; he wondered if there were other similarly affected architectures out there. He believes that the RISC-V code is not truly a problem, however, and no one has yet spoken up to dispute that. Meanwhile, setting those others aside might be the right approach:
If my general analysis is correct, are these ancient platforms really worth holding this back? I halfway expect to receive a few thrown tomatoes, an angry fist, and a "get off my lawn!", and if that's _all_ I hear, I'll take a hint and we can forget I ever proposed this. As mentioned, I do not intend to merge this unless there's broad consensus about it. But on the off chance that people feel differently, perhaps the Linus Jitter Dance is finally the solution to years of /dev/urandom kvetching.
The proposed patch was fairly small; it simply eliminated the file_operations struct for /dev/urandom and reused the one for /dev/random in its place, thus making the two devices behave identically. It also shorted out the behavior of the GRND_INSECURE flag, but he later said that was something of a distraction. The main intent of his proposal was to do the following:
Right now, we have:/dev/random = getrandom(0) /dev/urandom = getrandom(GRND_INSECURE)This proposal is to make that:/dev/random = getrandom(0) /dev/urandom = getrandom(0)
Torvalds had a positive
response
to the RFC. He said that the patch makes sense for architectures that have
a cycle counter; the jitter entropy change has been active for
two-and-a-half years without much complaint, so "I think we can call
that thing a success
". There may have been a few complaints about it,
but: "Honestly, I think all the complaints would have been from the
theoretical posers that don't have any practical suggestions
anyway
". Torvalds is known to have little patience for theoretical concerns about cryptography (or
theoretical concerns about anything else, in truth).
He did object to removing GRND_INSECURE for architectures that cannot do the jitter dance, since it is a way for user space to work around the lack of boot-time entropy, even if it is not at all secure:
Those systems are arguably broken from a randomness standpoint - what the h*ll are you supposed to do if there's nothing generating entropy - but broken or not, I suspect they still exists. Those horrendous MIPS things were quite common in embedded networking (routers, access points - places that *should* care)[...] And almost nobody tests those broken platforms: even people who build new kernels for those embedded networking things probably end up using said kernels with an existing user space setup - where people have some existing saved source of pseudo-entropy. So they might not ever even trigger the "first boot problem" that tends to be the worst case.
But, he said, he would be willing to apply the patch: "at some point 'worry
about broken platforms' ends up being too weak an excuse not to just
apply it
". According to Joshua Kinard, the two MIPS models in
question were from the 1980s, not ever used in systems, and the kernel test
for them in the random code "was probably added as a mental exercise following a
processor manual or such
". Maciej W. Rozycki said
that there may have been a few systems using those models, but no Linux
port was ever made for them. That might mean that the only problem systems
are "some m68k
museum pieces
", Donenfeld said.
As Geert Uytterhoeven pointed
out, though, the cycle-counter code for the Linux generic architecture,
which is the default and starting point for new architectures, is hardwired
to return zero. "Several architectures do not implement get_cycles(), or implement it
with a variant that's very similar or identical to the generic
version.
" David Laight added
a few examples (old x86, nios2) of architectures where that is the case.
But what about my NetHack machine?
Lutomirski had a more prosaic complaint:
I dislike this patch for a reason that has nothing to do with security. Somewhere there’s a Linux machine that boots straight to Nethack in a glorious 50ms. If Nethack gets 256 bits of amazing entropy from /dev/urandom, then the machine’s owner has to play for real. If it repeats the same game on occasion, the owner can be disappointed or amused. If it gets a weak seed that can be brute forced, then the owner can have fun brute forcing it.If, on the other hand, it waits 750ms for enough jitter entropy to be perfect, it’s a complete fail. No one wants to wait 750ms to play Nethack.
More seriously, he was concerned about devices like backup cameras or light bulbs that need to boot "immediately", and where the quality of the random numbers may not truly be a problem. The GRND_INSECURE escape hatch is there for just that reason. In a similar vein, Lennart Poettering was worried that systemd would have to wait one second to get a seed for its hash tables, when it already has a mechanism to reseed the tables:
So, systemd uses (potentially half-initialized) /dev/urandom for seeding its hash tables. For that its kinda OK if the random values have low entropy initially, as we'll automatically reseed when too many hash collisions happen, and then use a newer (and thus hopefully better) seed, again acquired through /dev/urandom. i.e. if the seeds are initially not good enough to thwart hash collision attacks, once the hash table are actually attacked we'll replace the seeds with [something] better. For that all we need is that the random pool eventually gets better, that's all.
It turns out that systemd is already using GRND_INSECURE on systems where it is available, so not changing that behavior, as was originally proposed, would neatly fix Poettering's concern. Donenfeld was completely amenable to pulling the disabling of GRND_INSECURE from his patch; it is not really his primary focus with the proposal, as noted.
Based on Torvalds's response, it would seem there are no huge barriers to
removing the final distinction between /dev/random and
/dev/urandom—other than the names, of course. If there are more
architectures that cannot use the jitter technique, though, that
distinction may live on, since Torvalds also thought there might be value
in keeping "the stupid stuff around as a 'doesn't hurt good platforms, might
help broken ones'
". The code removal would not be huge, so it does
not really provide much of a code simplification, Donenfeld said; it is
more a matter of being able to eliminate the endless debate about
which source of randomness to use on Linux. To that end, it seems like a
worthwhile goal.
Index entries for this article | |
---|---|
Kernel | Random numbers |
Security | Linux kernel/Random number generation |
(Log in to post comments)
Uniting the nethack random-number devices
Posted Feb 17, 2022 16:30 UTC (Thu)
by ballombe (subscriber, #9523)
[Link] (3 responses)
<https://nethackwiki.com/wiki/Random_number_generator>
Uniting the nethack random-number devices
Posted Feb 18, 2022 1:33 UTC (Fri)
by qys (subscriber, #156455)
[Link]
Uniting the nethack random-number devices
Posted Feb 18, 2022 17:45 UTC (Fri)
by ejr (subscriber, #51652)
[Link]
Uniting the nethack random-number devices
Posted Feb 21, 2022 14:33 UTC (Mon)
by error27 (subscriber, #8346)
[Link]
v1 posted
Posted Feb 17, 2022 16:33 UTC (Thu)
by zx2c4 (subscriber, #82519)
[Link]
Uniting the Linux random-number devices
Posted Feb 18, 2022 3:08 UTC (Fri)
by developer122 (guest, #152928)
[Link] (3 responses)
At the moment, both /dev/random and /dev/urandom block, until they have enough entropy. However their entropy sources differ. /dev/random draws from "truly random, crpto-ready" bits that came directly from a hardware source of some kind, where as /dev/urandom draws from a PRNG that is seeded from /dev/random's hardware-backed bits.
But we don't care, because the bits that have passed through the pseudo-RNG have like 99% of the randomness of the hardware bits and are "good enough" for crypto to rely on? (even though they might be a little stale if it's been a while since the PRNG was re-seeded)
I _suppose_ that drawing from /dev/urandom right after it's been seeded the first time with bits from /dev/random might be just as good as drawing from /dev/urandom, but what's the difference in their worst case? ie. if I'm an attacker and later I draw 1 billion numbers from the PRNG before the next time it's re-seeded.
Uniting the Linux random-number devices
Posted Feb 18, 2022 5:59 UTC (Fri)
by Otus (subscriber, #67685)
[Link]
Uniting the Linux random-number devices
Posted Feb 18, 2022 16:58 UTC (Fri)
by derobert (subscriber, #89569)
[Link]
Originally /dev/random made some guess of when entropy was "depleted", but that didn't really make sense — one effect of a PRNG being cryptography secure is it doesn't deplete the entropy. So a while back, that was removed.
An attacker can gain no knowledge of the CSPRNG's state from its output (well, at least not without an impossible number of them, like 2^128). It doesn't matter if they have a few billion or trillion.
And Linux keeps mixing in new entropy, so the internal state changes over time.
Uniting the Linux random-number devices
Posted Feb 19, 2022 14:37 UTC (Sat)
by ianmcc (subscriber, #88379)
[Link]
Once /dev/urandom is properly seeded (or you read from /dev/random), if you're an attacker and you draw 1 billion numbers, ... it doesn't help you because you can't crack the crypto in the PRNG. (well, if you *can*, you've made a breakthrough in crypto that will make you as famous as you'll be infamous).
In the old days (well, I think prior to 2020? So not so old), /dev/random would remove N bits of entropy from the pool for every N bits read from /dev/random, and if there isn't N bits of entropy available then it would block until there is. This was based on a misunderstanding that you need to consume entropy to generate cryptographically secure random numbers. But if you use a cryptographically secure PRNG, then you only need enough bits of entropy for the seed of the PRNG, and you can generate as many secure random bits as you like. Predicting the next number in the sequence requires determining the internal state of the PRNG, which isn't possible from examining the prior output (as long as the crypto algorithm doesn't contain any flaws). So there is an assumption that the crypto is strong and won't be broken.
Uniting the Linux random-number devices
Posted Feb 21, 2022 23:40 UTC (Mon)
by koh (subscriber, #101482)
[Link] (6 responses)
While that change may have been motivated by practical reasons, it nonetheless means you now get a filtered view on random bits - filtered through the eyes of crypto-strength. It may easily not be what an application wants to receive. This blurring of semantics concerns me.
Uniting the Linux random-number devices
Posted Feb 22, 2022 8:30 UTC (Tue)
by atnot (subscriber, #124910)
[Link] (5 responses)
Uniting the Linux random-number devices
Posted Feb 27, 2022 0:28 UTC (Sun)
by koh (subscriber, #101482)
[Link] (4 responses)
well, that's cheap; of course not and it's beside the point.
> that makes this distinction remotely meaningful in any way
This is more to the point: before I could assume that /dev/random gives to me whatever the hardware generates - meaning, I can test the acquired data itself, develop and test hardware based on it and even find out when there is not enough data. I realize that the last point was meant to be fixed, but it does constitute a quite substantial shift in semantics I honestly see no reason for - if you want unlimited "randomness" go for /dev/urandom. Hiding the distinction between the two devices is a step in the wrong direction.
Uniting the Linux random-number devices
Posted Feb 28, 2022 4:06 UTC (Mon)
by nybble41 (subscriber, #55106)
[Link] (3 responses)
That has not been the case in any version of /dev/random in Linux since the feature was first implemented as a mix of sources of hardware entropy based on secure hashes in 1994. The notable differences since then are (a) using better mixing functions, (b) adding more sources of entropy, and (c) no longer limiting the amount of data read (after initialization) based on a flawed interpretation of entropy.
If you want "raw" random data from hardware then you want /dev/hwrng, not /dev/random.
Uniting the Linux random-number devices
Posted Feb 28, 2022 22:57 UTC (Mon)
by koh (subscriber, #101482)
[Link] (2 responses)
Uniting the Linux random-number devices
Posted Feb 28, 2022 23:17 UTC (Mon)
by mpr22 (subscriber, #60784)
[Link]
Uniting the Linux random-number devices
Posted Mar 1, 2022 11:07 UTC (Tue)
by neggles (subscriber, #153254)
[Link]
Under the current behaviour, /dev/random will block if the CSPRNG has not yet been fully seeded, and /dev/urandom will not. For 99.9% of use cases in userspace there's no functional difference between the two; by the time your program is running, the CSPRNG will almost certainly be fully seeded. on a systemd system it definitely will be.
systemd and other initsystems are just about the only place where the distinction between "blocks until fully seeded" and "gives you the best numbers it can even if they suck" - as Lennart mentioned here, systemd uses the non-blocking source during early boot to seed some hash tables; the quality of that randomness is not important since they'll be reseeded later if collisions occur, but it can't carry on with boot until it's got something to work with.
In other words, the distinction only really matters if you're writing an initsystem.