If the attacker managed to read the inner state of your RNG, you need to rotate all keys. There is no defense. The key erasure RNG only limits the damage.
There is no "entropy fills back up", because it is not drained. There is "adding/replacing non-deterministic entropy", to mitigate how many keys are known to attacker if attacker had access to RNG inner state for limited amount of time.
The entropy in /dev/random it not any better than the entropy in /dev/urandom, after the entropy pool has been initialized (step 1 in my algo) they are the same. /dev/random blocks until step 1 is complete. Step #1 is not complete in two cases: very early boot before the entropy pool has been read from storage and boot with no entropy pool stored, so need to gather entropy from I/O or hardware RNG like rdseed.
For ssh, tls, wireguard etc, use urandom.
For embedded devices: inject entropy pool value at manufacturing time.
For VMs: inject entropy pool from host at first start / VM clone.
The server never "runs out of entropy".
Please watch the CCC presentation I linked above.
That's not the attack I'm talking about. The inner-state of your RNG can be brute-forced with an attack of size 2^256 (assuming 256-bits of internal state to your RNG).
If your 256-bit RNG creates 100x 256-bit AES-keys, the "common thread" is to attack the RNG. That's the most efficient way to get all 100x AES keys.
Case in point:
1. Try state X
2. Did it generate the RNG Sequence you're attacking? If so, you're done.
3. If not, X = X+1. Go back to step #1 and loop.
Simple brute-force attack against the state. That is to say, a 256-bit RNG only has "256-bits" of protection. Or to put it another way: the 100x AES Keys you've generated all have 256-bits of protection, max.
-----------
Stick a TRUE Hardware random number generator with entropy guarantees (such as RDSEED) as your generator, and you're immune to this brute force attack. In theory, its a non-trivial difference. In practice, 256-bits of entropy is enough for most people, and no one is going to accomplish this brute force attack.
Its not about "draining" entropy. Its about asking yourself how much entropy your application needs. I can IMAGINE people needing more than 256-bits of entropy in higher-security contexts.
* 100x different AES-256 keys generated by /dev/random would have 25,600 bits of entropy. (All 100x keys are independent, and would require an attack effort per key).
* 100x different AES-256 keys generated by /dev/urandom would "only" have 256-bits of entropy. (/dev/urandom would be attacked, assuming /dev/urandom started with 256-bits of entropy in its pool, assuming /dev/urandom never got extra entropy in the 100x calls)
You can't pretend that the two solutions to the problem are the same. At best, you can suggest that 256-bits of entropy is enough for practical purposes.
Again, after seeding with initial entropy, /dev/random and /dev/urandom are the same, /dev/random is not better entropy.
Attacking a single 256 bit key is exactly as equally impossible as attacking a 256 bit RNG pool used to generate 100 keys.
There is no actual scenario in which using hardware RNG to generate 100 keys would keep me safe while using a hardware RNG to initialize a deterministic RNG to generate 100 keys would lead to compromise.
If your attacker model includes brute forcing 2^256, I can't help you. If you're trying to prove that Aleph-one is greater than Aleph-0, perhaps, but the number of atoms in the universe is less than Aleph-0, so it's irrelevant to cryptography or to information security.
People who say "maybe an advance in math will break 2048 bit DHE" are at least theoretically correct. But no advance in math is going to break that RNG. If you can't trust that RNG, you can't send secrets using CTR, GCM, CHACHA, etc. because they will all break using that method.
But both are strictly easier than attacking 100x independently created 256-bit keys. The /dev/random case.
> If you're trying to prove that Aleph-one is greater than Aleph-0
I mean, yeah, that's basically the argument I have. 256-bits of entropy are probably enough for your application, but you cannot under any circumstances tell me that its the same as 25,600 bits of entropy. That's what /dev/random vs /dev/urandom comes down to. For most people in most situations, its almost inconceivable to imagine an application that needs more than 256-bits of true high quality entropy.
EDIT: A POTENTIAL case, which I admit I haven't though too much about... is a 2048-bit RSA key. I assume the RSA key needs to be generated with 2048-bits of true entropy (please correct me if I'm wrong), but the bits-of-security are far less than that, because RSA doesn't scale like other encryption schemes. So your 2048-bits of entropy RSA-key only scales to 128-bits of security.
If your 2048-bits of entropy RSA-key ended up to only have 256-bits of entropy generating it, you're possibly in bad luck (only 16-bits of entropy assuming a similar scaling factor). I'm not a specialist in the math, but... not all cryptographic primitives scale 1-to-1 with the input entropy source.
> But both are strictly easier than attacking 100x independently created 256-bit keys. The /dev/random case.
Both are impossible. Like, 'Solar System turned into thermodynamically optimal computronium fails' impossible. (seriously - '((mass of solar system * (speed of light)^2) / 0.0172 electronvolts ) / (2^256)' for calculations performed at 20C [0], and that evaluates to 5*10^-10. Drop the assumed temperature to 2.75K - the cosmic background temperature - and the energy per computation drops by a factor of several hundred, but that's still not nearly enough)
Or, put another way - if you can bruteforce 2^256, you can do that 100 times. (Even if you encrypt an object 100 times, you'll still only need to do ~2^264 work - not 2^25600)
An RSA-2048 keypair is generated by taking a CSPRNG like the one I proposed, generating 1024 bit numbers, checking them for being a prime number using Miller Rabin [1] until the chance of the number not being prime is below 2^-128 (generating new candidate primes if the current one turns out to be not prime), and then doing it all over again for the other prime. The two 1024 bit probably-primes "p" and "q" are the private key, their product "n" (with the public exponent e=65537) is the public key. Most systems precalculate some derived values used to speed up operations and store them with p and q, but you don't have to [2][3].
The RNG I proposed is absolutely good enough to generate RSA key pairs. There is no benefit to using "true hardware randomness" for generating candidate primes, after the initial pool of 256 bits of entropy has been generated.
1 - https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
2 - https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generat...
Let's put the time involved in perspective.
``` int main() { for (unsigned long long i = 0; i < (((unsigned long long)1) << 35ull); i++) { __asm__ __volatile__ (""); } } ```
this is large enough to remove the relevance of any start up time, and make noise somewhat meaningless.
On my laptop this takes 9 seconds. That's just counting to 2^35. Now let's imagine we're just counting to 2^256. Not even doing the work to break the rng. How long does it take?
2^221 * 9seconds.
Which is approximately 1.397 * 10 ^ 50 times the age of the universe (I think a billion billion billion billion billion times the age of the universe).
That's just counting from 0 to 2^256, not doing anything else at all.
Understand that if you can break a CSPRNG with 2^256 bits of state, you can break:
* The entire WebPKI system, because all you're doing is brute forcing an very high speed 256 bit hash function.
* TLS connections: you're just brute forcing 256bit keys here as well, in the worst case. Fortunately most are still just aes128. That's 6471949087173059816 times faster, so that's only a billion billion billion times the age of the universe.
Note that the numbers involved mean that "making computers faster" and "adding more computers" doesn't making a meaningful difference, because you run into an energy wall - literally more power than a star emits ends up being necessary.
So, please don't just regurgitate nonsense: brute forcing a current 256 bit CSPRNG is not possible, at all. because physics.
So to break it, you have to break the csprng algorithm. But if you can do that, then you can break any of the places the an RNG is used in practice. Eg. you could have a "true" rng seeding crypto, but it doesn't matter because the attacker can just use your algorithm to break the result of your crypto.
Note also the "true" random you get on a computer is fairly restricted - it has both little variance, and also significant bias, so the output has to be merged (hash function that you've broken) and whitened (again, hash function that you've broken). So even if you were trying to rely on "true" random, you're not getting as much "entropy" as you seem to think you are, and you've invented an algorithm that breaks all the massaging used to make it seem more random.
Do you want all of your AES Keys to be generated from one 256-bit random number generator? Or would you feel more comfortable for each AES Key to be independent sources of entropy? Assume all AES Keys are 256-bits for the rest of this post, to keep all encryption targets at 256-bits of security.
If an attacker breaks urandom, they effectively gain the key-generation for all keys that were based on that entropy pool (at least, until its 'entropy fills back up').
So if you're a server handling say, 100-connections per second... and for round-numbers sake, lets say that /dev/urandom generates 256-bits of entropy every second. If you break /dev/urandom for a 1-second interval (ie: you figure out /dev/urandom's 256-bit key for that 1-second interval), you now know all keys to all 100-connections that happened within that second.
If all 100-connections grabbed their own independent sources of entropy (/dev/random), then it wouldn't be possible. Probably because 100-connections per second would block and your hardware wouldn't support it. :-)
But yeah, its a question of "what do you want your server to do when it runs out of entropy". Do you want to just use pseudo-randomness to "fill in the blanks", which increases your attack surface. (All AES-keys you generate within that time period will have weakened security from an entropy perspective). Or would you rather BLOCK, and simply not support that case? (waiting on /dev/random will cause the server to slow down)
Since 256-bits of entropy is such a huge amount of security (if done properly), I think I'm inclined to agree with you. But still, its an engineering choice that has to be made.