4 ms·

RNG state entropy is not a resource that is exhausted by using the RNG. But even if it were, and assuming entropy limitations are relevant in this context (whi

RNG state entropy is not a resource that is exhausted by using the RNG. But even if it were, and assuming entropy limitations are relevant in this context (which I'd argue they are not), the total entropy requirement would not change by merely deriving the same set of values in another way. You might only need more bytes (!= entropy) from your root RNG to seed two separate RNGs. In which case you could just stretch the same number of bytes you'd normally request using e.g. HKDF. But again, it doesn't make much sense to think of entropy as something you can count or use up, really. There is no way to tell, and just a few bits (say 128) of entropy would be sufficient for almost anything...

koolba 9y ago
That’s what I’m referring to, retrieving more entropy from the system source to juice the initial state of the RNG. If you have a separate RNG per connection (or two per connection) that requires separate init, each connection would drain the system pool slightly. That’d be in constraint two having two static pools shared for all connections.
- tptacek 9y ago
  No, what they're saying is that the notion that you can "drain" the system pool is an urban legend created by a bad Linux man page. In reality, entropy isn't really ever "drained" from the system entropy pool.
  - AgalmicVentures 9y ago
    Expanding on this, for anyone who wants to read more, http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/ is a good resource.
  - FeepingCreature 9y ago
    The pool's estimated isn't drained, but its "objective entropy" is reduced; ie. the amount of state leaked to the outside goes up. Of course, practically you can't recover that information within a usable timespan, so it's academic. Actually, now I sort of wonder what would happen if you encrypted a quantum superposition so that to determine which branch was taken would require reversing an operation using, at the lower bound, more computation than is available in the universe. Would it hold, or collapse/decohere?
cesarb 9y ago
> RNG state entropy is not a resource that is exhausted by using the RNG. I thought so too, but a couple of years ago I was writing a comment on LWN (https://lwn.net/Articles/642839/ https://lwn.net/Articles/642839/) and it suddenly clicked. Entropy is a measure of unpredictability, that is, if you have 32 bits of entropy, there are 2^32 possible states. Suppose you generate an 8-bit value from that, assuming a function which uniformly mixes your state. For each of the possible 256 output values, on average 2^24 of the possible states would generate the same output value. Therefore, once you know the output value, you can discard the other 2^32 - 2^24 possibilities; only 2^24 possible states remain, so you now have only 24 bits of entropy left. The reason this is not a problem in practice is that, since the output function is one-way, an attacker would have to enumerate all possible states to find which ones would generate the same outputs. This becomes unfeasible once you have enough entropy in your state (256 bits or more). (The whole trick with Dual-EC was that, if you know the secret key, the output function is not one-way. Supposedly, either the key was discarded once generated, or the points were generated at random and not from a secret key, but nobody really believes that.)
- tptacek 9y ago
  In reality, all mainstream CSPRNGs are essentially just stream cipher keystreams (PRFs). Some of them run AES in CTR mode, some of them run HMAC. The commonality is that the "raw entropy" (from system timings and whatnot) is run through what is essentially a KDF and fed to the PRF. To believe that tapping 128 bits of "entropy" from /dev/urandom is equivalent to "depleting" 128 bit of entropy from the "system entropy pool", you must also believe that encrypting 16 bytes with AES-CTR somehow materially weakens the key. Obviously, that's not happening. We don't "run out of key" as we encrypt with a PRF. As Dan Bernstein puts it, securely expanding small secrets into very, very long secrets of one of the core functions of cryptography. Look at the key schedule of any block cipher for a very basic example. We reject ciphers in designs based on their inability to encrypt 2^64 blocks worth of data without potentially creating artifacts.
  - cesarb 9y ago
    > To believe that tapping 128 bits of "entropy" from /dev/urandom is equivalent to "depleting" 128 bit of entropy from the "system entropy pool", you must also believe that encrypting 16 bytes with AES-CTR somehow materially weakens the key. As long as none of the 128 bits of the plaintext is known, we're also adding 128 bits of unpredictability, so the net result is zero. If some of the plaintext bits are known, in theory the unpredictability should decrease. For an extreme example: if all 128 bits of plaintext are known, and all 128 bits of ciphertext are also known, there should be a single 128 bit AES key that maps that input to that output, so the entropy left in the key would be zero. However, there is no known way to find that single key other than through a brute force search through all the 2^128 keys, so it's still safe. That also applies to the CSPRNGs: even if the entropy has decreased to zero, as long as an attacker has to brute force through a large enough number of possible states to take advantage of that fact, it's safe. It doesn't change the fact that, when the entropy left is zero, there is a single state which could lead to the observed outputs. Yes, this means that after the entropy in the CSPRNG has passed the point where brute force is no longer viable, the amount of entropy left on the pool becomes a useless measurement. What matters is how much work an attacker would have to do, not how much theoretical entropy is left.

koolba 9y ago

That’s what I’m referring to, retrieving more entropy from the system source to juice the initial state of the RNG. If you have a separate RNG per connection (or two per connection) that requires separate init, each connection would drain the system pool slightly. That’d be in constraint two having two static pools shared for all connections.

tptacek 9y ago
No, what they're saying is that the notion that you can "drain" the system pool is an urban legend created by a bad Linux man page. In reality, entropy isn't really ever "drained" from the system entropy pool.
- AgalmicVentures 9y ago
  Expanding on this, for anyone who wants to read more, http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/ is a good resource.
- FeepingCreature 9y ago
  The pool's estimated isn't drained, but its "objective entropy" is reduced; ie. the amount of state leaked to the outside goes up. Of course, practically you can't recover that information within a usable timespan, so it's academic. Actually, now I sort of wonder what would happen if you encrypted a quantum superposition so that to determine which branch was taken would require reversing an operation using, at the lower bound, more computation than is available in the universe. Would it hold, or collapse/decohere?

cesarb 9y ago

> RNG state entropy is not a resource that is exhausted by using the RNG. I thought so too, but a couple of years ago I was writing a comment on LWN (https://lwn.net/Articles/642839/ https://lwn.net/Articles/642839/) and it suddenly clicked. Entropy is a measure of unpredictability, that is, if you have 32 bits of entropy, there are 2^32 possible states. Suppose you generate an 8-bit value from that, assuming a function which uniformly mixes your state. For each of the possible 256 output values, on average 2^24 of the possible states would generate the same output value. Therefore, once you know the output value, you can discard the other 2^32 - 2^24 possibilities; only 2^24 possible states remain, so you now have only 24 bits of entropy left. The reason this is not a problem in practice is that, since the output function is one-way, an attacker would have to enumerate all possible states to find which ones would generate the same outputs. This becomes unfeasible once you have enough entropy in your state (256 bits or more). (The whole trick with Dual-EC was that, if you know the secret key, the output function is not one-way. Supposedly, either the key was discarded once generated, or the points were generated at random and not from a secret key, but nobody really believes that.)

tptacek 9y ago
In reality, all mainstream CSPRNGs are essentially just stream cipher keystreams (PRFs). Some of them run AES in CTR mode, some of them run HMAC. The commonality is that the "raw entropy" (from system timings and whatnot) is run through what is essentially a KDF and fed to the PRF. To believe that tapping 128 bits of "entropy" from /dev/urandom is equivalent to "depleting" 128 bit of entropy from the "system entropy pool", you must also believe that encrypting 16 bytes with AES-CTR somehow materially weakens the key. Obviously, that's not happening. We don't "run out of key" as we encrypt with a PRF. As Dan Bernstein puts it, securely expanding small secrets into very, very long secrets of one of the core functions of cryptography. Look at the key schedule of any block cipher for a very basic example. We reject ciphers in designs based on their inability to encrypt 2^64 blocks worth of data without potentially creating artifacts.
- cesarb 9y ago
  > To believe that tapping 128 bits of "entropy" from /dev/urandom is equivalent to "depleting" 128 bit of entropy from the "system entropy pool", you must also believe that encrypting 16 bytes with AES-CTR somehow materially weakens the key. As long as none of the 128 bits of the plaintext is known, we're also adding 128 bits of unpredictability, so the net result is zero. If some of the plaintext bits are known, in theory the unpredictability should decrease. For an extreme example: if all 128 bits of plaintext are known, and all 128 bits of ciphertext are also known, there should be a single 128 bit AES key that maps that input to that output, so the entropy left in the key would be zero. However, there is no known way to find that single key other than through a brute force search through all the 2^128 keys, so it's still safe. That also applies to the CSPRNGs: even if the entropy has decreased to zero, as long as an attacker has to brute force through a large enough number of possible states to take advantage of that fact, it's safe. It doesn't change the fact that, when the entropy left is zero, there is a single state which could lead to the observed outputs. Yes, this means that after the entropy in the CSPRNG has passed the point where brute force is no longer viable, the amount of entropy left on the pool becomes a useless measurement. What matters is how much work an attacker would have to do, not how much theoretical entropy is left.