This is a good place as any to ask, last time I didn't get any answer: has there ever been a serious Linux exploit from manipulating/predicting bad PRNG? Apart from the Debian SSH key generation fiasco from years ago, of course.
Having a good entropy source makes mathematical sense, and you want something a bit more "random" than a dice roll, but I wonder at which point it becomes security theatre.
Of all the possible avenues for exploiting a modern OS might have, I figure kernel PRNG prediction to be very, very far down the list of things to try.
It’s both hard to attack but also a hugely audited system with a lot of attention paid.
That being said, [1] from 2012. The challenge with security is that structural weaknesses can take a long time to be discovered but once they are it’s catastrophic. Modern Linux finally switched to CSPRNG and proper construction and relies less on the numerology of entropy estimation it had been using (ie real security instead of theater). RDRAND has also been there for a long time on the x86 side which is useful because even if it’s insecure it gets mixed with other entropy sources like instruction execution time and scheduling jitter to protect standalone servers and iot devices.
Of course you hit the nail on the head in terms of the challenge of distinguishing security theater because you won’t know if the hardening is useful until there’s a problem, but there’s enough knowledgeable people on it that it’s less security theater than it might seem if you know what’s going on.
30 years ago BSDs already had non-blocking /dev/random (there was no difference to /dev/urandom). OpenBSD especially wouldn’t have shipped something known insecure. Blocking random probably caused more issues (DOS, random hangs, etc.) than a no blocking CSPRNG would have.
Linux did /dev/random first, so naturally it had the oldest design for a few years, without the security expert scrutiny and experience, which the other OSes had for their implementations.
OpenBSD didn't exist yet when /dev/random and /dev/urandom were created for Linux.
Easy to dunk on Linux, but it would be misremembering history.
OpenBSD was using an insecure PRNG before 2014 when they upgraded to ChaCha20 to replace RC4. Yarrow came about in 1999 with Fortuna following in 2003 as a more secure version. Apple switched to Fortuna in 2020 while Linux switched to ChaCha20 in 2016.
Windows is possibly in the strongest position using SHA-1 prior to Vista but the specific details are largely unknown. There were known weaknesses found in Windows 2000 which used RC4 (the same thing OpenBSD was using until 2014). They migrated to AES-CTR-DRBG at least from 2019.
So 30 years ago, that's 1996 and everyone was basically some form of insecure. 20 years ago, we're in the early 2000s and probably FreeBSD was the first to start trying to secure but their implementation was quite weak (Yarrow was a good step but it was weak). It took up until about the mid 2010s for everyone to migrate and Linux was not the first nor the last.
The strongest I'll say is that Theodore Ts'o's objections to Yarrow have not stood the test of time (Yarrow itself was weak, but the argument against CSPRNG in favor of entropy numerology was incorrect). Linux similarly has made some troubling statements when it comes to security / cryptography. I think those cultural things are the things that give a certain impression even though technically Linux does seem to have ultimately navigated to a decent position overall.
/dev/[u]random is actually a CSPRNG. it uses a cryptographic hash function to mix in every drop of randomness accessible to the kernel. predicting it without compromising the kernel entails predicting all the randomness that went into it, past a certain point you are better off bruteforcing the internal state directly and that's intractable.
the greatest danger is right after boot where it's possible the kernel didn't have enough randomness to mix in yet. not as much of an issue on modern systems.
You can analyze it much like you'd analyze a password. If you construct a password from four words taken from a list of 1024 words, that's 40 bits of entropy. On average, a brute force attacker would have to try 2^39 (half the possibilities) random passwords before cracking your account. You can then apply that number to the time/money required for one attempt, and see if it's sufficiently secure for your tastes. If the answer comes back as 10 minutes, maybe it's not good enough. If it's 10 quadrillion years, you're probably OK.
If you have bad PRNG, you should be able to quantify it in terms of bits. The Debian bug resulted in 15 bits of randomness, since all inputs to the PRNG were erased except for the pid, which was 15 bits at the time.
Another real-world example, albeit not Linux. I once worked on a program that had the option of encrypting save files. The encryption was custom (not done by me!) and had a bit of an issue. The encryption itself was not bad, but the save file's master encryption key was generated from the current time. This reduced the number of bits of randomness to well within brute-force range, especially if you could guess at roughly when the key was created. This was convenient for users who had lost their passwords, but somewhat less convenient for users who wanted to actually protect their data.
An attacker isn't going to spontaneously try breaking your PRNG, but if you do have an issue, it's a real concern. It'll be far down the list of things to try just because any modern system will hopefully have very good randomness.
Some of the paranoia has been proven correct. For example both Intel and AMD had RDRAND bugs so not relying on it as sole source was the correct choice.
Assuming you are talking about real physical dice and not an imaginary function that generates perfectly random die rolls.
They are actually pretty poor random number generators. For starters, dice are chaotic, not random, the outcome is based entirely on initial conditions. For humans rolling dice, the space of initial conditions can become surprisingly constrained, especially if the human wants to achieve specific outcomes.
Half the entropy is trying to figure out which pieces of this article's text are supposed to be the silly falsehoods being corrected, and which pieces are just the second or third paragraph of a preceding 'Fact'. Deadpool is easier to follow.
Hey, someone submitted my old article. On my birthday!
Oh, people hate it… and even someone I definitely look up to.
You‘re absolutely right, though, I don‘t remember it being that bad, and probably I just read over it when resurrecting the article, because I‘m so familiar with every word.
I‘ll slap some <hr> tags on it when I‘m back home from my holiday.
I saw a note from an earlier year's discussion saying the css has been changed over the years. Perhaps it was easier then to discern fact or myth, truth or fiction.
Cryptographically secure random number generators are equivalent to encryption itself. If you could predict anything about the plain text by analysis of the cipher text the algorithm is compromised/broken and useless. That's the whole point! Saying that /dev/random has "exhausted entropy" is as useful as saying "the fleep didn't florp the gorpobittin!". Completely useless words strung together without any meaning.
A CSPRNG is just an algorithm that uses some entropy as a key and feeds back on itself to generate a stream of random bytes. It is a way of expanding a small bit of entropy into a much larger sequence of random values.
From that you can derive the underlying objection here: estimating entropy, blocking /dev/random, and all the other noise is equivalent to saying "cryptography doesn't work". It is both wrong and pointless.
The only place it matters is at boot when there is no hardware source of randomness _which excludes pretty much all PCs which have hardware generators_. You need a true random key to start the CSPRNG but that's it. If you don't have a hardware unit you use time of arrival of the next network packet. Or the frequency of keystrokes on the keyboard.
Now you might ask: why bother seeing the entropy pool at all? The answer is Perfect Forward Secrecy. By mixing in new randomness you are effectively slowly swapping out the key used for the encrypted stream. Thus even if someone is able to compromise something based on guessing the random number sequence your CSPRNG generated their guesses will get more and more wrong as new entropy enters the pool eventually becoming useless. This is a defense-in-depth policy though, not a practical attack mechanism.
On linux it is unfortunate that /dev/urandom has the property of silently vending non-random bytes on hardware without an RNG just after boot and that /dev/random was designed to block when the magical fairies say so but of the two failure modes /dev/urandom is the least bad because practically most hardware (even embedded hardware these days) simply can't encounter its failure mode.
> A CSPRNG is just an algorithm that uses some entropy as a key and feeds back on itself to generate a stream of random bytes.
You say yourself that there is a distinction. CSPRNGs can generate unpredictable ("random") bytes, given entropy. They cannot, however, produce entropy. They are entirely deterministic.
Entropy gas to be gathered. It cannot be generated. Therefore, there is a meaningful distinction between the input entropy and output random bits.
I do agree that once the PRNG is sufficiently initialized, it does not make sense to say that “entropy ran out”, however. Given a 256 bit key, modern PRNGs can generate unpredictable bit streams of sizes that will practically never be exhausted.
Back in the dinosaur days (around 2005) I was working on a PHP CMS used by a big registrar. Occasionally page loads would block for seconds. It appeared randomly (natch) and was relatively unreproducible.
I couldn’t find any good way to debug it and a friend suggested GDB. I had never thought of using such a low level debugger on a scripting language, but what choice did I have? Fired it up, found a blocked process and sure enough it was blocked on reads to /dev/random.
I leaned two things that day: the decision to make and keep /dev/random blocking was dumb and GDB (or lldb, or valgrind, etc.) is useful for debugging just about anything.
Yeah I also have been debugging python scripts that way. Honestly it was because I haven't found another way to attach a debugger to a running python process.
I woke up around 4am, read this, and wondered if I was still in a dream state given the meandering nature of it.
Were the man page musings written in response to the (alleged, but... uh... NSA) kleptographic backdoor in Dual_EC_DRBG? It requires multiple successive outputs to compromise and derive internal PRNG state, if memory serves.
In that one construction, /dev/random blocking on seeding would have a mild state-hiding advantage over /dev/urandom, I imagine... but, sheesh. Nobody use that generator.
Of course, when searching for man urandom you still found the old versions at the top of the search results for years and years afterwards. And the German Wikipedia page will probably never change.
> Note from 2024: This article was published on March 16th, 2014. It is still correct in its discussion of entropy and randomness, but the Linux kernel random number generator has been reworked several times since then and does not look like this anymore. Good news: the separation between /dev/urandom and /dev/random is practically gone.
My understanding is that on modern Linux system:
At early boot phases, /dev/random can still block, because not enough entropy has been seeded yet. /dev/urandom will not block, but the random data might be of poor quality and not suitable for crypto purposes. This happens very early in the boot, so probably it's not even possible to run user stuff at this time. At least on my laptop, the message "random: crng init done" gets logged almost instantly after boot and long before even initrd starts. Might be different for exotic platforms, I guess.
Once there was enough entropy seeded, both /dev/random and /dev/urandom works identically, they don't block and they return high quality random data. So for most userspace purposes, these files can be used interchangeably, one is not better than another.
It started looking a whole lot like OpenBSD’s random number system. Private entropy pool from good system entropy seeds a ChaCha20 stream with random reseeds for forward secrecy in case of compromise. I think Linux is even more paranoid in the early boot environment where even in the presence of a seed file it prefers to get system entropy mixed in before confidently saying it can do crypto activities.
> Might be different for exotic platforms, I guess.
Short-lived isolated VMs (like might be used for CI) are one place where entropy can be a problem. The relevant definition of “platform” here is less about the CPU architecture and more about the environment.
Should, yes. Will, perhaps, but better be aware of the potential problem and check.
Just yesterday I encountered people complaining about a VM not connecting to a cloud service when they neglected to put their DNS server’s address in the config for the DHCP server used by that particular host. And a dysfunctional RNG is much more difficult to detect.
I remember Jason Donenfeld tried to get rid of the boot time entropy hole in urandom by using cpu jitter to get fast entropy (what he calls Linus Jitter dance) but had to roll back because it broke things when run on an Amiga.
Original discussion from 2014:
* https://news.ycombinator.com/item?id=7359992
Also:
2020: https://news.ycombinator.com/item?id=22683627
2018: https://news.ycombinator.com/item?id=17779657
2017: https://news.ycombinator.com/item?id=13332741
2015: https://news.ycombinator.com/item?id=10149019
This is a good place as any to ask, last time I didn't get any answer: has there ever been a serious Linux exploit from manipulating/predicting bad PRNG? Apart from the Debian SSH key generation fiasco from years ago, of course.
Having a good entropy source makes mathematical sense, and you want something a bit more "random" than a dice roll, but I wonder at which point it becomes security theatre.
Of all the possible avenues for exploiting a modern OS might have, I figure kernel PRNG prediction to be very, very far down the list of things to try.
It’s both hard to attack but also a hugely audited system with a lot of attention paid.
That being said, [1] from 2012. The challenge with security is that structural weaknesses can take a long time to be discovered but once they are it’s catastrophic. Modern Linux finally switched to CSPRNG and proper construction and relies less on the numerology of entropy estimation it had been using (ie real security instead of theater). RDRAND has also been there for a long time on the x86 side which is useful because even if it’s insecure it gets mixed with other entropy sources like instruction execution time and scheduling jitter to protect standalone servers and iot devices.
Of course you hit the nail on the head in terms of the challenge of distinguishing security theater because you won’t know if the hardening is useful until there’s a problem, but there’s enough knowledgeable people on it that it’s less security theater than it might seem if you know what’s going on.
[1] https://www.usenix.org/system/files/conference/usenixsecurit...
30 years ago BSDs already had non-blocking /dev/random (there was no difference to /dev/urandom). OpenBSD especially wouldn’t have shipped something known insecure. Blocking random probably caused more issues (DOS, random hangs, etc.) than a no blocking CSPRNG would have.
Linux did /dev/random first, so naturally it had the oldest design for a few years, without the security expert scrutiny and experience, which the other OSes had for their implementations.
OpenBSD didn't exist yet when /dev/random and /dev/urandom were created for Linux.
Easy to dunk on Linux, but it would be misremembering history.
OpenBSD was using an insecure PRNG before 2014 when they upgraded to ChaCha20 to replace RC4. Yarrow came about in 1999 with Fortuna following in 2003 as a more secure version. Apple switched to Fortuna in 2020 while Linux switched to ChaCha20 in 2016.
Windows is possibly in the strongest position using SHA-1 prior to Vista but the specific details are largely unknown. There were known weaknesses found in Windows 2000 which used RC4 (the same thing OpenBSD was using until 2014). They migrated to AES-CTR-DRBG at least from 2019.
So 30 years ago, that's 1996 and everyone was basically some form of insecure. 20 years ago, we're in the early 2000s and probably FreeBSD was the first to start trying to secure but their implementation was quite weak (Yarrow was a good step but it was weak). It took up until about the mid 2010s for everyone to migrate and Linux was not the first nor the last.
The strongest I'll say is that Theodore Ts'o's objections to Yarrow have not stood the test of time (Yarrow itself was weak, but the argument against CSPRNG in favor of entropy numerology was incorrect). Linux similarly has made some troubling statements when it comes to security / cryptography. I think those cultural things are the things that give a certain impression even though technically Linux does seem to have ultimately navigated to a decent position overall.
I think Apple uses a NIST compliant DRBG now, but their manuals are wrong.
/dev/[u]random is actually a CSPRNG. it uses a cryptographic hash function to mix in every drop of randomness accessible to the kernel. predicting it without compromising the kernel entails predicting all the randomness that went into it, past a certain point you are better off bruteforcing the internal state directly and that's intractable.
the greatest danger is right after boot where it's possible the kernel didn't have enough randomness to mix in yet. not as much of an issue on modern systems.
which is why periodically the kernel updates an entropy file on disk which is used on reboot as extra seed
cloning/snapshotting VMs might have entropy problems, but a proper VM manager will also inject entropy into the VM on boot
I think this one is among the most significant findings: https://factorable.net/
I also believe there were some android ASLR issues based on the same weakness (i.e., low early boot-time entropy).
But this is all quite old, and there've been massive improvements. Basically, "don't use a very old linux kernel" is your mitigation for these issues.
You can analyze it much like you'd analyze a password. If you construct a password from four words taken from a list of 1024 words, that's 40 bits of entropy. On average, a brute force attacker would have to try 2^39 (half the possibilities) random passwords before cracking your account. You can then apply that number to the time/money required for one attempt, and see if it's sufficiently secure for your tastes. If the answer comes back as 10 minutes, maybe it's not good enough. If it's 10 quadrillion years, you're probably OK.
If you have bad PRNG, you should be able to quantify it in terms of bits. The Debian bug resulted in 15 bits of randomness, since all inputs to the PRNG were erased except for the pid, which was 15 bits at the time.
Another real-world example, albeit not Linux. I once worked on a program that had the option of encrypting save files. The encryption was custom (not done by me!) and had a bit of an issue. The encryption itself was not bad, but the save file's master encryption key was generated from the current time. This reduced the number of bits of randomness to well within brute-force range, especially if you could guess at roughly when the key was created. This was convenient for users who had lost their passwords, but somewhat less convenient for users who wanted to actually protect their data.
An attacker isn't going to spontaneously try breaking your PRNG, but if you do have an issue, it's a real concern. It'll be far down the list of things to try just because any modern system will hopefully have very good randomness.
Some of the paranoia has been proven correct. For example both Intel and AMD had RDRAND bugs so not relying on it as sole source was the correct choice.
There was a bitcoin key generation flaw on android, and AFAIK people lost money.
I don't think anything a computer can do is more random than a dice roll.
Assuming you are talking about real physical dice and not an imaginary function that generates perfectly random die rolls.
They are actually pretty poor random number generators. For starters, dice are chaotic, not random, the outcome is based entirely on initial conditions. For humans rolling dice, the space of initial conditions can become surprisingly constrained, especially if the human wants to achieve specific outcomes.
> For starters, dice are chaotic, not random
Unless you're doing something at the quantum level (maybe) this is true of every random number generator.
Half the entropy is trying to figure out which pieces of this article's text are supposed to be the silly falsehoods being corrected, and which pieces are just the second or third paragraph of a preceding 'Fact'. Deadpool is easier to follow.
Hey, someone submitted my old article. On my birthday!
Oh, people hate it… and even someone I definitely look up to.
You‘re absolutely right, though, I don‘t remember it being that bad, and probably I just read over it when resurrecting the article, because I‘m so familiar with every word.
I‘ll slap some <hr> tags on it when I‘m back home from my holiday.
If it helps, it used to look like this: https://web.archive.org/web/20140309183752/http://www.2uo.de...
Definitely a lot more readable! Something must have changed in the meantime.
It looks like some links have gone too, like the one in the sentence "how does /dev/random know how much entropy there is available to give out?"
Way better.
I hate it when updates, migrations or cosmic radiation break fidelity.
Label the myths rather than leaving them as plain statements.
Yes. It should look like:
Most importantly -- Happy birthday!!!
Happy birthday!
This'll all wait for later, hope you're enjoying a nice mai tai on your holiday.
I saw a note from an earlier year's discussion saying the css has been changed over the years. Perhaps it was easier then to discern fact or myth, truth or fiction.
I pulled up a random version from 2014, and it's more readable: https://web.archive.org/web/20141023082929/https://www.2uo.d...
haha, this is so much better
> Deadpool is easier to follow.
Oh wow.
I want to know as much as you're willing to write about how Deadpool is hard to follow. (A shot-for-shot commentary track would be ideal.)
glad i’m not the only one. i’m more or less baffled reading that.
the article is why you need to tell your LLM to 'make noistakes'
Cryptographically secure random number generators are equivalent to encryption itself. If you could predict anything about the plain text by analysis of the cipher text the algorithm is compromised/broken and useless. That's the whole point! Saying that /dev/random has "exhausted entropy" is as useful as saying "the fleep didn't florp the gorpobittin!". Completely useless words strung together without any meaning.
A CSPRNG is just an algorithm that uses some entropy as a key and feeds back on itself to generate a stream of random bytes. It is a way of expanding a small bit of entropy into a much larger sequence of random values.
From that you can derive the underlying objection here: estimating entropy, blocking /dev/random, and all the other noise is equivalent to saying "cryptography doesn't work". It is both wrong and pointless.
The only place it matters is at boot when there is no hardware source of randomness _which excludes pretty much all PCs which have hardware generators_. You need a true random key to start the CSPRNG but that's it. If you don't have a hardware unit you use time of arrival of the next network packet. Or the frequency of keystrokes on the keyboard.
Now you might ask: why bother seeing the entropy pool at all? The answer is Perfect Forward Secrecy. By mixing in new randomness you are effectively slowly swapping out the key used for the encrypted stream. Thus even if someone is able to compromise something based on guessing the random number sequence your CSPRNG generated their guesses will get more and more wrong as new entropy enters the pool eventually becoming useless. This is a defense-in-depth policy though, not a practical attack mechanism.
On linux it is unfortunate that /dev/urandom has the property of silently vending non-random bytes on hardware without an RNG just after boot and that /dev/random was designed to block when the magical fairies say so but of the two failure modes /dev/urandom is the least bad because practically most hardware (even embedded hardware these days) simply can't encounter its failure mode.
> A CSPRNG is just an algorithm that uses some entropy as a key and feeds back on itself to generate a stream of random bytes.
You say yourself that there is a distinction. CSPRNGs can generate unpredictable ("random") bytes, given entropy. They cannot, however, produce entropy. They are entirely deterministic.
Entropy gas to be gathered. It cannot be generated. Therefore, there is a meaningful distinction between the input entropy and output random bits.
I do agree that once the PRNG is sufficiently initialized, it does not make sense to say that “entropy ran out”, however. Given a 256 bit key, modern PRNGs can generate unpredictable bit streams of sizes that will practically never be exhausted.
Back in the dinosaur days (around 2005) I was working on a PHP CMS used by a big registrar. Occasionally page loads would block for seconds. It appeared randomly (natch) and was relatively unreproducible.
I couldn’t find any good way to debug it and a friend suggested GDB. I had never thought of using such a low level debugger on a scripting language, but what choice did I have? Fired it up, found a blocked process and sure enough it was blocked on reads to /dev/random.
I leaned two things that day: the decision to make and keep /dev/random blocking was dumb and GDB (or lldb, or valgrind, etc.) is useful for debugging just about anything.
Yeah I also have been debugging python scripts that way. Honestly it was because I haven't found another way to attach a debugger to a running python process.
for something like this strace is a really good fit
I probably did start with strace, now that I think about it. It’s been a long time.
That was hard to tell where the additional commentary on the fact ended and the next myth started.
The CSS has broken some time in the last 12 years, people have posted archive links that make it much clearer [1].
The author is on holiday (and enjoying their birthday!) and will get to it when they're back home.
[1] https://web.archive.org/web/20140309183752/http://www.2uo.de...
I woke up around 4am, read this, and wondered if I was still in a dream state given the meandering nature of it.
Were the man page musings written in response to the (alleged, but... uh... NSA) kleptographic backdoor in Dual_EC_DRBG? It requires multiple successive outputs to compromise and derive internal PRNG state, if memory serves.
In that one construction, /dev/random blocking on seeding would have a mild state-hiding advantage over /dev/urandom, I imagine... but, sheesh. Nobody use that generator.
There's a talk by Filippo that explains this nicely https://www.youtube.com/watch?v=0DV8WnqhH2Y
Twelve years later, if there's still so much misconception about /dev/(u)random, has the man page been fixed?
Edit: can't count.
Yes. It’s mentioned at https://www.thomas-huehn.com/myths-about-urandom-revisited/
Of course, when searching for man urandom you still found the old versions at the top of the search results for years and years afterwards. And the German Wikipedia page will probably never change.
[flagged]
(2014)
Ah, I wonder what's change since then.
Here's quote from the article:
> Note from 2024: This article was published on March 16th, 2014. It is still correct in its discussion of entropy and randomness, but the Linux kernel random number generator has been reworked several times since then and does not look like this anymore. Good news: the separation between /dev/urandom and /dev/random is practically gone.
My understanding is that on modern Linux system:
At early boot phases, /dev/random can still block, because not enough entropy has been seeded yet. /dev/urandom will not block, but the random data might be of poor quality and not suitable for crypto purposes. This happens very early in the boot, so probably it's not even possible to run user stuff at this time. At least on my laptop, the message "random: crng init done" gets logged almost instantly after boot and long before even initrd starts. Might be different for exotic platforms, I guess.
Once there was enough entropy seeded, both /dev/random and /dev/urandom works identically, they don't block and they return high quality random data. So for most userspace purposes, these files can be used interchangeably, one is not better than another.
It started looking a whole lot like OpenBSD’s random number system. Private entropy pool from good system entropy seeds a ChaCha20 stream with random reseeds for forward secrecy in case of compromise. I think Linux is even more paranoid in the early boot environment where even in the presence of a seed file it prefers to get system entropy mixed in before confidently saying it can do crypto activities.
> Might be different for exotic platforms, I guess.
Short-lived isolated VMs (like might be used for CI) are one place where entropy can be a problem. The relevant definition of “platform” here is less about the CPU architecture and more about the environment.
VMs should have VirtIO RNG set up so there is a high quality entropy source at boot time, provided by the host system.
Should, yes. Will, perhaps, but better be aware of the potential problem and check.
Just yesterday I encountered people complaining about a VM not connecting to a cloud service when they neglected to put their DNS server’s address in the config for the DHCP server used by that particular host. And a dysfunctional RNG is much more difficult to detect.
I remember Jason Donenfeld tried to get rid of the boot time entropy hole in urandom by using cpu jitter to get fast entropy (what he calls Linus Jitter dance) but had to roll back because it broke things when run on an Amiga.