New and improved Linux Random Number Generator ready for testing
portswigger.net
portswigger.net
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.
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.
https://lwn.net/Articles/808575/ "Removing the Linux /dev/random blocking pool"
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
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".
https://lkml.org/lkml/2016/4/21/839
but there has been a notable development in the subsystem this year, finally `/dev/random` blocks only before initialization, and never after!
https://lore.kernel.org/lkml/20200131204924.GA455123@mit.edu...
https://twitter.com/matthew_d_green/status/14334701097425182...
Still better than the current implementation.
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.
https://www.phoronix.com/scan.php?page=news_item&px=Linux-5....
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:
> 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.
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 API: https://fuchsia.dev/fuchsia-src/reference/syscalls/cprng_dra...
”Terminates the calling process”? That sounds different and interesting, do you know more about this aspect of Fuchsia?
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.
https://glacierprotocol.org/docs/deposit/generate-cold-stora...
I do a lot of entropy research, and was annoyed I had to roll my own implementation for a no-photon camera entropy source.
* https://en.wikipedia.org/wiki/Diceware
Useful site:
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
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).
Also, it would be reasonable for the RNG to notice some source is returning input of no value (straight zeroes) and reject it.
Now if your 9 bad sources are 100% predictable, then yes, there's no point in adding them.
Can you 'lie' to the operating system about these sources of entropy in order to control the random number generation?
* 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();
}
void foo(bool a) __attribute__((latent_entropy))
{
if (a)
{
latent_entropy OP NUMBER;
bar();
}
else
{
latent_entropy OP NUMBER;
baz();
}
}
Many kernel procedures handling interrupts have the latent_entropy attribute.
more information at https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
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.
> 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?
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.
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.
https://csrc.nist.gov/CSRC/media/Projects/Random-Bit-Generat...
Maybe? I'm not familiar, summarily discussed it with research director.
(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.
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 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).