7 ms·

Not blocking under insufficient entropy does not suddenly make that entropy available. Punting entropy collection to userspace doesn't magically allow for DoS-f

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.
  - tptacek 7y ago
    This is not how the LRNG works, or has ever worked. Think of CSPRNG output as the keystream of a stream cipher, which is what it practically is. Draw 256 bytes of keystream out of a stream cipher, and you have in no meaningful sense depleted that cipher's remaining store of unpredictable keystream bytes. Were it otherwise, no modern cryptography would function.
- jerf 7y ago
  "/dev/random assumes that reading 64 bits from it will decrease the entropy in its pool by 64 bits, which is nonsense." To amplify Hendrikto's point, /dev/random is implemented to "believe" that if it has 128 bits of randomness, and you get 128 bits from it, it now has 0 bits of randomness in it. 0 bits of randomness means that you ought to now be able to tell me exactly what the internal state of /dev/random is. I don't mean it vaguely implies that in the English sense, I mean, that's what it mathematically means. To have zero bits of randomness is to be fully determined. Yet this is clearly false. There is no known and likely no feasible process to read all the "bits" out of /dev/random and tell me the resulting internal state. Even if there was some process to be demonstrated, it would still not necessarily result in a crack of any particular key, and it would be on the order of a high-priority security bug, but nothing more. It's not an "end of the world" scenario.
  - quotemstr 7y ago
    > There is no known and likely no feasible process to read all the "bits" out of /dev/random and tell me the resulting internal state That's fine if you trust the PRNG. Linux used to at least attempt to provide a source of true randomness. You and Hendrikto are essentially asserting that everyone ought to accept the PRNG output in lieu of true randomness. Given various compromises in RNG primitives over the years, I'm not so sure it's a good idea to completely close off the true entropy estimation to userspace. I prefer punting that choice to applications, which can use urandom or random today at their choice. Maybe everyone should be happy with the PRNG output. T'so goes further and argues, however, that if you provide any mechanism to block on entropy (even to root only), applications will block on it (due to a perception of superiority) and so the interface must be removed from the kernel. I see this change as an imposition of policy on userspace.
    - jerf 7y ago
      "You and Hendrikto are essentially asserting that everyone ought to accept the PRNG output in lieu of true randomness." No, what I am asserting is simply that the idea that you drain one bit of randomness out of a pool per bit you take is not practically true unless you can actually fully determine the state of the randomness generator when you've "drained" it. No less, no more. You can't have "zero bits of entropy" and also "I still can't tell you the internal contents of the random number" generator at the same time, because the latter is "non-zero bits of entropy". Either you've got zero or you don't. As of right now, nobody can so determine the state of the random number generator from enough bits of output, we have no reason to believe anybody ever will [1], and the real kicker is even if they someday do, it's a bug, not the retroactive destruction of all encryption ever. A SHA-1 pre-image attack is a much more serious practical attack on cryptography than someone finding a way to drain /dev/random today and get the internal state. It's only true in theory that you've "drained" the entropy when you have access to amounts of computation that do not fit into the universe. Yes, it is still true in theory, but not in a useful way. We do not need to write our kernels as if our adversaries are turning galaxy clusters into computronium to attack our random number generator. [1]: Please carefully note distinction between "we have no reason to believe anyone ever will" and "it is absolutely 100% certain nobody ever will". We have no choice but to operate on our best understandings of the world now. "But maybe somebody may break" doesn't apply to just the current random generator... it applies to everything including all possible proposed replacements, so it does not provide a way to make a choice.
saagarjha 7y ago
Isn’t overcommitment a feature of most modern operating systems?
- wahern 7y ago
  Not on Windows, where it's optional on a per request basis. It's common on Unix because of fork[1], but AFAIU only Linux and FreeBSD overcommit by default for all anonymous memory allocation (i.e. malloc backing). [1] Notably, Solaris does not overcommit for fork.
  - saagarjha 7y ago
    macOS overcommits; not sure about some of the other BSDs do by default but I'm fairly sure they have knobs for it.
    - wahern 7y ago
      AFAIU, macOS implements dynamic swap and I assumed it always backed anonymous memory with swap reservations. Do you have a reference?
      - saagarjha 7y ago
        Hmm, maybe I'm misunderstanding? When you make a (single) patently large allocation, macOS will do nothing; it won't show up as used virtual memory and the swap size won't go up. As you write to the memory usage will go up ("Memory" in Activity Monitor) but then it will quickly start swapping out until the limits of your disk, at which point you'll get OOM'd (assuming that your memory doesn't compress well, that is…).
        wahern 7y ago
        Ah, I see. Thanks!
  - jsmith45 7y ago
    I was not aware of any mechanism that would cause windows to allow overcommits. The main allocation APIs allow for a "reservation" type of allocation, which reserves some of the virtual address space in the process, without actually allocating it. But those need to be converted to real allocations before use, and doing that adds to the processes commit charge. I never found any API for actually making memory available to a process without increasing that processes's commit charge. That would obviously be necessary for real overcommit, as to my knowledge it is supposed to be an invariant of Windows that the sumOfAllProcessesCommitCharge < physicalMemory+pageFileSize. If an API exists for this, I must have missed it. I suppose a process could simulate overcommit by catching the Access Violation, verifying that the violation was a read/write of a reserved page allocated with some special "virtual overcommit" allocator, and requesting that it be committed, and resuming execution. Needless to say, such user mode page fault handling will be significantly slower than a kernel doing it.
deleted 7y ago
[deleted]
imtringued 7y ago
Actually you are making exactly the mistake that this change is intended to avoid. The distinction between /dev/random and /dev/urandom makes it appear that /dev/urandom is inferior and /dev/random is the "true" random number generator but that isn't the case. They are equally good since they both wait for an initial amount of entropy and receive additional entropy from the OS even after boot. Additional entropy does make the RNG more secure [0] but reusing existing entropy doesn't make your random numbers less secure because they were created from an unpredictable source. [0] Let's say you plug in a USB based hardware RNG, after booting. You turn a software entropy source on, after booting. /dev/random would immediately take advantage of the RNG. Already opened /dev/urandom streams wouldn't, until they are closed. (For how many people is this a critical feature?)
- ryukafalz 7y ago
  > The distinction between /dev/random and /dev/urandom makes it appear that /dev/urandom is inferior and /dev/random is the "true" random number generator but that isn't the case. They are equally good since they both wait for an initial amount of entropy and receive additional entropy from the OS even after boot. I was under the impression that urandom does not wait for initial entropy on Linux. Am I mistaken/has this changed?

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.
- tptacek 7y ago
  This is not how the LRNG works, or has ever worked. Think of CSPRNG output as the keystream of a stream cipher, which is what it practically is. Draw 256 bytes of keystream out of a stream cipher, and you have in no meaningful sense depleted that cipher's remaining store of unpredictable keystream bytes. Were it otherwise, no modern cryptography would function.
jerf 7y ago
"/dev/random assumes that reading 64 bits from it will decrease the entropy in its pool by 64 bits, which is nonsense." To amplify Hendrikto's point, /dev/random is implemented to "believe" that if it has 128 bits of randomness, and you get 128 bits from it, it now has 0 bits of randomness in it. 0 bits of randomness means that you ought to now be able to tell me exactly what the internal state of /dev/random is. I don't mean it vaguely implies that in the English sense, I mean, that's what it mathematically means. To have zero bits of randomness is to be fully determined. Yet this is clearly false. There is no known and likely no feasible process to read all the "bits" out of /dev/random and tell me the resulting internal state. Even if there was some process to be demonstrated, it would still not necessarily result in a crack of any particular key, and it would be on the order of a high-priority security bug, but nothing more. It's not an "end of the world" scenario.
- quotemstr 7y ago
  > There is no known and likely no feasible process to read all the "bits" out of /dev/random and tell me the resulting internal state That's fine if you trust the PRNG. Linux used to at least attempt to provide a source of true randomness. You and Hendrikto are essentially asserting that everyone ought to accept the PRNG output in lieu of true randomness. Given various compromises in RNG primitives over the years, I'm not so sure it's a good idea to completely close off the true entropy estimation to userspace. I prefer punting that choice to applications, which can use urandom or random today at their choice. Maybe everyone should be happy with the PRNG output. T'so goes further and argues, however, that if you provide any mechanism to block on entropy (even to root only), applications will block on it (due to a perception of superiority) and so the interface must be removed from the kernel. I see this change as an imposition of policy on userspace.
  - jerf 7y ago
    "You and Hendrikto are essentially asserting that everyone ought to accept the PRNG output in lieu of true randomness." No, what I am asserting is simply that the idea that you drain one bit of randomness out of a pool per bit you take is not practically true unless you can actually fully determine the state of the randomness generator when you've "drained" it. No less, no more. You can't have "zero bits of entropy" and also "I still can't tell you the internal contents of the random number" generator at the same time, because the latter is "non-zero bits of entropy". Either you've got zero or you don't. As of right now, nobody can so determine the state of the random number generator from enough bits of output, we have no reason to believe anybody ever will [1], and the real kicker is even if they someday do, it's a bug, not the retroactive destruction of all encryption ever. A SHA-1 pre-image attack is a much more serious practical attack on cryptography than someone finding a way to drain /dev/random today and get the internal state. It's only true in theory that you've "drained" the entropy when you have access to amounts of computation that do not fit into the universe. Yes, it is still true in theory, but not in a useful way. We do not need to write our kernels as if our adversaries are turning galaxy clusters into computronium to attack our random number generator. [1]: Please carefully note distinction between "we have no reason to believe anyone ever will" and "it is absolutely 100% certain nobody ever will". We have no choice but to operate on our best understandings of the world now. "But maybe somebody may break" doesn't apply to just the current random generator... it applies to everything including all possible proposed replacements, so it does not provide a way to make a choice.

saagarjha 7y ago

Isn’t overcommitment a feature of most modern operating systems?

wahern 7y ago
Not on Windows, where it's optional on a per request basis. It's common on Unix because of fork[1], but AFAIU only Linux and FreeBSD overcommit by default for all anonymous memory allocation (i.e. malloc backing). [1] Notably, Solaris does not overcommit for fork.
- saagarjha 7y ago
  macOS overcommits; not sure about some of the other BSDs do by default but I'm fairly sure they have knobs for it.
  - wahern 7y ago
    AFAIU, macOS implements dynamic swap and I assumed it always backed anonymous memory with swap reservations. Do you have a reference?
    - saagarjha 7y ago
      Hmm, maybe I'm misunderstanding? When you make a (single) patently large allocation, macOS will do nothing; it won't show up as used virtual memory and the swap size won't go up. As you write to the memory usage will go up ("Memory" in Activity Monitor) but then it will quickly start swapping out until the limits of your disk, at which point you'll get OOM'd (assuming that your memory doesn't compress well, that is…).
      - wahern 7y ago
        Ah, I see. Thanks!
- jsmith45 7y ago
  I was not aware of any mechanism that would cause windows to allow overcommits. The main allocation APIs allow for a "reservation" type of allocation, which reserves some of the virtual address space in the process, without actually allocating it. But those need to be converted to real allocations before use, and doing that adds to the processes commit charge. I never found any API for actually making memory available to a process without increasing that processes's commit charge. That would obviously be necessary for real overcommit, as to my knowledge it is supposed to be an invariant of Windows that the sumOfAllProcessesCommitCharge < physicalMemory+pageFileSize. If an API exists for this, I must have missed it. I suppose a process could simulate overcommit by catching the Access Violation, verifying that the violation was a read/write of a reserved page allocated with some special "virtual overcommit" allocator, and requesting that it be committed, and resuming execution. Needless to say, such user mode page fault handling will be significantly slower than a kernel doing it.

deleted 7y ago

[deleted]

imtringued 7y ago

Actually you are making exactly the mistake that this change is intended to avoid. The distinction between /dev/random and /dev/urandom makes it appear that /dev/urandom is inferior and /dev/random is the "true" random number generator but that isn't the case. They are equally good since they both wait for an initial amount of entropy and receive additional entropy from the OS even after boot. Additional entropy does make the RNG more secure [0] but reusing existing entropy doesn't make your random numbers less secure because they were created from an unpredictable source. [0] Let's say you plug in a USB based hardware RNG, after booting. You turn a software entropy source on, after booting. /dev/random would immediately take advantage of the RNG. Already opened /dev/urandom streams wouldn't, until they are closed. (For how many people is this a critical feature?)

ryukafalz 7y ago
> The distinction between /dev/random and /dev/urandom makes it appear that /dev/urandom is inferior and /dev/random is the "true" random number generator but that isn't the case. They are equally good since they both wait for an initial amount of entropy and receive additional entropy from the OS even after boot. I was under the impression that urandom does not wait for initial entropy on Linux. Am I mistaken/has this changed?