3 ms·

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

by sph 6mo ago

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.

hannob 6mo ago
I think this one is among the most significant findings: https://factorable.net/ 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.
vlovich123 6mo 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. [1] https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf https://www.usenix.org/system/files/conference/usenixsecurit...
- jonhohle 6mo ago
  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 6mo 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 6mo 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.
      - 6mo ago
wat10000 6mo 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.
GoblinSlayer 6mo ago
There was a bitcoin key generation flaw on android, and AFAIK people lost money.
teravor 6mo 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 6mo 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
the8472 6mo 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.
singpolyma3 6mo ago
I don't think anything a computer can do is more random than a dice roll.
- MadnessASAP 6mo 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 6mo 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.

by sph 6mo ago

hannob 6mo ago

I think this one is among the most significant findings: https://factorable.net/ 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.

vlovich123 6mo 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. [1] https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf https://www.usenix.org/system/files/conference/usenixsecurit...

jonhohle 6mo ago
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 6mo 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 6mo 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.
    - 6mo ago

wat10000 6mo 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.

GoblinSlayer 6mo ago

There was a bitcoin key generation flaw on android, and AFAIK people lost money.

teravor 6mo 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 6mo 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

the8472 6mo 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.

singpolyma3 6mo ago

I don't think anything a computer can do is more random than a dice roll.

MadnessASAP 6mo 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 6mo 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.