1. Seed itself reliably.
2. Do nothing unless seeded.
3. Re-seed itself regularly, for forward secrecy.
4. Have good performance.
How difficult is #1? It's as simple as gathering 128 bits of entropy. If you have 128 bits, you an expand them into an infinite sequence of random numbers, securely, forever.
I think this is the essence of your comment. The topic is important, so it's worth being clear.
Your VM host simply must instantly inject unique entropy into each VM guest instantly on creation, duplication and start. Otherwise you're breaking your own security.
On a recent Linux environment those problems are solved however. Use proper random drivers for your virtualized environment and use getrandom() in your application.
When you duplicate any VM guest, all sensitive key material should be replaced instantly (preferably never copied to begin with, the host should generate and inject fresh key material).
Refilling the entropy pool alone isn't enough when reuse-insecure ciphers like stream ciphers are actively used, for the reasons stated above. Some ciphers are more tolerant of reuse (see AES-GCM vs AES-GCM-SIV).
How? And why 128 only?
The acceptable safe maximum length isn't quite infinite, it's basically 2^64 rounds (not necessarily bits or bytes) for 128 bits of entropy. But that's basically arbitrarily long in practice as anyone cares.
So with original entropy x, evaluate G(x) => x', c. Output the random bits c and repeat with x = x'. The sequence of c is psuedorandom.
k=128 is the key length of the generator. We define an efficient program to be one that runs in some time polynomial in k. How big of a k you need is based on how powerful computers are at present.
So then the question becomes, what's the largest file you can encrypt with a single key? And the answer is any file you want. There's practically no size limit when you're encrypting files.
128 bits is usually the minimum recommended key size, not because of anything to do with the amount of randomness you can produce, but because you always have worry about an attacker guessing your key by brute force. Brute forcing a key is the same as just trying all possible keys to find one that works. (If there's another way to brute force the key, again you have a bad cipher.) We can estimate how big a key needs to be by looking at the fastest computers that exist: https://en.wikipedia.org/wiki/Supercomputer The fastest computer in the world does something like 2^55 operations per second. There are 2^25 seconds in a year, so if we generously assume that checking a key is just one operation, then a supercomputer like that could check about 2^80 keys per year. 128 is just the first nice power of 2 that's much larger than 80.
Often (e.g. in the Signal protocol), a short secret key is extended using a HKDF (RFC 5869) to create enough bits for a symmetric key and an IV or a nonce (and a MAC key if needed).
So for randomness, take 128 bits, use HKDF to extend to 192 bits, use 128 bits of output as AES-128 key, use next 64 bits of output as nonce, use 64 bits counter, produce AES-128(key, nonce||counter) for every value of counter until it overflows as randomness. 2^64 of 2^4 byte blocks is 2^68 bytes of randomness - enough for most purposes. An Intel chip will produce it at 1GB/sec per core.
Though there will still be people doing it for various reasons, one of them "because we can".
I think of this analogy: you re-key/re-seed periodically not because the originally lock gets weaker, but in case someone stole your key without you knowing. Accurate?
After that it's just down to using /dev/urandom[1] or the getrandom syscall (which is the same as using /dev/urandom). Also the getrandom syscall actually has the behavior you're talking about.
[1] http://sockpuppet.org/blog/2014/02/25/safely-generate-random...
mv /dev/random /dev/badrandom
ln -s /dev/random /dev/urandom # is this the right syntax?
Or something like that?1. http://superuser.com/questions/309840/how-can-i-point-dev-ra...
Edit: on boot, first prevent access to /dev/urandom, then symlink it to /dev/random. Then as soon as /dev/random stops blocking, reverse the direction of the symlink. Same improved security, much simpler to use.
1 - try to read from /dev/random.
2 - While 1 has not succeeded, wait and try again
3 - Once it has succeeded, read from /dev/urandom on next reads
There's no stealing with entropy. And once random returns a read the RNG is seeded, period.
I agree the current implementation makes this distinction worthless, but it doesn't have to be. The biggest hurdle is that true entropy is scarce, and thus must be strictly partitioned between users.
A hardware RNG would solve this, but RDRAND not so much. I feel that if consumer hardware is being subverted by TLAs, the RNG would be the most likely avenue of attack. We may even eventually see partitioning of secure systems into deterministic/functional and non-deterministic parts, with the non-deterministic tape being saved for auditing.
First: while I don't know what you mean by "teasing out differences with respect to various oracles", the fact that you have a kernel CSPRNG that your system relies on means that diversity in CSPRNGs is a bad thing. Simply: alternatives to the LRNG lead to multiple single points of failure.
Entropy is not "scarce". In fact, it's infinite and renewable. To generate a practically unbounded number of random bytes from just 16 bytes of starting state entropy, just use those 16 bytes as an AES key, and use it to encrypt an incrementing counter.
urandom only implements computational security, whereas random makes an attempt at information theoretic security (albeit an extremely poor one). Computational security is so practically useful that the difference between the two seems moot, but there still is a valid distinction.
To me, XOR using /dev/random should be usable for a true OTP [0] whereas XOR using /dev/urandom has the security of the effective stream cipher.
[0] (malleability disclaimer, lest you think I'm arguing for the practicalities of "OTP" or something)
We can define our measure of entropy such that the output of AES (/SHA1) qualifies, or such that it does not. The way it is used in the random/urandom distinction, it's clearly not meant to include PRNG output.
They should be completely partitioned pools, and collected entropy that goes out random should never be mixed into the urandom pool. Of course it's likely random still wants whitening, likely resulting in the use of a computationally-secure algorithm.
Practically since it's anyone's guess what the random clients expect, it's probably the right thing to `ln -f urandom random`. Bona fide hardware sources can come up with their own device/daemon to administer and/or stir into the kernel P/RNG. I'm just pointing out that there is a worthwhile distinction they were trying for, despite the engineering pitfalls of trying to make it available!
It seems you would want to slowly change/update the entropy pool to protect against compromise. So can there be a worst-case situation (if you don't block - for the different reason) that your entropy pool is not updating fast enough to recover from compromise. Or the pool update requires so little entropy (compared to what linux is doing with kind of refilling it) that its almost impossible for that to matter?
OTOH, Kroah-Hartmann and Torvalds seemed to approve of my essay ("Myths about /dev/urandom"), so maybe not all hope is lost.
Still, let's not lose perspective here: the Linux random subsystem certainly has its flaws, but it is secure for all practical purposes. Just not convenient.
Why would this be a problem? Read one byte from /dev/random, and observe one of 257 possible values chosen at random. :D
Or is there something I'm not seeing about how reseeding works?
It's very unlikely that a compromise will be temporary. This situation "transient compromise" will never happen. Moreover, once a system is compromised, by definition you cannot trust it until replacing it from a known-good source or backup, at which point, you just start the CSRNG with new entropy.
No system should need or even attempt to recover from a transient compromise, you are just causing a false feeling of security.
Rekeying frequently makes passive attacks way harder, so it makes sense to rekey as a often as you can.
You should generally avoid xor when it comes to untrusted output such as rdrand since it could theoretically control what gets generated and as such could cancel out whatever you're xoring it with (or at least this is the claim AFAIK). It's better to mix it using some other method, e.g. hash or cipher[1].
[1] https://boringssl.googlesource.com/boringssl/+/master/crypto...
This is silly.
There are three problems a kernel CSPRNG needs to address:
1. It needs to seed itself reliably and not provide output when it's not securely seeded.
2. It needs to re-key itself regularly to provide forward secrecy and recovery from attacks.
3. It needs to be performant enough to be used in applications to the exclusion of all other RNGs.
That's it. Once problem (1) is addressed, there is never again for the uptime of the system a concern about the quality or "level" of entropy in the LRNG. DRBGs like this document proposes are effectively stream ciphers (in fact: Salsa20, the new hotness in bulk cipher designs, is essentially a hash DRBG --- and, in the BSDs, a [crappy] stream cipher was the RNG). "Entropy" keys the cipher. The idea that you can "run low" on entropy is the same as the idea that you can "run low" on key. No.
Kernel CSPRNGs do need continually updated entropy pools. But not because their original entropy is depleted! Rather: you want your RNG to be updated so that its "key" changes regularly, so that if your system is compromised transiently, you'll recover.
And, of course, the division between /dev/random and /dev/urandom sabotages goal (3) --- arguably the most important goal. Almost every time you've read about some crypto randomness catastrophe --- from Debian commenting out their RNG and reducing SSH key space to 16 bits, to Bitcoin wallets coughing up private keys by repeating nonces --- you've been reading about userspace RNG failures. People use userspace RNGs because they think the kernel RNG is too slow. And they think the kernel RNG is too slow because they use /dev/random, which obstinately refuses to provide output when --- wait, I'm not dignifying /dev/random: it refuses to provide output at random.