19 ms·

random blocking pool

265 points by lukastyrychtr 7y ago

saagarjha 7y ago
Am I correct in my understanding that /dev/random will not block anymore and behave similarly to /dev/urandom after it has been initialized? Or is there still some inherent difference between the two?
- hannob 7y ago
  The "after it has been initialized" is the inherent difference.
Erlich_Bachman 7y ago
Summarizing the article, `cat /dev/random` will still work but will never block, possibly returning random data based on less entropy than before. They claim that in the modern situation there is already enough entropy in it even for secure key generation. There seemingly will still exist a programmatic way to get a random stream based on predictable amount of entropy, but not through reading this filesystem node.
- gioele 7y ago
  > Summarizing the article, `cat /dev/random` will still work but will never block `cat /dev/random` may still block, but only once per reboot. It may block if it is called so early that not enough entropy has been gathered yet. Once there enough entropy has been gathered it will never block again.
  - simias 7y ago
    As mentioned by the article that's already the default behaviour of getrandom() and the BSDs have symlinked /dev/random to /dev/urandom for a long time already. I think this is a change for the best, in particular this bit sounds completely true to my ears: > Theodore Y. Ts'o, who is the maintainer of the Linux random-number subsystem, appears to have changed his mind along the way about the need for a blocking pool. He said that removing that pool would effectively get rid of the idea that Linux has a true random-number generator (TRNG), which "is not insane; this is what the *BSD's have always done". He, too, is concerned that providing a TRNG mechanism will just serve as an attractant for application developers. He also thinks that it is not really possible to guarantee a TRNG in the kernel, given all of the different types of hardware supported by Linux. Even making the facility only available to root will not solve the problem: Application programmers would give instructions requiring that their application be installed as root to be more secure, "because that way you can get access the _really_ good random numbers". The number of time I've had to deal with security-related software and scripts who insisted in sampling /dev/random and stalling for minutes at a time...
    - JdeBP 7y ago
      A minor note: * Only FreeBSD symbolically links, and it does it in the other direction. urandom is the symbolic link to random. * OpenBSD has four distinct character device files: random, arandom, srandom, and urandom. * NetBSD (as of 2019) has two distinct character device files: random and urandom. They have different semantics from each other. https://netbsd.gw.com/cgi-bin/man-cgi?rnd+4+NetBSD-current https://netbsd.gw.com/cgi-bin/man-cgi?rnd+4+NetBSD-current
      - aquabeagle 7y ago
        On OpenBSD: $ ls -l /dev/*random* lrwxr-xr-x 1 root wheel 7 Dec 10 15:05 /dev/random@ -> urandom crw-r--r-- 1 root wheel 45, 0 Jan 6 15:30 /dev/urandom
        JdeBP 7y ago
        That must be a recent change. $ ls -F /dev/*random* /dev/arandom /dev/random /dev/srandom /dev/urandom $
        ben_bai 7y ago
        Deleted in 2017. https://marc.info/?l=openbsd-cvs&m=151069089605712&w=2 https://marc.info/?l=openbsd-cvs&m=151069089605712&w=2 you can delete arandom and srandom Edit: better link
    - guenthert 7y ago
      And you don't think they did so for a reason? If you don't care for security (and there are good reason why one wouldn't), then you can create the link yourself on those systems (or link to /dev/zero for extra low wait times). Why does now everyone have to suffer the same? What happened to "keep policy out of the kernel"?
- ale_jrb 7y ago
  I understood it that reading from `/dev/random` will still block just after boot (i.e. before it's initialised) unless you pass the new flag `GRND_INSECURE` to `getrandom`. After it's initialised, however, it will never block because it's now just using the CRNG.
  - richardwhiuk 7y ago
    Please don't confuse `/dev/random` and `getrandom` - they are separate interfaces.
walterbell 7y ago
On the subject of TRNG, John Denker wrote a 2005 paper for using soundcard data as a source of randomness, http://www.av8n.com/turbid/ http://www.av8n.com/turbid/ > We discuss how to configure and use turbid, which is a Hardware Random Number Generator (HRNG), also called a True Random Generator (TRNG). It is suitable for a wide range of applications, from the simplest benign applications to the most demanding high-stakes adversarial applications, including cryptography and gaming. It relies on a combination of physical process and cryptological algorithms, rather than either of those separately. It harvests randomness from physical processes, and uses that randomness efficiently. The hash saturation principle is used to distill the data, so that the output is virtually 100% random for all practical purposes. This is calculated based on physical properties of the inputs, not merely estimated by looking at the statistics of the outputs. In contrast to a Pseudo-Random Generator, it has no internal state to worry about. In particular, we describe a low-cost high-performance implementation, using the computer’s audio I/O system. On randomness, http://www.av8n.com/turbid/paper/turbid.htm#sec-raw-randomness http://www.av8n.com/turbid/paper/turbid.htm#sec-raw-randomne... > Understanding turbid requires some interdisciplinary skills. It requires physics, analog electronics, and cryptography.
- hannob 7y ago
  This is one of these approaches that are for all practical purposes completely useless. There's basically only three problems generating good randomness: 1. Very early during boot you don't have a lot of good sources. 2. On very constrained devices you have limited external input. 3. Bugs in the implementation. Randomness from soundcards doesn't help with any of these. They probably aren't yet initialized at the point in time where it matters most, they don't exist for the most problematic devices and bugs are bugs, no matter what your source of randomness.
  - bigiain 7y ago
    > Randomness from soundcards doesn't help with any of these. "Randomness from soundcards" is also spectacularly unlikely to help on the cloud. Pretty sure they don't fit SoundBlaster16s to EC2 instances or Digital Ocean Droplets...
jonesdaisy 7y ago
https://genericbuddy.com/careprost-3ml-eye-drops https://genericbuddy.com/careprost-3ml-eye-drops
csours 7y ago
I was looking at Java properties the other day and I thought to myself, "We still need to set /dev/./urandom in 2019?"
- ktpsns 7y ago
  This is a valid point -- most high level programming languages provide some kind of function to provide random numbers in a given interval, such as [0,1]. See also https://stackoverflow.com/questions/2572366/how-to-use-dev-random-or-urandom-in-c https://stackoverflow.com/questions/2572366/how-to-use-dev-r... This is even true for shell scripting, see for instance http://www.tldp.org/LDP/abs/html/randomvar.html http://www.tldp.org/LDP/abs/html/randomvar.html
quotemstr 7y ago
Not blocking under insufficient entropy does not suddenly make that entropy available. Punting entropy collection to userspace doesn't magically allow for DoS-free random number generation --- it just transforms, silently, a condition of insufficient entropy into a subtle security vulnerability. It feels like a form of reality denial, a bit like overcommit. The more time goes by, the more I wish there were a unixlike built on robustness, determinacy, and strict resource accounting.
- Hendrikto 7y ago
  > Not blocking under insufficient entropy does not suddenly make that entropy available. That’s why it is still blocking until it has been sufficiently initialized. After it has gathered sufficient entropy, the pool’s entropy is not exhausted by reading from it. /dev/random assumes that reading 64 bits from it will decrease the entropy in its pool by 64 bits, which is nonsense. Linux’s PRNG is based on cryptographically strong primitives, and reading output from /dev/random does not expose its internal state. Your pointless rant just indicates that you do not really understand what’s going on.
  - cesarb 7y ago
    > /dev/random assumes that reading 64 bits from it will decrease the entropy in its pool by 64 bits, which is nonsense. It's not complete nonsense. Suppose for explanation purposes that you had a pool with only 256 bits (2^256 possible states), and you read 64 bits from it. Of these 2^256 possible states, most would not have output that exact 64-bit value you just read; on average only 2^192 of the possible states would have resulted in that output value. Therefore, once you know that 64-bit value, the pool now has only 192 bits of entropy (2^192 possible states). Read three more 64-bit values, and on average only one of the 2^256 originally possible states could have resulted in these four 64-bit values; since there's only one possible state, the pool's entropy is zero. However, like you said "Linux’s PRNG is based on cryptographically strong primitives": the only known way to find which of the 2^256 possible states could have resulted on these four 64-bit values would be to try all of them. Which is simply not viable, even with all the computing power in the world. That is, once the number of possible states (the pool's entropy) gets above a threshold, even if you later exhaust all the theoretical entropy from it, there's still no way to know the pool's state.
CiPHPerCoder 7y ago
Making /dev/random behave like getrandom(2) will finally put to rest one of the most frustrating arguments in the public understanding of cryptography. Please do it.
- jdormit 7y ago
  What argument are you referring to?
  - jacobush 7y ago
    That you must never use urandom for serious stuff?
  - geofft 7y ago
    The question of whether "true random numbers" as defined by this weird government standard exist. More fundamentally, an important conceptual part of crypto is that you can use a random key of a very small, fixed size, like 16 bytes, to generate an infinite amount of output, such that knowing any part of the output doesn't help you guess at any other part of the output nor the input key. If true, this is an amazingly powerful property because you can securely exchange (or derive) a short key once and then you can send as much encrypted data back and forth as you want. If you needed to re-seed the input with as many bits as you take from the output, disk encryption wouldn't be sound (you'd need a key or passphrase as long as your disk), SSL would be way more expensive (and couldn't be forward-secure) if it even worked at all, Kerberos wouldn't work, Signal wouldn't work, etc. The claim of /dev/random and this wacky government standard is that in fact disk encryption, SSL, etc. are flawed designs, good enough for securing a single communication but suboptimal because they encrypt more bits of data than the size of the random key, and so when generating random keys, you really ought to use "true random numbers" so that breaking one SSL connection doesn't help you break another. Whether it's a pen-and-paper cipher like Vigenère or a fancy modern algorithm like AES, anything with a fixed-size key can be cryptanalyzed and you shouldn't provide too much output with it, for your secure stuff you must use a one-time pad. The claim of the cryptography community is that, no, in fact, there's nothing flawed about this approach and stretching fixed-size keys is the very miracle of cryptography. We know how to do it securely for any worthwhile definition of "securely" (including definitions where quantum computers are relevant) and we should, because key-based encryption has changed our world for the better.
brohee 7y ago
That this happens right after Thomas Pornin ridiculing the blocking pool (https://research.nccgroup.com/2019/12/19/on-linuxs-random-number-generation/ https://research.nccgroup.com/2019/12/19/on-linuxs-random-nu..., HN discussion https://news.ycombinator.com/item?id=21843081 https://news.ycombinator.com/item?id=21843081) is obviously purely coincidental, right? Especially as it was read and commented upon by Theodore Tso that at last changed his mind...
- dfc 7y ago
  It's version three of this patch.
- ATsch 7y ago
  Many people have been ridiculing entropy tracking as pointless pseudeo-security vodoo for a very long time. https://media.ccc.de/v/32c3-7441-the_plain_simple_reality_of_entropy https://media.ccc.de/v/32c3-7441-the_plain_simple_reality_of... This talk from 2015 springs to mind to me as the previous widely discussed one. But the ncc article might of course have been the straw that healed the camels back.
  - tytso 7y ago
    There was a time when some people thought that it was just fine to use MD5 and SHA1. Yarrow-160, a random number generator devised by Kelsey, Schineier, and Ferguson, used SHA1. Entropy tracking was used in the original versions of PGP because there were those people who had a very healthy (for that time) lack of confidence in "strong cryptographic algorithms" actually being strong. As PBS Space Time once said, discussing Pilot Wave Theory and why it's considered unorthodox when compared to the Many Worlds interpretation of Quantuum Theory, "Orthrodoxy == Radicalism plus Time". There was a time when the Many Worlds interpretation was considered out there. Similarly, there was a time when not trusting crypto algorithms as being Forever Strong was normal, and designing a network protocol like Wireguard without algorithm agility would have been considered highly radical. Today, trusting "strong cryptographic primitives" is considered an axiom. But remember that an axiom is something that you assume to be true and use as the basis of further proofs. Just as a Voodoo practitioner assumes that their belief system is true....
zaarn 7y ago
It's very amusing that the various kernel developers are bashing on GnuPG, going as far as calling it's behaviour a "misuse. Full stop." PGP/GPG has certainly falled out of favor.
- deleted 7y ago
  [deleted]
- grammarxcore 7y ago
  So is GnuPG bad because it reads directly from /dev/random instead of using an interface like getrandom()? I'm naive enough to not know reading directly from /dev/random is bad and would love to know more.
  - toast0 7y ago
    The getrandom() syscall is relatively new. Before it was available, you had two choices. Use a non-Linux OS with reasonable /dev/(u)random or use Linux with its Sophie's choice: /dev/random will give you something that's probably good, but will block for good and bad reasons. /dev/urandom will never block, including when the random system is totally unseeded. GnuPG could not use /dev/urandom, since there was no indication of seeding, so it had to use /dev/random which blocks until the system is seeded and also when the entropy count of nebulous value was low. Most (all) BSDs have /dev/urandom the same as /dev/random, where it blocks until seeded and then never blocks again . This behavior is available in Linux with the getrandom() syscall, but perhaps GnuPG hasn't updated to use it? Also, there was some discussion in the last few months of changing the behavior of that syscall, which thankfully didn't happen, in favor of having the kernel generate some hopeful entropy on demand in case there is a caller blocked on random with an unseeded pool.
    - grammarxcore 7y ago
      So the issue is the block? I make a blocking call and another app attempts to make a call during the block and will fail if it's not expecting to wait? Is that (one of) the problem(s)? Thanks for breaking that down for me!
latchkey 7y ago
Filed this one in 2011 and it got a lot of heated discussion... https://bugs.launchpad.net/bugs/706011 https://bugs.launchpad.net/bugs/706011
- jancsika 7y ago
  A professional response on a bug report seeks to narrow down the possible source of a bug (if any) so it may be understood, tested, and addressed properly. The first response to start such a process is taligent in response #22. A useful addition to that is #23 where Steven Ayre suggests opening that as a separate bug that focuses solely on this issue. I'm not sure what the purpose is for the other responses you received. They seem to seek to use the breadth of your issue report to widen the discussion to maximally contentious security topics.
  - JdeBP 7y ago
    That's not a fair assessment of the other responses. Steve McIntyre's in #7, for one example.
pczy 7y ago
This is the best explanation of this issue that i know of: https://www.2uo.de/myths-about-urandom https://www.2uo.de/myths-about-urandom
devit 7y ago
There are two threat models against code using RNGs: 1. The adversary has an amount of computing power that is feasible as currently foreseeable: in this case, all you need are K "truly random" bits where K=128/256/512 and can then use a strong stream cipher or equivalent to generate infinite random bits, so you only need to block at boot to get those K bits, and you can even store them on disk from the previous boot and have them passed from an external source at install time 2. The adversary has unlimited computing power: in this case, you need hardware that can generate truly random bits and can only return randomness at the rate the hardware gives you the bits Now obviously if you are using the randomness to feed an algorithm that is only strong against feasible computing power (i.e. all crypto except one-time pads) then it doesn't make sense to require resistance against unlimited computing power for the RNG. So in practice both /dev/urandom, /dev/random, getrandom(), etc. should only resist feasible computing power, and resisting against unlimited computing power should be a special interface that is never used by default except by tool that generate one-time pads or equivalent.
- xyzzyz 7y ago
  > 2. The adversary has unlimited computing power: in this case, you need hardware that can generate truly random bits and can only return randomness at the rate the hardware gives you the bits What would you need those bits for in that case? Literally the only things that comes to my mind is generating one time pads, as standard cryptography is useless in such scenario.
  - firethief 7y ago
    Game-theoretically, you want a source of random numbers when you need to make a decision your adversary can't predict. Traditionally some cultures have (accidentally?) used bird augury for this, but obviously that won't do when you're up against Unlimited Computing Power, as birds are basically deterministic.
  - deleted 7y ago
    [deleted]
- fooker 7y ago
JdeBP 7y ago
Interestingly, this follows the systemd people back in 2018 changing its seed-at-boot tool, systemd-random-seed, to write the machine-ID as the first 16 bytes of seed data to /dev/random at every seed write. * https://github.com/systemd/systemd/commit/8ba12aef045ba1a766a73f535a114781dbb763c2 https://github.com/systemd/systemd/commit/8ba12aef045ba1a766... * https://www.freedesktop.org/software/systemd/man/systemd-random-seed.service.html https://www.freedesktop.org/software/systemd/man/systemd-ran... * http://jdebp.uk./Softwares/nosh/guide/commands/machine-id.xml http://jdebp.uk./Softwares/nosh/guide/commands/machine-id.xm...
edoceo 7y ago
This looks like it explains why syslog-ng is hanging on boot? It's trying to read a random. At least, hangs until there is some random (have to just mash the keyboard a bit)
- beefhash 7y ago
  I am now somewhat curious why syslog-ng needs random bytes on boot.
- lanternslight 7y ago
  Ugh! That explains so much! I did not correlate the mashing of keys and mouse clicks with RNG.
- downerending 7y ago
  This reminds me of the (possibly apocryphal) story of old VMS (?) systems hanging if their console, which was often a printer, ran out of paper.
emilfihlman 7y ago
Changing getrandom was just idiotic and breaks god damn userspace. The man page was extremely clear in documentation in the first place.
SignalsFromBob 7y ago
Are hardware RNGs, such as the ones that plug into a USB port, of any value when the RNG in Linux is good enough for generating GPG keys? I'm wondering what the use case is for people that buy them.
commandersaki 7y ago
I don't see why this is so difficult. 1. Make a kernel config option that makes /dev/urandom block until entropy pool initialises. 2. Make a dependant kernel config option so /dev/random is /dev/urandom. There done. Everyone can have their own choice on what security they want.

265 points by lukastyrychtr 7y ago

Am I correct in my understanding that /dev/random will not block anymore and behave similarly to /dev/urandom after it has been initialized? Or is there still some inherent difference between the two?

hannob 7y ago
The "after it has been initialized" is the inherent difference.

Erlich_Bachman 7y ago

Summarizing the article, `cat /dev/random` will still work but will never block, possibly returning random data based on less entropy than before. They claim that in the modern situation there is already enough entropy in it even for secure key generation. There seemingly will still exist a programmatic way to get a random stream based on predictable amount of entropy, but not through reading this filesystem node.

gioele 7y ago
> Summarizing the article, `cat /dev/random` will still work but will never block `cat /dev/random` may still block, but only once per reboot. It may block if it is called so early that not enough entropy has been gathered yet. Once there enough entropy has been gathered it will never block again.
- simias 7y ago
  As mentioned by the article that's already the default behaviour of getrandom() and the BSDs have symlinked /dev/random to /dev/urandom for a long time already. I think this is a change for the best, in particular this bit sounds completely true to my ears: > Theodore Y. Ts'o, who is the maintainer of the Linux random-number subsystem, appears to have changed his mind along the way about the need for a blocking pool. He said that removing that pool would effectively get rid of the idea that Linux has a true random-number generator (TRNG), which "is not insane; this is what the *BSD's have always done". He, too, is concerned that providing a TRNG mechanism will just serve as an attractant for application developers. He also thinks that it is not really possible to guarantee a TRNG in the kernel, given all of the different types of hardware supported by Linux. Even making the facility only available to root will not solve the problem: Application programmers would give instructions requiring that their application be installed as root to be more secure, "because that way you can get access the _really_ good random numbers". The number of time I've had to deal with security-related software and scripts who insisted in sampling /dev/random and stalling for minutes at a time...
  - JdeBP 7y ago
    A minor note: * Only FreeBSD symbolically links, and it does it in the other direction. urandom is the symbolic link to random. * OpenBSD has four distinct character device files: random, arandom, srandom, and urandom. * NetBSD (as of 2019) has two distinct character device files: random and urandom. They have different semantics from each other. https://netbsd.gw.com/cgi-bin/man-cgi?rnd+4+NetBSD-current https://netbsd.gw.com/cgi-bin/man-cgi?rnd+4+NetBSD-current
    - aquabeagle 7y ago
      On OpenBSD: $ ls -l /dev/*random* lrwxr-xr-x 1 root wheel 7 Dec 10 15:05 /dev/random@ -> urandom crw-r--r-- 1 root wheel 45, 0 Jan 6 15:30 /dev/urandom
      - JdeBP 7y ago
        That must be a recent change. $ ls -F /dev/*random* /dev/arandom /dev/random /dev/srandom /dev/urandom $
        ben_bai 7y ago
        Deleted in 2017. https://marc.info/?l=openbsd-cvs&m=151069089605712&w=2 https://marc.info/?l=openbsd-cvs&m=151069089605712&w=2 you can delete arandom and srandom Edit: better link
  - guenthert 7y ago
    And you don't think they did so for a reason? If you don't care for security (and there are good reason why one wouldn't), then you can create the link yourself on those systems (or link to /dev/zero for extra low wait times). Why does now everyone have to suffer the same? What happened to "keep policy out of the kernel"?
ale_jrb 7y ago
I understood it that reading from `/dev/random` will still block just after boot (i.e. before it's initialised) unless you pass the new flag `GRND_INSECURE` to `getrandom`. After it's initialised, however, it will never block because it's now just using the CRNG.
- richardwhiuk 7y ago
  Please don't confuse `/dev/random` and `getrandom` - they are separate interfaces.

walterbell 7y ago

On the subject of TRNG, John Denker wrote a 2005 paper for using soundcard data as a source of randomness, http://www.av8n.com/turbid/ http://www.av8n.com/turbid/ > We discuss how to configure and use turbid, which is a Hardware Random Number Generator (HRNG), also called a True Random Generator (TRNG). It is suitable for a wide range of applications, from the simplest benign applications to the most demanding high-stakes adversarial applications, including cryptography and gaming. It relies on a combination of physical process and cryptological algorithms, rather than either of those separately. It harvests randomness from physical processes, and uses that randomness efficiently. The hash saturation principle is used to distill the data, so that the output is virtually 100% random for all practical purposes. This is calculated based on physical properties of the inputs, not merely estimated by looking at the statistics of the outputs. In contrast to a Pseudo-Random Generator, it has no internal state to worry about. In particular, we describe a low-cost high-performance implementation, using the computer’s audio I/O system. On randomness, http://www.av8n.com/turbid/paper/turbid.htm#sec-raw-randomness http://www.av8n.com/turbid/paper/turbid.htm#sec-raw-randomne... > Understanding turbid requires some interdisciplinary skills. It requires physics, analog electronics, and cryptography.

hannob 7y ago
This is one of these approaches that are for all practical purposes completely useless. There's basically only three problems generating good randomness: 1. Very early during boot you don't have a lot of good sources. 2. On very constrained devices you have limited external input. 3. Bugs in the implementation. Randomness from soundcards doesn't help with any of these. They probably aren't yet initialized at the point in time where it matters most, they don't exist for the most problematic devices and bugs are bugs, no matter what your source of randomness.
- bigiain 7y ago
  > Randomness from soundcards doesn't help with any of these. "Randomness from soundcards" is also spectacularly unlikely to help on the cloud. Pretty sure they don't fit SoundBlaster16s to EC2 instances or Digital Ocean Droplets...

jonesdaisy 7y ago

https://genericbuddy.com/careprost-3ml-eye-drops https://genericbuddy.com/careprost-3ml-eye-drops

csours 7y ago

I was looking at Java properties the other day and I thought to myself, "We still need to set /dev/./urandom in 2019?"

ktpsns 7y ago
This is a valid point -- most high level programming languages provide some kind of function to provide random numbers in a given interval, such as [0,1]. See also https://stackoverflow.com/questions/2572366/how-to-use-dev-random-or-urandom-in-c https://stackoverflow.com/questions/2572366/how-to-use-dev-r... This is even true for shell scripting, see for instance http://www.tldp.org/LDP/abs/html/randomvar.html http://www.tldp.org/LDP/abs/html/randomvar.html

quotemstr 7y ago

Not blocking under insufficient entropy does not suddenly make that entropy available. Punting entropy collection to userspace doesn't magically allow for DoS-free random number generation --- it just transforms, silently, a condition of insufficient entropy into a subtle security vulnerability. It feels like a form of reality denial, a bit like overcommit. The more time goes by, the more I wish there were a unixlike built on robustness, determinacy, and strict resource accounting.

Hendrikto 7y ago
> Not blocking under insufficient entropy does not suddenly make that entropy available. That’s why it is still blocking until it has been sufficiently initialized. After it has gathered sufficient entropy, the pool’s entropy is not exhausted by reading from it. /dev/random assumes that reading 64 bits from it will decrease the entropy in its pool by 64 bits, which is nonsense. Linux’s PRNG is based on cryptographically strong primitives, and reading output from /dev/random does not expose its internal state. Your pointless rant just indicates that you do not really understand what’s going on.
- cesarb 7y ago
  > /dev/random assumes that reading 64 bits from it will decrease the entropy in its pool by 64 bits, which is nonsense. It's not complete nonsense. Suppose for explanation purposes that you had a pool with only 256 bits (2^256 possible states), and you read 64 bits from it. Of these 2^256 possible states, most would not have output that exact 64-bit value you just read; on average only 2^192 of the possible states would have resulted in that output value. Therefore, once you know that 64-bit value, the pool now has only 192 bits of entropy (2^192 possible states). Read three more 64-bit values, and on average only one of the 2^256 originally possible states could have resulted in these four 64-bit values; since there's only one possible state, the pool's entropy is zero. However, like you said "Linux’s PRNG is based on cryptographically strong primitives": the only known way to find which of the 2^256 possible states could have resulted on these four 64-bit values would be to try all of them. Which is simply not viable, even with all the computing power in the world. That is, once the number of possible states (the pool's entropy) gets above a threshold, even if you later exhaust all the theoretical entropy from it, there's still no way to know the pool's state.

CiPHPerCoder 7y ago

Making /dev/random behave like getrandom(2) will finally put to rest one of the most frustrating arguments in the public understanding of cryptography. Please do it.

jdormit 7y ago
What argument are you referring to?
- jacobush 7y ago
  That you must never use urandom for serious stuff?
- geofft 7y ago
  The question of whether "true random numbers" as defined by this weird government standard exist. More fundamentally, an important conceptual part of crypto is that you can use a random key of a very small, fixed size, like 16 bytes, to generate an infinite amount of output, such that knowing any part of the output doesn't help you guess at any other part of the output nor the input key. If true, this is an amazingly powerful property because you can securely exchange (or derive) a short key once and then you can send as much encrypted data back and forth as you want. If you needed to re-seed the input with as many bits as you take from the output, disk encryption wouldn't be sound (you'd need a key or passphrase as long as your disk), SSL would be way more expensive (and couldn't be forward-secure) if it even worked at all, Kerberos wouldn't work, Signal wouldn't work, etc. The claim of /dev/random and this wacky government standard is that in fact disk encryption, SSL, etc. are flawed designs, good enough for securing a single communication but suboptimal because they encrypt more bits of data than the size of the random key, and so when generating random keys, you really ought to use "true random numbers" so that breaking one SSL connection doesn't help you break another. Whether it's a pen-and-paper cipher like Vigenère or a fancy modern algorithm like AES, anything with a fixed-size key can be cryptanalyzed and you shouldn't provide too much output with it, for your secure stuff you must use a one-time pad. The claim of the cryptography community is that, no, in fact, there's nothing flawed about this approach and stretching fixed-size keys is the very miracle of cryptography. We know how to do it securely for any worthwhile definition of "securely" (including definitions where quantum computers are relevant) and we should, because key-based encryption has changed our world for the better.

brohee 7y ago

That this happens right after Thomas Pornin ridiculing the blocking pool (https://research.nccgroup.com/2019/12/19/on-linuxs-random-number-generation/ https://research.nccgroup.com/2019/12/19/on-linuxs-random-nu..., HN discussion https://news.ycombinator.com/item?id=21843081 https://news.ycombinator.com/item?id=21843081) is obviously purely coincidental, right? Especially as it was read and commented upon by Theodore Tso that at last changed his mind...

dfc 7y ago
It's version three of this patch.
ATsch 7y ago
Many people have been ridiculing entropy tracking as pointless pseudeo-security vodoo for a very long time. https://media.ccc.de/v/32c3-7441-the_plain_simple_reality_of_entropy https://media.ccc.de/v/32c3-7441-the_plain_simple_reality_of... This talk from 2015 springs to mind to me as the previous widely discussed one. But the ncc article might of course have been the straw that healed the camels back.
- tytso 7y ago
  There was a time when some people thought that it was just fine to use MD5 and SHA1. Yarrow-160, a random number generator devised by Kelsey, Schineier, and Ferguson, used SHA1. Entropy tracking was used in the original versions of PGP because there were those people who had a very healthy (for that time) lack of confidence in "strong cryptographic algorithms" actually being strong. As PBS Space Time once said, discussing Pilot Wave Theory and why it's considered unorthodox when compared to the Many Worlds interpretation of Quantuum Theory, "Orthrodoxy == Radicalism plus Time". There was a time when the Many Worlds interpretation was considered out there. Similarly, there was a time when not trusting crypto algorithms as being Forever Strong was normal, and designing a network protocol like Wireguard without algorithm agility would have been considered highly radical. Today, trusting "strong cryptographic primitives" is considered an axiom. But remember that an axiom is something that you assume to be true and use as the basis of further proofs. Just as a Voodoo practitioner assumes that their belief system is true....

zaarn 7y ago

It's very amusing that the various kernel developers are bashing on GnuPG, going as far as calling it's behaviour a "misuse. Full stop." PGP/GPG has certainly falled out of favor.

deleted 7y ago
[deleted]
grammarxcore 7y ago
So is GnuPG bad because it reads directly from /dev/random instead of using an interface like getrandom()? I'm naive enough to not know reading directly from /dev/random is bad and would love to know more.
- toast0 7y ago
  The getrandom() syscall is relatively new. Before it was available, you had two choices. Use a non-Linux OS with reasonable /dev/(u)random or use Linux with its Sophie's choice: /dev/random will give you something that's probably good, but will block for good and bad reasons. /dev/urandom will never block, including when the random system is totally unseeded. GnuPG could not use /dev/urandom, since there was no indication of seeding, so it had to use /dev/random which blocks until the system is seeded and also when the entropy count of nebulous value was low. Most (all) BSDs have /dev/urandom the same as /dev/random, where it blocks until seeded and then never blocks again . This behavior is available in Linux with the getrandom() syscall, but perhaps GnuPG hasn't updated to use it? Also, there was some discussion in the last few months of changing the behavior of that syscall, which thankfully didn't happen, in favor of having the kernel generate some hopeful entropy on demand in case there is a caller blocked on random with an unseeded pool.
  - grammarxcore 7y ago
    So the issue is the block? I make a blocking call and another app attempts to make a call during the block and will fail if it's not expecting to wait? Is that (one of) the problem(s)? Thanks for breaking that down for me!

latchkey 7y ago

Filed this one in 2011 and it got a lot of heated discussion... https://bugs.launchpad.net/bugs/706011 https://bugs.launchpad.net/bugs/706011

jancsika 7y ago
A professional response on a bug report seeks to narrow down the possible source of a bug (if any) so it may be understood, tested, and addressed properly. The first response to start such a process is taligent in response #22. A useful addition to that is #23 where Steven Ayre suggests opening that as a separate bug that focuses solely on this issue. I'm not sure what the purpose is for the other responses you received. They seem to seek to use the breadth of your issue report to widen the discussion to maximally contentious security topics.
- JdeBP 7y ago
  That's not a fair assessment of the other responses. Steve McIntyre's in #7, for one example.

pczy 7y ago

This is the best explanation of this issue that i know of: https://www.2uo.de/myths-about-urandom https://www.2uo.de/myths-about-urandom

devit 7y ago

There are two threat models against code using RNGs: 1. The adversary has an amount of computing power that is feasible as currently foreseeable: in this case, all you need are K "truly random" bits where K=128/256/512 and can then use a strong stream cipher or equivalent to generate infinite random bits, so you only need to block at boot to get those K bits, and you can even store them on disk from the previous boot and have them passed from an external source at install time 2. The adversary has unlimited computing power: in this case, you need hardware that can generate truly random bits and can only return randomness at the rate the hardware gives you the bits Now obviously if you are using the randomness to feed an algorithm that is only strong against feasible computing power (i.e. all crypto except one-time pads) then it doesn't make sense to require resistance against unlimited computing power for the RNG. So in practice both /dev/urandom, /dev/random, getrandom(), etc. should only resist feasible computing power, and resisting against unlimited computing power should be a special interface that is never used by default except by tool that generate one-time pads or equivalent.

xyzzyz 7y ago
> 2. The adversary has unlimited computing power: in this case, you need hardware that can generate truly random bits and can only return randomness at the rate the hardware gives you the bits What would you need those bits for in that case? Literally the only things that comes to my mind is generating one time pads, as standard cryptography is useless in such scenario.
- firethief 7y ago
  Game-theoretically, you want a source of random numbers when you need to make a decision your adversary can't predict. Traditionally some cultures have (accidentally?) used bird augury for this, but obviously that won't do when you're up against Unlimited Computing Power, as birds are basically deterministic.
- deleted 7y ago
  [deleted]
fooker 7y ago

JdeBP 7y ago

Interestingly, this follows the systemd people back in 2018 changing its seed-at-boot tool, systemd-random-seed, to write the machine-ID as the first 16 bytes of seed data to /dev/random at every seed write. * https://github.com/systemd/systemd/commit/8ba12aef045ba1a766a73f535a114781dbb763c2 https://github.com/systemd/systemd/commit/8ba12aef045ba1a766... * https://www.freedesktop.org/software/systemd/man/systemd-random-seed.service.html https://www.freedesktop.org/software/systemd/man/systemd-ran... * http://jdebp.uk./Softwares/nosh/guide/commands/machine-id.xml http://jdebp.uk./Softwares/nosh/guide/commands/machine-id.xm...

edoceo 7y ago

This looks like it explains why syslog-ng is hanging on boot? It's trying to read a random. At least, hangs until there is some random (have to just mash the keyboard a bit)

beefhash 7y ago
I am now somewhat curious why syslog-ng needs random bytes on boot.
lanternslight 7y ago
Ugh! That explains so much! I did not correlate the mashing of keys and mouse clicks with RNG.
downerending 7y ago
This reminds me of the (possibly apocryphal) story of old VMS (?) systems hanging if their console, which was often a printer, ran out of paper.

emilfihlman 7y ago

Changing getrandom was just idiotic and breaks god damn userspace. The man page was extremely clear in documentation in the first place.

SignalsFromBob 7y ago

Are hardware RNGs, such as the ones that plug into a USB port, of any value when the RNG in Linux is good enough for generating GPG keys? I'm wondering what the use case is for people that buy them.

commandersaki 7y ago

I don't see why this is so difficult. 1. Make a kernel config option that makes /dev/urandom block until entropy pool initialises. 2. Make a dependant kernel config option so /dev/random is /dev/urandom. There done. Everyone can have their own choice on what security they want.