Comment by wolf550e
7 years ago
True about no way to deterministically get more than 256 bits of entropy out of 256 bits of initial entropy, but the requirements are to run wireguard, ssh, tls, generate web app session cookies. All those, I believe, would be satisfied by using a urandom which is implemented the way I described. What real use case has a requirement of more than 256 bits of "real" entropy?
Note that the real linux urandom is not as simple as I described, and djb's proposed key erasure RNG [1] is not as simple as I described. My design was just to talk about "draining" of the entropy.
> All those, I believe, would be satisfied by using a urandom which is implemented the way I described.
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.
I would be comfortable using AES keys generated by my algorithm, even though I would prefer djb's proposed key erasure RNG I linked above.
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.
> If the attacker managed to read the inner state of your RNG, you need to rotate all keys.
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.
7 replies →