/dev/random – a new approach
lwn.net
lwn.net
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.
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...
Why would this be a problem? Read one byte from /dev/random, and observe one of 257 possible values chosen at random. :D
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?
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.
How? And why 128 only?
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.
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.
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.
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.
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).
Though there will still be people doing it for various reasons, one of them "because we can".
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.
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?
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.
Or is there something I'm not seeing about how reseeding works?
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.
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!
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)
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.
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.
To the extent that any applications exist where a information theoretic RNG was required, this scheme does not provide one. Instead, it continues the to offer an interface that causes confusion and insecurity without an apparent benefit.
Fortuna specifically addresses the problems of entropy estimation that the grandparent comment brings up:
"making any kind of estimate of the amount of entropy is extremely difficult, if not impossible. It depends heavily on how much the attacker knows or can know, but that information is not available to the developers during the design phase."
"Fortuna solves the problem of having to define entropy estimators by getting rid of them."
1: https://www.schneier.com/cryptography/paperfiles/fortuna.pdf
Funny that the term "information theoretic" is used with not even one "theorem" in the linked document.
"By using the primary DRBG to serve /dev/random, the LRNG ensures that each random number generated by the primary DRBG must be backed by an equal amount of entropy that seeded the DRBG. Hence, the data derived from /dev/random is backed by information theoretical entropy."
(page 21 of the PDF documentation)
http://www.2uo.de/myths-about-urandom/
EDIT: or read tptacek's root comment on this very page.
Think of the pool's entropy as a "measure of unpredictability". If the entropy is ten bits, for instance, you'd need at most 1024 guesses to find the pool state.
You should think of the random generator as having two separate and independent parts: the pool itself and the output function.
Inputs are mixed into the pool using a cryptographic function which takes two values: the previous pool state and the input value, and outputs the new pool state. This function thoroughly mixes its inputs, such that a one-bit difference on any of them would result on average to half of the output bits changing, and other than by guessing it's not possible to get from the output back to the inputs.
Suppose you start with the pool containing only zeros. You add to it an input containing one bit of entropy. Around half of the pool bits will flip, and you can't easily reverse the function to get back the input, but since it's only one bit of entropy you can make two guesses and find one which matches the new pool state. Each new bit of entropy added doubles the number of guesses you need to make; but due to the pigeonhole principle, you can't have more entropy than the number of bits in the pool.
To read from the pool, you use the second part, the output function. It again is a cryptographic function which takes the whole pool as its input, mixes it together, and outputs a number. Other than by guessing, it's not possible to get from this output to the pool state.
Now let's go back to the one-bit example. The pool started with zero entropy (a fixed initial state), and got one bit of entropy added. It can now be in one of two possible states. It goes through the output function, which prevents one reading the output from getting back to the pool state. However, since there were only two possible states (one bit of entropy), you can try both and see which one would generate the output you got... and now the pool state is completely predictable, that is, it now has zero bits of entropy again! By reading from the pool, even with the protection of the output function, you reduced its entropy. Not only that, but there were only two possible outputs, so the output itself had only one bit of entropy, no matter how many bits you had asked for.
Now if you read a 32-bit number from a pool with 33 bits of entropy, you can make many guesses and find out a possible pool state. However, again due to the pigeonhole principle, there's on average two possible pool states which will generate the same 32-bit output. Two pool states = one bit. So by reading 32 bits, you reduced the remaining entropy to one bit.
This is important because if you can predict the pool state, you can predict what it will output next, which is obviously bad.
----
Now, why isn't the situation that bad in practice? First, the input entropy counter tends to underestimate the entropy being added (by design, since it's better to underestimate than to overestimate). Second, "by guessing" can take a long enough time to be impractical. Suppose you have a 1024-bit pool, and read 1023 bits from it. In theory, the pool state should be almost completely predictable: there should be only two possible states. In practice, you would have to do more than 2^1000 guesses (a ridiculously large number) before you could actually make it that predictable.
However, that only applies after the pool got unpredictable enough. That's why the new getrandom() system call (which you should use instead of reading /dev/random or /dev/urandom) will always block (or return failure in non-blocking mode) until the pool has gotten enough entropy at least once.
That's the entire point of a DRBG†: to securely incorporate inputs of wildly varying randomness into an RNG whose future outputs are as difficult to predict from past output as keys are to recover from ciphers.
To somehow "predict" the output of the system from its input, you would need to be able to work back from the output of a cryptographic keystream generator back to its key. If you can do that, forget the RNG: you've broken most modern cryptography.
† and even prior to this proposal, that's what the LRNG implemented
If, for instance, the pool has only 256 possible values (8 bits of entropy), perhaps because the system just booted and almost nothing has been added yet to the pool, there will be only 256 possible keys, and only 256 possible output streams. If you have enough of the output (on average around one byte), you can try the 256 possible pool states, and see which one would give you the same output you have. And since now you know both the pool and generator state, the system's entropy is now zero: it's completely predictable.
The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable. Which AFAIK is what the new getrandom() syscall does.
Fortunately, it's easy to store a value which can take one of 2^128 possible states: it's 16 bytes. That's all. That's all you need. That's all you'll ever need.
Take that one value; use it to key a keyed hash or an HMAC or a stream cypher or a block cypher. Encrypt the 16-byte value for 0, then 1, then 2 &c. You will get an effectively infinite sequence of random numbers.
'But wait!' you say, 'maybe I'm worried that I might expose some of that state!' Then just periodically rekey that keyed hash or HMAC or stream cypher or block cypher. There are a number of ways to do that: one possibility would be to hash the current key and the new entropy, but there are other, smarter ways to do it as well.
That's it. That's all you need.
More important: nobody knows if the entropy counter is truly conservative, because nobody knows how to properly count entropy. Linux makes educated guesses by assuming a model of entropy for the inputs (inter-arrival times of events). That's far less solid than the rest of the random subsystem.
For goodness' sake, Fortuna already exists. What happened to "don't invent your own cryptography"?
I'm curious why there still needs to be a distinct /dev/random though. Hasn't history shown that they should really just both point to the same thing? Is there really a need for the difference here? Ditto with the entropy estimation, why is this still a thing?
Page 4: "The new approach implements the modeling of a slow noise source within the LRNG based on the timing of interrupts and allowing other, even fast operating noise sources to contribute entropy. As discussed above for the legacy /dev/random, only the high-resolution time stamps deliver entropy for hardware events and other information processed by the legacy /dev/random implementation hardly have any entropy. This identification is used as a basis that solely the timing of interrupts is used."
"The concept of the LRNG allows the selection of the used DRBG and the backend cipher implementations at compile time."
Is SP800-90A DRBG really state of the art?
According to Wikipedia "the publication contains the specification for four cryptographically secure pseudorandom number generators for use in cryptography." Without Dual-EC it's still three different DRBGs. How good are they? Is there anything better?
The stuff that extends the "state of the art" beyond SP800-90A tends to be system-specific and feature-based. For instance, the "estimators" in the LRNG are an extension to SP800-90A (and a bad idea). Rolling over seed files are another extension.
Thanks. Does it matter which one of the three is then selected? Only one can be a default.
Fortuna also has the benefit of mitigating damage from a compromised generator. If the generator is compromised it's very difficult to rewind the RNG output and perform a history attack (is that even the right word for such a thing?).
This!
Again I think this illustrates the echo chamber some camps can't seem to depart. But I agree with your thinking.
This is an issue I've been thinking about quite a bit. Is there a way to somehow sign a circuit design on silicon and allow devs to check the circuit's integrity?
For example, in the case of a TRNG, the developer can add a "verify" instruction to ensure that the TRNG on the user's CPU is not compromised before executing the RAND instruction. Of course, that's what the dev does, but the signing itself is much more complex.
I've been looking through the literature and I haven't found much to go on. I know it's likely impossible to do given how many layers there are between silicon and machine code, but I'd like to at least give it a try.
The problem of verifying the integrity of embedded silicon (at the microcircuitry level) is one that hasn't really been solved yet. This has been a problem for the DoD since forever.
THEY solved it partially by using US-sourced parts and working with industry to make sure the designs weren't sabotaged or otherwise backdoored. It's still an active concern though.
http://www.dtic.mil/ndia/2014system/16990WedTrack1Shanahan.p...
https://www.schneier.com/blog/archives/2012/05/backdoor_foun...
If you randomly check, say, power usage and latency of the on-board RNG (ideally combined with high-resolution IR recordings of the CPU), it will, at least, be harder for the CPU manufacturer to install a backdoored RNG that is active most of the time (but one that only gets activated after receiving some trigger, say a specific instruction sequence would still be virtually undetectable)
I personally think this is a good approach, as it allows hardware TRNG to increase the quality and quantity of entropy without being able to own the internal generator.
BoringSSL takes a similar approach with rdrand in that it mixes it using the chacha20 stream cipher. The operating system PRNG is used to generate the keys and rdrand is filtered on every call when you need a random number. I don't know what LibreSSL does (it uses chacha20 in some manner) and I'm pretty sure OpenSSL doesn't use rdrand at all unless you ask for it (in which case it will ONLY use rdrand).
$ rngtest -c 200000 -b 2000 < /dev/urandom
.....
rngtest: bits received from input: 4000000032
rngtest: FIPS 140-2 successes: 199848
rngtest: FIPS 140-2 failures: 152
rngtest: FIPS 140-2(2001-10-10) Monobit: 24
rngtest: FIPS 140-2(2001-10-10) Poker: 15
rngtest: FIPS 140-2(2001-10-10) Runs: 60
rngtest: FIPS 140-2(2001-10-10) Long run: 54
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=3.782; avg=63.752; max=82.928)Mibits/s
rngtest: FIPS tests speed: (min=4.559; avg=158.909; max=194.627)Mibits/s
rngtest: Program run time: 83882495 microseconds
rdseed directly gives you the output of a hardware RNG, limited by the rate that hardware RNG produces random bits. rdrand gives you CSPRNG output seeded by rdseed.
I don't know why rdseed was added a generation after rdrand. Whatever the case is you can guarantee that rdrand's internal generator gets reseeded by calling it a certain number of times[2]. You can also wait some amount of time between calls but it's likely faster just to generate more data to force the reseed.
[1] Like Windows it uses AES-256 (AFAIK) in CTR mode as specified in NIST 800-90 or whatever the latest version of that standard is.
[2] the DRNG reseeds automatically after generating 511 128-bit samples (from Intel's drng_samples source package)
Sadly, LavaRand, the connoisseur's choice of internet randomness, is no longer with us:
http://web.archive.org/web/20010926221159/http://lavarand.sg...
That said, here is my little "wwwrand" script, that assumes Google News will return unpredictable and unrepeatable content. You could also throttle curl using --limit-rate to generate more interrupts for strace to log.
nice -n 19 strace -CTiv -ttt curl -LNv https://news.google.com 2>&1 | shasum -a 512