Entropy and the NetBSD Kernel(washbear.neocities.org)
washbear.neocities.org
Entropy and the NetBSD Kernel
https://washbear.neocities.org/entropy.html
36 comments
If you like this sort of thing, here's a zoo of other designs:
* http://aka.ms/win10rng (Windows 10, PDF)
* https://en.wikipedia.org/wiki/Fortuna_(PRNG) (FreeBSD)
* https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/f... (NIST)
* https://github.com/torvalds/linux/blob/master/drivers/char/r... (Linux; I could not find a separate design document as such. Perhaps the best design reference is this block comment at the beginning of the file implementing it)
* http://aka.ms/win10rng (Windows 10, PDF)
* https://en.wikipedia.org/wiki/Fortuna_(PRNG) (FreeBSD)
* https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/f... (NIST)
* https://github.com/torvalds/linux/blob/master/drivers/char/r... (Linux; I could not find a separate design document as such. Perhaps the best design reference is this block comment at the beginning of the file implementing it)
Picking on one point, I think the name of the hardware is a fair thing to chuck in the pool.
As this article says, early in the process you often have several soirces of low quality, and all we can do is hope to get the best we can from anywhere we can. The name and versions of everything attached is fairly horrible entropy, but it doesn't hurt.
As this article says, early in the process you often have several soirces of low quality, and all we can do is hope to get the best we can from anywhere we can. The name and versions of everything attached is fairly horrible entropy, but it doesn't hurt.
Together with the italicized remark I read that as “there is this unnamed platform that does not use RNG but just hashes bunch of arbitrary system parameters and state and calls the result random-enough”. In fact the unnamed OS does not do that and reality is significantly more complex and involves PRNG, but the official documantation for well-known and officially undocumented and unsupported internal get_random()-like API is worded in a way that implies that what it returns is simply MD5 of giant struct containing around hundred of assorted timers, counters and other system state.
Yep, one of the cool things about entropy is that it always increases. If you keep XORing more information into the seed pool, you only ever increase the total entropy.
As long as you use reasonably secure way to add entropy into the pool, ie. don't XOR stuff into some kind of pool buffer but use something that at least partly resembles secure hash even for adding entropy (as using full-blown SHA-x to process interrupt timings and similar high volume low quality entropy sources is not exactly practical due to both performance and synchronization issues).
Also, total entropy is not necessarily the same thing as attacker's uncertainity of the pool's state. The difference seems mostly theoretical, but there are practical issues for both cases of these two quantities beeing wildy different.
Also, total entropy is not necessarily the same thing as attacker's uncertainity of the pool's state. The difference seems mostly theoretical, but there are practical issues for both cases of these two quantities beeing wildy different.
+1 on the mix-with-SHA or something like it paragraph.
Re: Entropy; in a system RNG design, entropy is typically considered relative to an attacker. In some very real sense, the "total entropy" of the system is only the unpredictability of the generator to the most knowledgeable attacker.
Re: Entropy; in a system RNG design, entropy is typically considered relative to an attacker. In some very real sense, the "total entropy" of the system is only the unpredictability of the generator to the most knowledgeable attacker.
I wasn't one of the downvoters, since your actual point is clear and true, but DO NOT EVER USE XOR TO COMBINE ENTROPY! I cannot emphasize this enough - XOR allows malicous entropy sources to cancel out other entropy. Always use a cryptographically secure hash function, especially when adding entropy from RDRAND.
You can't just use naive XOR, but if you take slightly more effort, yes, sure.
I think OpenBSD has an interesting solution to this problem, randomness is saved in a seedfile on shutdown/periodically during runtime, and injected directly into the kernel via boot loader before the kernel loads.
This gives you a quality of randomness as early as possible during kernel boot, and allows you to employ it with kernel structures that are otherwise impossible to modify post-initialization (that say may be required to get "randomness harvesting" working).
This gives you a quality of randomness as early as possible during kernel boot, and allows you to employ it with kernel structures that are otherwise impossible to modify post-initialization (that say may be required to get "randomness harvesting" working).
From the article we're reading:
> On shutdown (these days between shutdowns too, just in case power is lost), the current state of the entropy pool as collected during the lifetime of the system is saved into a file so it can be loaded on next boot. This should include enough sufficiently unpredictable data to give you a pretty good security margin.
> When the file is loaded, it's combined with additional entropy collected during the boot process.
> The first time the system is booted, and early in the boot process, things get more difficult.
> On shutdown (these days between shutdowns too, just in case power is lost), the current state of the entropy pool as collected during the lifetime of the system is saved into a file so it can be loaded on next boot. This should include enough sufficiently unpredictable data to give you a pretty good security margin.
> When the file is loaded, it's combined with additional entropy collected during the boot process.
> The first time the system is booted, and early in the boot process, things get more difficult.
NetBSD's approach is different as the kernel is loading the file, and it has to have "enough" kernel initialized to gain file system access, that is already past the point where many kernel structures can be randomized.
NetBSD's approach to this is pretty much the as *nix have done for a long time.
NetBSD's approach to this is pretty much the as *nix have done for a long time.
See ahoka's sibling comment.
Windows (at least 10) and FreeBSD do the same thing. (Windows 10 does quite a lot of entropy gathering in the boot loader and passes it off to the operating system. There are a number of interesting things in their design that I don't believe any open source operating system yet incorporates; the whitepaper is a worth a read.)
I think now a days “reboots” are a thing of the past. All of my instances scale up and scale down and have a max life of 30 days before they are rebuilt on a patched AMI. I think most stuff is done like that and not real metal boxes anymore.
If you're running in a VM, you are at the mercy of the host, so you may as well ask the host for a random seed. Use other factors if you can, but those are all controllable by a sufficiently determined host.
what do you mean computing life exists outside of containers that exist in a magical void
NetBSD also supports this via the rndseed boot option.
More is being discussed here at mailing list thread https://mail-index.netbsd.org/tech-userlevel/2020/05/02/msg0...
A couple of considerations:
Regarding the hostname thing, the NISP SP800-90Ar1 specs for PRNGs include "personalization strings" as an optional part of the initialization. Lots of other systems have similar parameters. The fundamental idea is that randomness sources are sometimes subject to failure, especially as you ask for more and more random data (e.g., until recently, /dev/random on Linux would block if it "didn't have enough entropy", and there have been plenty of issues related to code NOT CHECKING for short reads). The NIST spec suggests using things like serial numbers, user IDs, MAC addresses, software versions, timestamps, module and applications, even random numbers derived from other sources as parts of the personalization string. The idea is that each PRNG created will always have at least one unique input to it, so you at least avoid repeated outputs if the seeds and the nonces get hosed up.
So there's a case to be made for hauling in low-randomness data, even if it doesn't help accumulate enough randomness. The hostname certainly isn't perfect (think of all those Raspberry Pis with the same hostname), but it doesn't HURT as long as we're honest about what that input is providing (distinction versus randomness).
Also: the author notes that some of the random sources they tested are highly biased. While biased output from a random source isn't GREAT, it isn't necessarily a showstopper. The key thing for security in this context is not a lack of bias, but a lack of predictability. Suppose I have a biased random source, with a 1/3 probability of outputting a 1, and a 2/3 probability of outputting a 0. If there's nobody out there who can predict the NEXT output with probability greater than 2/3 (i.e., it's not backdoored or subject to some nasty attack), then it's just fine as a random source. We just can't treat each bit we read as providing a "full bit" of random into the system. In the example above, you could just seed your 256-bit PRNG with about 280 bits of biased input. Alternatively, you could just do the old "read twice: discard if results match; otherwise take the first value" trick to get an unbiased source.
Also, it's important to remember that "entropy" in these conversations is used in a squishy way, and it's easy to mix up different definitions of the term. Folks talking about "entropy" in the context of PRNGs usually mean unpredictability, unstructuredness, unrecoverability, or some combination thereof. They typically do not mean Shannon entropy, which is essentially a measure of UNIFORMITY of output . If you feed the numbers 0 through 255-- in order-- into an entropy calculator, it will report exactly 8 bits of entropy, even though the input was clearly structured and predictable. That's why I've tried to avoid using the term "entropy" and focus on "random" or "randomness".
As for backdoors-- it's theoretically possible that things like RDRAND or a USB key or whatever can be compromised. Standard, non-dedicated randomness inputs (like keystroke timing, network packet arrival times, disk I/O info, interrupt timing, clock drift, etc.) are still included in OS PRNGs, and PRNG state is periodically updated to fold in that randomness. While it isn't EASY for a hardware backdoor to overcome this, it's theoretically possible, and it only takes a small amount of influence to create some devastating effects. Dan Bernstein wrote an article back in 2014 about the hardware backdoor idea; one very simple suggestion that he made was to simply design cryptosystems to use LESS random data (his Ed25519 system generates nonces deterministically, for instance).
Regarding the hostname thing, the NISP SP800-90Ar1 specs for PRNGs include "personalization strings" as an optional part of the initialization. Lots of other systems have similar parameters. The fundamental idea is that randomness sources are sometimes subject to failure, especially as you ask for more and more random data (e.g., until recently, /dev/random on Linux would block if it "didn't have enough entropy", and there have been plenty of issues related to code NOT CHECKING for short reads). The NIST spec suggests using things like serial numbers, user IDs, MAC addresses, software versions, timestamps, module and applications, even random numbers derived from other sources as parts of the personalization string. The idea is that each PRNG created will always have at least one unique input to it, so you at least avoid repeated outputs if the seeds and the nonces get hosed up.
So there's a case to be made for hauling in low-randomness data, even if it doesn't help accumulate enough randomness. The hostname certainly isn't perfect (think of all those Raspberry Pis with the same hostname), but it doesn't HURT as long as we're honest about what that input is providing (distinction versus randomness).
Also: the author notes that some of the random sources they tested are highly biased. While biased output from a random source isn't GREAT, it isn't necessarily a showstopper. The key thing for security in this context is not a lack of bias, but a lack of predictability. Suppose I have a biased random source, with a 1/3 probability of outputting a 1, and a 2/3 probability of outputting a 0. If there's nobody out there who can predict the NEXT output with probability greater than 2/3 (i.e., it's not backdoored or subject to some nasty attack), then it's just fine as a random source. We just can't treat each bit we read as providing a "full bit" of random into the system. In the example above, you could just seed your 256-bit PRNG with about 280 bits of biased input. Alternatively, you could just do the old "read twice: discard if results match; otherwise take the first value" trick to get an unbiased source.
Also, it's important to remember that "entropy" in these conversations is used in a squishy way, and it's easy to mix up different definitions of the term. Folks talking about "entropy" in the context of PRNGs usually mean unpredictability, unstructuredness, unrecoverability, or some combination thereof. They typically do not mean Shannon entropy, which is essentially a measure of UNIFORMITY of output . If you feed the numbers 0 through 255-- in order-- into an entropy calculator, it will report exactly 8 bits of entropy, even though the input was clearly structured and predictable. That's why I've tried to avoid using the term "entropy" and focus on "random" or "randomness".
As for backdoors-- it's theoretically possible that things like RDRAND or a USB key or whatever can be compromised. Standard, non-dedicated randomness inputs (like keystroke timing, network packet arrival times, disk I/O info, interrupt timing, clock drift, etc.) are still included in OS PRNGs, and PRNG state is periodically updated to fold in that randomness. While it isn't EASY for a hardware backdoor to overcome this, it's theoretically possible, and it only takes a small amount of influence to create some devastating effects. Dan Bernstein wrote an article back in 2014 about the hardware backdoor idea; one very simple suggestion that he made was to simply design cryptosystems to use LESS random data (his Ed25519 system generates nonces deterministically, for instance).
FWIW, the Windows 10 RNG includes (one-time) personalization data that is non-random but maybe unique during initialization. (They don't call it that, but it's the same idea.)
Low-entropy random sources don't hurt but there's not really much point using them unless you have no better options (i.e., jitter entropy for initial seeding on embedded systems).
Better to just use the biased source directly than to make up an ad-hoc de-biasing algorithm. I'm know there are mathy ways to combine imperfect sources and get perfect entropy out, but it adds complexity, which is a risk.
Respect where it is due to DJB, but if Intel wants to compromise your system, it's already got the SMM/IME backdoor; it doesn't need to poison RDRAND. There is sometimes a disconnect between cryptography researchers and cryptography practitioners. I enjoyed and would recommend JPA et al's RWC paper, Too Much Crypto: https://eprint.iacr.org/2019/1492.pdf
Low-entropy random sources don't hurt but there's not really much point using them unless you have no better options (i.e., jitter entropy for initial seeding on embedded systems).
Better to just use the biased source directly than to make up an ad-hoc de-biasing algorithm. I'm know there are mathy ways to combine imperfect sources and get perfect entropy out, but it adds complexity, which is a risk.
Respect where it is due to DJB, but if Intel wants to compromise your system, it's already got the SMM/IME backdoor; it doesn't need to poison RDRAND. There is sometimes a disconnect between cryptography researchers and cryptography practitioners. I enjoyed and would recommend JPA et al's RWC paper, Too Much Crypto: https://eprint.iacr.org/2019/1492.pdf
Oh, there are definitely better ways to de-bias; the read-check-discard construction is meant as a math example, not practical advice. Most of the popular PRNG constructions (for instance, anything in SP800-90A) will integrate things in a much saner fashion (e.g., with a hash or MAC algorithm). I was mainly trying to make the point that a bias in a random bit source doesn't automatically mean that everything is broken and horrible.
The biased/low-entropy point was mainly in relation to a specific case mentioned in the original article (Allwinner embedded ARM systems). I don't know how quickly that particular HWRNG provides data, but if the bias isn't huge, and the random can be read quickly enough, I'd probably argue to include it. Even if it's biased 4-to-1, you can still reach a desired "amount" of randomness (however you're choosing to measure it) pretty quickly.
The biased/low-entropy point was mainly in relation to a specific case mentioned in the original article (Allwinner embedded ARM systems). I don't know how quickly that particular HWRNG provides data, but if the bias isn't huge, and the random can be read quickly enough, I'd probably argue to include it. Even if it's biased 4-to-1, you can still reach a desired "amount" of randomness (however you're choosing to measure it) pretty quickly.
> you could just do the old "read twice: discard if results match; otherwise take the first value" trick to get an unbiased source.
Huh?
If I have a legitimately random source that gives 00, 10 or 11 entirely at random (but never 01 which is why we're filtering it), and you feed it through your proposed process to get a 16-bit number you always get 1111111111111111 which is clearly no sort of random.
Huh?
If I have a legitimately random source that gives 00, 10 or 11 entirely at random (but never 01 which is why we're filtering it), and you feed it through your proposed process to get a 16-bit number you always get 1111111111111111 which is clearly no sort of random.
I suppose I should have made it explicit that this construction relies on the unpredictability of SINGLE-bit reads. I had actually considered some wording about that and the independence of each sample, but figured I'd sound pedantic.
Under the system you outlined, that single-bit unpredictability condition doesn't hold, so you're right that the construction totally breaks down. Given a starting bit of 0, you can predict the next bit with absolute certainty.
For something like your random source, it would be best to just skip every other bit and look at the result as a biased bit generator. In that case, the construction works: you would have (0, 1) and (1, 0) each happening with probability 2/9, while the matching sets (0, 0) and (1, 1) happen with a combined probability 5/9. That gives (0, 1) and (1, 0) as equally likely outputs, so just consistently take one of them, and you have an unbiased source.
But what you mention DOES have some relevance to bit generators, too. One of the Bernstein scenarios deals with a hypothetical backdoored RDRAND instruction on x86. The basic idea is that the instruction is designed with some understanding of the system the values will be used in, and doing a short brute-force to see which value would fix the first four bits to a desired pattern. With the "sample, check unmatched, take first" construction, that pattern would be SUPER easy to fix.
Under the system you outlined, that single-bit unpredictability condition doesn't hold, so you're right that the construction totally breaks down. Given a starting bit of 0, you can predict the next bit with absolute certainty.
For something like your random source, it would be best to just skip every other bit and look at the result as a biased bit generator. In that case, the construction works: you would have (0, 1) and (1, 0) each happening with probability 2/9, while the matching sets (0, 0) and (1, 1) happen with a combined probability 5/9. That gives (0, 1) and (1, 0) as equally likely outputs, so just consistently take one of them, and you have an unbiased source.
But what you mention DOES have some relevance to bit generators, too. One of the Bernstein scenarios deals with a hypothetical backdoored RDRAND instruction on x86. The basic idea is that the instruction is designed with some understanding of the system the values will be used in, and doing a short brute-force to see which value would fix the first four bits to a desired pattern. With the "sample, check unmatched, take first" construction, that pattern would be SUPER easy to fix.
In context, they were talking about the specific case of a source that outputs 33% 1s and 67% 0s, with no correlation between successive outputs. For the general case of a entropy source that's (not provably not) biased in some arbitary way that you don't know about, you obviously need a cryptographically secure hash function.
Buy a hardware source of entropy.
If you own an Intel CPU made in the last decade? 15 years? you've already got one. PowerPC's got the DARN instruction as well.
What Theodore Ts'o said about it:
https://web.archive.org/web/20180611180213/https://plus.goog...
(This Theodore Ts'o: https://en.wikipedia.org/wiki/Theodore_Ts%27o)
https://web.archive.org/web/20180611180213/https://plus.goog...
(This Theodore Ts'o: https://en.wikipedia.org/wiki/Theodore_Ts%27o)
You obviously should never use a hardware module as your only source of entropy. What loeg is pointing out is that if you need a hardware RNG (in addition to your seedfile, RTC, environmental noise, etc), a modern CPU fills that particular role in the SRNG system without any additional hardware.
I have a great deal of respect for Ted Ts'o but I don't think this concern has much merit. If your CPU vendor is an attacker, there are much more trivial ways for the manufacturer to break your security in hard to detect ways.
Hardware has random failures, software only systematic ones.
Aging is an issue, as is EMR and power supply.
Aging is an issue, as is EMR and power supply.
this is an odd conclusion to make from my article, given that the entire point of it is to assert the difficulty in establishing trust and the lack of wisdom in relying on a single source
jbirer(2)
While a TRNG is fundamentally necessary for initial entropy, it is generally a good idea to mix as much other randomness as possible to reduce your dependency on a single source, in case that single source turns out to be biased. So I agree with the author that there is still some value in the "low value" options.