Comment by wolf550e
7 years ago
Because after you gather ~256 bits of entropy from I/O sources (or rdrand^H^H^H rdseed [1]), using it to generate infinite output of /dev/urandom does not drain it. Adding more entropy only helps if the entropy pool inner state leaked, it is not needed to add more entropy because it drained through using it.
Proof:
1. Take 256 bits of entropy.
2. Use HKDF to generate 128 bit key and 64 bit nonce.
3. Use key and nonce for AES-CTR with all possible 2^64 counter values to produce 2^68 bytes of output.
4. goto 2.
If you can compute the inner state of the RNG (and thus predict future output) by just observing the output (not through side channels), using any amount of output, then all modern symmetric crypto is broken. If you can't, then using the entropy in an RNG does not drain the entropy pool.
And here is a CCC talk about it: https://www.youtube.com/watch?v=OSfmtRc4VsE
1 - https://software.intel.com/en-us/blogs/2012/11/17/the-differ...
EDIT: Thanks for 'dragontamer for pointing out difference between rdrand and rdseed.
So after reading this thread my understanding of the "draining is a fallacy" view is
(1) yes genuine non-programmatic entropy bits accumulate at a slow rate and can be drained
(2) in practise no one should care about (1) because once you have ~256 bits to initialise a CSPRNG you can use the output of that CSPRNG until the Earth is swallowed up by the sun; thats what the S of Cryptographically Secure Programmatic Random Number Generator promises.
(3) the linked systemd code is silly to even provide a function genuine_random_bytes that tries to get additional genuine non-programmatic entropy as every possible use case is covered by (2)
(4) The real fallacy is when people think that it might be possible to discover the seed of a CSRNG or predict its next outputs by examining a long enough run of its previous output. In practise such an attack should not be possible.
If I've got the summary right, the only point I would disagree on principle is (3). I can imagine that someone might rationally want "genuine" entropy independent of a kernel CSPRNG, for example for seeding their own CSPRNG.
re your (1), the bits cannot be drained. The only thing that can happen to them is that there is an attacker with root on your computer, and they see the CSPRNG inner state, and the attacker loses their access but they can still predict output of CSPRNG because it's deterministic, so you want to inject new entropy into it so the attacker will lose ability to predict CSPRNG output. djb says this is nonse. https://blog.cr.yp.to/20140205-entropy.html
> If you can compute the inner state of the RNG (and thus predict future output) by just observing the output (not through side channels), using any amount of output, then all modern symmetric crypto is broken. If you can't, then using the entropy in an RNG does not drain the entropy pool.
This seems wrong to me.
If you can predict #1 (the 256-bits of entropy in step 1), then you can break the system. This is highly likely, as Intel only assures 65-bits of entropy across two rdrand calls. (64-bits of entropy from the first call, +1 bit from the 2nd call, since RDRAND is generated from an internal random number generator. So there's going to be a correlation between the two values).
In effect, if #1 is created with four calls to RDRAND, you only have around 68-bits of entropy, which can be brute-forced faster than a true source of 256-bits of entropy. Therefore, your RNG is broken. https://software.intel.com/en-us/blogs/2012/11/17/the-differ...
RDSEED is the instruction that guarantees 64-bits of independent / multiplicative entropy, but executes slower as a result.
----------
In effect, you're "simplifying" the problem. #1, getting 256 bits of entropy, is the hard part of the problem. You cannot ignore this part of the problem.
In any case, it seems to me that a large number of people don't know how to properly use the RDRAND function, in this thread as well as in the Github thread. RDRAND has a chance of failure, AND it doesn't even hold multiplicative entropy guarantees.
So this seems like a case of EVERYONE hasn't read the docs yet. Please people, do NOT use RDRAND as a source of entropy. Use RDSEED as a source of entropy. RDRAND is only a random number generator with only 64-bits of entropy guaranteed at any given state, and probably additive entropy at that.
I can ignore "how to do #1" when discussing whether entropy is drained by using it or not.
You need to get 256 bits of high quality entropy. We assume there are ways to do that.
On a device that has no way to do that, you can't do crypto (unless you accept the entropy from outside, which is key escrow, but might be ok for an IoT device that communicates only to its mothership).
> I can ignore "how to do #1" when discussing whether entropy is drained by using it or not.
Ehhh... fair point. Still, the overall discussion is about RDRAND, so I feel like its very important to point out how RDSEED must be used to properly generate the 256 bits of entropy you require in step #1.
Each of these steps are tricky, and require thorough analysis to understand.
------------
EDIT: Its not so much that entropy is "used up". Its that RNG-sources of randomness gives "additive" entropy, while true entropy is "multiplicative".
Generating random numbers from a 256-bit RNG will give 256-bits of entropy from the first step, but be 100% predictable (and therefore "only" 256-bits on the 2nd step).
If the "next programmer" wants 512-bits of entropy, they will NEVER get 512-bits of entropy from your methodology, because you only started with 256-bits of entropy. Only by gathering "more" entropy will you be able to reach 512-bits of entropy.
The argument would go "who needs more than 256-bits of entropy", which is a fine point. But... that's how the math checks out.
It all comes back to the RDRAND vs RDSEED question. If the user just wants "unpredictable random numbers", then RDRAND and /dev/urandom is sufficient. But if you're creating independent random number generators (ex: If you're creating a service like random.org, and are guaranteeing certain amount of entropy per call to everyone), then you need to be using RDSEED.
Does 10 calls of your RNG produce 256-bits of randomness, or 2560-bits of randomness? What are your requirements? What are the requirements of the end user? For most people, having a RNG that "only" provides 256-bits of randomness across 10,000 calls is perfectly fine and sufficient. But there are plenty of cryptographic cases where that's not enough (and "true" 256-bits of entropy are needed in every call).
11 replies →