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.
vlovich123 12 hours ago [-]
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.
jlokier 9 hours ago [-]
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.
vlovich123 3 hours ago [-]
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.
teravor 9 hours ago [-]
/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.
dist-epoch 7 hours ago [-]
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 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.
the8472 8 hours ago [-]
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.
GoblinSlayer 10 hours ago [-]
There was a bitcoin key generation flaw on android, and AFAIK people lost money.
singpolyma3 7 hours ago [-]
I don't think anything a computer can do is more random than a dice roll.
MadnessASAP 6 hours ago [-]
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.
singpolyma3 5 hours ago [-]
> 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.
wat10000 10 hours ago [-]
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.
xiphmont 13 hours ago [-]
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.
Tomte 12 hours ago [-]
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.
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?"
rkagerer 7 hours ago [-]
Way better.
I hate it when updates, migrations or cosmic radiation break fidelity.
gblargg 11 hours ago [-]
Label the myths rather than leaving them as plain statements.
wang_li 10 hours ago [-]
Yes. It should look like:
Myth: the moon is made of green cheese.
Fact: the moon is made of yellow and green cheese.
flyinprogrammer 11 hours ago [-]
Most importantly -- Happy birthday!!!
syncsynchalt 9 hours ago [-]
Happy birthday!
This'll all wait for later, hope you're enjoying a nice mai tai on your holiday.
roter 13 hours ago [-]
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 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.)
notnmeyer 13 hours ago [-]
glad i’m not the only one. i’m more or less baffled reading that.
cyanydeez 11 hours ago [-]
the article is why you need to tell your LLM to 'make noistakes'
jonhohle 11 hours ago [-]
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.
1718627440 7 hours ago [-]
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.
hnav 8 hours ago [-]
for something like this strace is a really good fit
xenadu02 5 hours ago [-]
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.
iamtedd 13 hours ago [-]
That was hard to tell where the additional commentary on the fact ended and the next myth started.
syncsynchalt 9 hours ago [-]
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.
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.
iamtedd 12 hours ago [-]
Twelve years later, if there's still so much misconception about /dev/(u)random, has the man page been fixed?
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.
EMPTYCONTOUR 13 hours ago [-]
[flagged]
NooneAtAll3 13 hours ago [-]
(2014)
ape4 13 hours ago [-]
Ah, I wonder what's change since then.
vbezhenar 13 hours ago [-]
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.
aomix 12 hours ago [-]
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.
mananaysiempre 13 hours ago [-]
> 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.
ChrisSD 13 hours ago [-]
VMs should have VirtIO RNG set up so there is a high quality entropy source at boot time, provided by the host system.
mananaysiempre 13 hours ago [-]
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.
* 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
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.
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...
OpenBSD didn't exist yet when /dev/random and /dev/urandom were created for Linux.
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.
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.
cloning/snapshotting VMs might have entropy problems, but a proper VM manager will also inject entropy into the VM on boot
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.
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.
Unless you're doing something at the quantum level (maybe) this is true of every random number generator.
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.
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.
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?"
I hate it when updates, migrations or cosmic radiation break fidelity.
This'll all wait for later, hope you're enjoying a nice mai tai on your holiday.
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.)
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.
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.
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...
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.
Edit: can't count.
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.
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.
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.