4 ms·

> Not blocking under insufficient entropy does not suddenly make that entropy available. That’s why it is still blocking until it has been sufficiently initial

> 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.

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.