70 comments

[ 3.9 ms ] story [ 137 ms ] thread
>The /dev/random is the “very foundation” of cryptography on Linux, developer Stephan Müller told The Daily Swig. “If /dev/random breaks, the entire cryptography on Linux is broken,” Müller said.

I thought using /dev/random was depricated and that you should instead use a getrandom syscall that blocks if you don't have enough entropy.

in the the man page they say only legacy

> The /dev/random device is a legacy interface which dates back to a time where the cryptographic primitives used in the implementation of /dev/urandom were not widely trusted. It will return random bytes only within the estimated number of bits of fresh noise in the entropy pool, blocking if necessary. /dev/random is suitable for applications that need high quality randomness, and can afford indeterminate delays.

and recommend:

> Linux 3.17 and later provides the simpler and safer getrandom(2) interface which requires no special files; see the getrandom(2) manual page for details.

You're right, but when kernel developers talk about /dev/random they generally mean the underlying RNG, not the interface by which you access it. To a userland developer the phrase "read from /dev/random via the getrandom system call" is nonsense but to a kernel developer it sounds reasonable.
/dev/random does block "if you don't have enough entropy" (in contrast to /dev/urandom, which doesn't). The only difference is that getrandom() doesn't require a file descriptor to use.

Note that "if you don't have enough entropy" is not based on any rigorous formal analysis, which is why /dev/urandom has been recommended for a long time, and why the entire concept of blocking randomness syscalls is controversial in kernel-land:

https://lwn.net/Articles/800509/

> blocks if you don't have enough entropy

Which, in most cases I can think of is a rather undesirable behavior.

I would really be interested to understand which use cases justify using an actual blocking call to retrieve random bits.

I've always been under the impression that the only valid use case for raw entropy bits is regularly seeding crypto-hard RNGs that can generate an endless stream of random bits (à la /dev/urandom).

Looking forward to being educated on the topic.

Correct behavior: Block (or don’t be available) until you can securely generate an effectively endless stream of random bits, then never.

Correct API: https://fuchsia.dev/fuchsia-src/reference/syscalls/cprng_dra...

I decided to have a quick look, and this caught my eye: —- zx_cprng_draw() terminates the calling process if buffer is not a valid userspace pointer. ——

”Terminates the calling process”? That sounds different and interesting, do you know more about this aspect of Fuchsia?

I'm not too familiar with Fuchsia, but other syscalls return ZX_ERR_INVALID_ARGS so I suspect the idea was to keep this particular, security-critical call as simple as possible. This behavior shouldn't break any code that wasn't already broken.
> I would really be interested to understand which use cases justify using an actual blocking call to retrieve random bits.

The only case I can think of is when you've mass produced a million devices that each need unique certificates that are generated on first boot. If no good source of randomness is available, there's a decent risk you'll have duplicates.

If lives (or life savings) are at stake, I'd still xor some dice values in the mix.

https://glacierprotocol.org/docs/deposit/generate-cold-stora...

Or some lava lamps
lavarand was invented and patented by SGI in 1996: https://www.lavarand.org/news/lavadiff.html
There was a library to use webcams for entropy called lavarnd up until about 8 years ago, as well. I am unsure if the api to the os changed or there's a functional difference between ccd and cmos or whatever.

I do a lot of entropy research, and was annoyed I had to roll my own implementation for a no-photon camera entropy source.

Which comes directly from a suspected NSA mouth. No, it's from the German BSI, which is a NSA collaborator.

Still better than the current implementation.

How to measure randomness ? Even distribution ? Volatility ? Independence ?
You can't truly measure randomness, by definition a true random source would have exactly the same probably to produce any sequence of bits, so given any two sequences it is impossible to say for sure that one is "more random" than another.

However there are many well-accepted tests for judging that a sequences of bits is likely to be random. Basically these tests are looking for common failure modes and expected statistics that are likely to fail if your source isn't truly random (for example distribution skew, repeating patterns, ...).

But it is important to clarify that these tests are guesses. The have both false-positives and false-negatives. For example a "random number generator" that just has a large hardcoded list of random-looking values and loops over the list may pass a test if the list is long enough that the loop can't be detected, even though the values are decidedly not random. On the other hand a true random source may generate a very long sequence of zeros, the probability would be infinitesimal, but it is entirely possible and doesn't mean that the source isn't random.

I have a question about the statement "you can't truly measure randomness", if it's alright (since you seem knowledgeable about this).

> For example a "random number generator" that just has a large hardcoded list of random-looking values and loops over the list may pass a test if the list is long enough that the loop can't be detected, even though the values are decidedly not random.

My understanding is that's entirely fine from a statistical point of view. One can establish properties of this sequence up to some probabilistic error, perhaps also depending on the total number of values from the list that end up being used.

Isn't this in some sense analogous to measurement error? As far as I know, nothing can be precisely "measured" either. Is there a deeper sense in which the quality of the random sequence can't be analogously assessed?

> since you seem knowledgeable about this

I should probably state to be clear that I am not a cryptographer. I just have an interest in the subject.

It also depends a lot what you mean by random. I generally take "random value" to mean "a value which can not be predicted". Of course in cryptography we often use a CSPRNG which can be perfectly predicted, it is deterministic, not random at all! However in that case what we actually care about is "a value which can not be predicted without knowing the secret state". For many use cases this is sufficiently close to true random. (Or the predictability can actually be useful, for example using a CSPRNG as a stream cypher.)

The reason why I said that my large hardcoded list was not random is that it is predictable. It is easily predictable if you know the hardcoded list of course. But even if you declare that list as "secret state" it is still predictable once it starts repeating and spews out the exact sequence of bits over and over again.

> My understanding is that's entirely fine from a statistical point of view.

Sure, but statistics are different than cryptography. If you just want your simulation to work well it is probably fine (unless the repeating causes funny artifacts in the simulation). I would argue that for most non-cryptographic use cases you don't even need anything close to "true random", you just need a distribution that matches your desired distribution with little bias and ideally doesn't repeat in a way that aligns poorly with how you use the numbers.

> Isn't this in some sense analogous to measurement error?

I'm not sure I completely follow here but I think the answer is "no". The difference is that randomness is a property of the generation process, not the output. https://xkcd.com/221/ is a great way to highlight this. In this case 4 was a very good quality random number. No once could have predicted it with greater that 1/6 probability. However once you check it into source code it isn't "random" any more. This is because the die produces "random numbers" but there is nothing special about the number itself. There is no test that will tell you that "4" is random or non-random, the question doesn't really make sense.

What the tests do is they take a list of values and try to detect "problems" (situations in the output that would be unlikely if the source was truly random). For example if you have a weighed die that rolls 6 80% of the time a good test will tell you that your random source is likely biased based on a sample of output values. Of course the more data you feed to the test the more likely that it is that failures are true failures. If you roll a die 10 times and don't get a 6 it isn't proof that the die is unfair or predictable in some way. If you roll that same die 1000 times without a six it is looking much more suspicious, but still impossible to prove just by looking at the outputs.

> For example a "random number generator" that just has a large hardcoded list of random-looking values and loops over the list may pass a test if the list is long enough that the loop can't be detected, even though the values are decidedly not random.

Even cryptographically secure RNGs have fixed periods, they are not infinite. What's important is how long that "list" is. So for purposes of computer randomness, a long fixed list may indeed be okay if it is truly long enough. It will need to be truly massive to pass Diehard though.

For sure. However most CSPRNGs have "huge" periods which would be infeasible to hardcode into a software implementation. Knowing your period is important any time you use a PRNG for cryptography.
(comment deleted)
We should be stirring in the low bits of image pixels on attached cameras, and the bottom bits of mic and radio receiver input.
Only if we trust the camera to not have a specific upper limit on image processing. It's also a decent attack vector. Any old USB plug could lower system entropy. If everything else is done properly this isn't an issue, but it still seems to increase attack surface area for little gain.
If we use a secure cryptographic algorithm which combines different entropy sources and then hashes them together, even a completely insecure additional source of entropy will not reduce the security of /dev/random [1]

If we have 10 different sources of entropy for our random number generator, and only one of them is truly random, our random number generator is still secure.

[1] There’s an issue where /dev/random will have less actual entropy than it think it has, but as long as we have 128 bits[2] or more of actual entropy, the output will still be secure.

[2] 256 bits if worrying about quantum computers or theoretical future computers the size of a continent

What exactly is the point of adding 9 known insecure sources if only one is doing the actual useful work? Is it less secure? I guess not. Is it more secure? Doesn’t seem like it.
If you add 9 known not-very-good sources of randomness, it's still better than adding no sources of randomness.

Now if your 9 bad sources are 100% predictable, then yes, there's no point in adding them.

You wouldn't. He is just talking about a worst case scenario. He's is saying that as long as one of your sources of randomness is "truly" random you are fine.l
(comment deleted)
> Is it more secure? Doesn’t seem like it.

Why not? Unless all 9 "insecure" sources are 100% attacker-controlled or broken at the same time, they would still be adding entropy.

Each additional source is adding one more hoop for the attacker to have to jump through.

The more sources are added, the less the chance that all of them are broken or attacker-controlled at the same time on the same computer.

Conversely, if you only have one (presumably good) entropy source it would be much easier for it to be compromised than if you have 10 sources, including the good one (even though some of them are easier to break than others).

Suppose you have 10 sources of entropy and you don't know which ones are good. If you pick one, and you pick the wrong one, you lose. If you use all of them with an algorithm that works as long as any one of them is good, and any one of them is good, you're good.
The question is, which sources are "known secure"? There have been AMD systems where RDRAND is broken and always returns the same value -- I bet those users would have been happy if their webcam got mixed in.
Even if their webcam was pointed at a black wall in a dark room?
I just checked and my camera, even if a close the cover and put it under a blanket, still doesn't return straight zeroes. As long as there is some "fuzz" there is something useful to generate randomness.

Also, it would be reasonable for the RNG to notice some source is returning input of no value (straight zeroes) and reject it.

You can actually use a camera sensor as a kind of Geiger counter by blocking normal light eg with foil and measuring fluctuations in the results!
It is not possible for any such attack to "lower system entropy". Bytes stirred into the pool can only ever add entropy.
That's more high level then what kernel normally deals with. You can use rngd in userland to do it though.
Turning on the camera for any reason would creep me out
So, stir them in only if it is being used anyway.
There is a lot said for making the Linux random number generator configurable. A good entropy (random number) source takes entropy from a number of different sources and combines it with a cryptographic strong algorithm: Either a strong hash whose output is made the key and IV for a stream cipher, or directly using an Extendable-Output Function (XOF) such as a cryptographic sponge. [1]

For example, there is some controversy with the RDRAND (the x86 ”give me random bits” op code) operation, with concerns that maybe the numbers weren’t truly random, and at least one known security hole where the RDRAND output could leak under some circumstances. However, it’s widely available and probably makes good random bits. However, if it doesn’t, we want other sources of entropy (microphone output low bits, interrupt timings, etc.) so /dev/random or /dev/urandom still gives us strong entropy even if RDRAND is completely busted.

[1] I personally think a cryptographic sponge is ideal for this, since sponge functions have absorb, output, and duplex (absorb after output, i.e. accept new entropy from the system after outputting bits) functionality

When I first got my Ryzen CPU, it had some bug where RDRAND always returned -1! Fortunately this was fixed in a microcode update.
Experienced something similar here. NodeJS node-sass would crash with "rdrand failed". Super weird experience to have to apply a BIOS update to fix a node_modules build failure, but that's 2021.
While having it configurable is one option, I'd prefer to just "chuck everything in".

A feature I would like (which would make things more complicated I realise) would be to have a variety of sources, which estimated quality for each source, and then check the quality is still high even if one of the sources is "broken".

> According to Müller, LPRG incorporates four entropy sources that operate completely independent of each other including execution timing jitter and the timing of the arrival of interrupts.

Can you 'lie' to the operating system about these sources of entropy in order to control the random number generation?

Last time i checked, /dev/random was receiving entropy from

* The kernel command line string at boot.

* Every time there is an input event (mouse, keyboard, ...).

* Every time there is a disk event.

* By retrieving the cpu cycles counter (RDTSC on x86) from random interrupts.

* Hardware RNGs(RDRAND on x86).

* From latent entropy every time a process is created.

Latent entropy is a 64 bits unsigned that has its state modified every time a procedure with the attribute latent_entropy is executed. The latent_entropy attribute is implemented by a GCC plugin and adds random operations on the latent_entropy seed to a procedure. For example

    void foo(bool a) __attribute__((latent_entropy))
    {
        if (a)
            bar();
        else
            baz();
    }
 
become

    void foo(bool a) __attribute__((latent_entropy))
    {
        if (a)
        {
            latent_entropy OP NUMBER;
            bar();
     }
        else
        {
            latent_entropy OP NUMBER;
            baz();
        }
    }
where OP (*= += -= ^= ...) and NUMBER are randomly generated at compilation time.

Many kernel procedures handling interrupts have the latent_entropy attribute.

more information at https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

You never hear about developments of the RNG on other OSes. It gives me more confidence that the Linux RNG is constantly being reviewed.
> You never hear about developments of the RNG on other OSes.

Probably because you don't listen?

> It gives me more confidence that the Linux RNG is constantly being reviewed.

It took decades for the linux devs to abandon their idiotic concept of running out of entropy and making /dev/random stop blocking (that happened last year in the 5.6 kernel).

Hell, after getentropy was introduced by openbsd, not only did linux decide to invent their own variant they just had to replicate /dev/random's running-out-of-entropy behaviour.

> It took decades for the linux devs to abandon their idiotic concept of running out of entropy and making /dev/random stop blocking (that happened last year in the 5.6 kernel

It wasn't an idiotic concept it was 1 part "No longer needed for trust in the algorithms used by /dev/urandom" and 1 part "Did 2 functions but was really used for 1". Since the majority of people were using it just as a source of secure random data (not the 2nd use of aggregating sources of entropy) and CSPRNGs (and the implementation of in the kernel) are much more trusted now it made sense to change. That doesn't mean it was an idiotic concept it just outlived its reasons for having been implemented that way and was changed.

For clarity's sake to others that may not be as familiar /dev/random still blocks it was the concept of the blocking pool that was removed. I.e. once it has been fully initialized post boot it will serve an endless stream of random data as fast as it can regardless of how much new entropy enters the system. This is what tools actually need, some other systems have provided this via a separate /dev/arandom. /dev/urandom still acts the same way it always has, it'll serve you the output of the CSPRNG regardless if it has had enough time to properly seed it with entropy yet (so may act more like a standard PRNG very early into the boot cycle).

This is something that has frustrated me for years. There has been no interest in modernizing the Linux PRNG really ever. This article doesn't go into more depth so I don't know if it's just tacking on more entropy sources and algorithm support or a real modernization.

Windows, MacOS, every BSD, Solaris, etc. have moved past the (blocking) /dev/random vs /dev/urandom to more mathematically sound solutions. (Seriously, measuring entropy?) But Torvalds, Ts'o, etc. have blocked, belittled, or ignored any movement there.

It's crazy that the OS that runs all the things essentially has a roll-your-own-crypto PRNG at its core rather than relying on actual experts for that.

Unfortunately, it's "good enough" to not HAVE to change. Use /dev/random sparingly to seed your own PRNG, change your Java config to use /dev/urandom, or (shudder) use rngd to make it seed itself.

At least once a year I hit some COTS product that craps itself under load blocking on /dev/random on a VM, causing an outage. Yes, it's a "worked on my laptop" problem, but an unnecessary rake to leave out in the garden.

Blocking /dev/random has been a problem that many people were interested about for a long time, and it has had alternatives: /dev/urandom since forever (though it has a big problem for some short period just after bootup), getentropy() since 2015 can do the right thing with the right options, and finally since 2020 /dev/random does the right thing - it only blocks until seeded, then gives unlimited secure random bytes. (I only learned about this 2020 update in this very thread!)

My understanding is that /dev/random behavior persisted for so long only due to some dumb corporate/military compliance thing that some huge companies "needed". EDIT: apparently this was due to NIST standard SP800-90B and maybe German AIS 31, and the most recent idea is to forget them, and have orgs that really need the strange/problematic blocking behavior implement it in user-space.

tl;dr the solution is a USB-powered cup of Yahtzee dice. There was some debate over the color of the dice and usb-c vs usb-a. But it will be included in the next kernel release and shipped out to every user of the linux kernel with the next update.
QQ: why does this belong in the kernel at all?
Two reasons.

(1) The kernel itself needs access to good random numbers for its operation.

(2) Having a source of random number is something many applications need, and just like other services (storage, communication) random numbers a good thing to provide.

As the article shows, generating good random numbers generated based on physical entropy is a complex process. Not providing this as a service to applications would probably lead to many applications having bad random numbers. Just like we don't expect all applications to implement their own version of TCP.

Note that applications may use PRNGs from a library, for example Clib. But unless you want just pseudo randomness you somehow need to get entropy/noise from the physical machine. And the service presented to the application (for example via /dev/random) provides that.

Though of course, this could be in a userland library too. Just reading entropy from HW (exposed by the kernel). But the kernel still needs access to random number it can control and trust.
I wonder why they just didn't take a cue from OpenBSD's arc4random solution years ago, instead of this drawn-out contortion.