6 ms·

Entropy and the NetBSD Kernel

43 points by jayp1418 6y ago

als0 6y ago
> My goal was to ensure that we have collected from as many potential sources of randomness as possible to ensure a quality initial seed for userspace random number generators. So, it includes everything, including sources considered "low value", like interrupt timings. 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.
CJefferson 6y ago
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.
- libeclipse 6y ago
  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.
  - dfox 6y ago
    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.
    - loeg 6y ago
      +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.
  - loeg 6y ago
    You can't just use naive XOR, but if you take slightly more effort, yes, sure.
  - a1369209993 6y ago
    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.
- dfox 6y ago
  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.
jbirer 6y ago
I liked the article but I did not like that the author ended it with "im a chick". Gender is irrelevant to tech and we should avoid emphasizing things that distract from it and bring us personal attention.
- blandflakes 6y ago
  I think it might say something about your priorities that the word that stands out to you in the conclusion is "chick".
- metalliqaz 6y ago
  Rather than downvote or try to dunk on you, I will give an honest response that might be worth your consideration. The author concludes by helpfully pointing out that the above article is not written by a security expert and thus should not be relied upon for serious security matters without additional study. She chose a lighthearted and slightly deprecating, "I'm just some hacker chick" to do so. It's pretty normal for a blog. Try and picture a slightly different scenario: "I'm just some hacker dude." In this situation, it's very likely that you wouldn't have looked twice at the sentence and would have skimmed to the end of the article without any concern whatsoever. You wouldn't have bothered to post about how the article should just say "hacker" without any further qualification. That's called the status quo. What is "normal" doesn't seem like a personal or political bias, but it is. It's the slightest reinforcement of that status quo. A little bit every day. Something that strikes you as different might seem as an affront, but in reality it is no more than an inclusion of another person's perspective that hasn't been exposed much in the culture. It's not better or worse, it's just different. You can test for this. In this case, replace "chick" with "dude" and see how it looks. If it doesn't appear to have an agenda that way, then you are just running up against an internal bias.
  - washbear 6y ago
    thank you :)
throwaway2048 6y ago
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).
- ahoka 6y ago
  NetBSD also supports this via the rndseed boot option.
- mlyle 6y ago
  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.
  - throwaway2048 6y ago
    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.
    - loeg 6y ago
      See ahoka's sibling comment.
- flatiron 6y ago
  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.
29athrowaway 6y ago
Buy a hardware source of entropy.
- loeg 6y ago
  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.
  - 29athrowaway 6y ago
    What Theodore Ts'o said about it: https://web.archive.org/web/20180611180213/https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J https://web.archive.org/web/20180611180213/https://plus.goog... (This Theodore Ts'o: https://en.wikipedia.org/wiki/Theodore_Ts%27o https://en.wikipedia.org/wiki/Theodore_Ts%27o)
    - a1369209993 6y ago
      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.
    - loeg 6y ago
      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.
- Tomte 6y ago
  Hardware has random failures, software only systematic ones. Aging is an issue, as is EMR and power supply.
- washbear 6y ago
  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
loeg 6y ago
If you like this sort of thing, here's a zoo of other designs: * http://aka.ms/win10rng http://aka.ms/win10rng (Windows 10, PDF) * https://en.wikipedia.org/wiki/Fortuna_(PRNG) https://en.wikipedia.org/wiki/Fortuna_(PRNG) (FreeBSD) * https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/f... (NIST) * https://github.com/torvalds/linux/blob/master/drivers/char/random.c#L55-L307 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)
cipher_314159 6y ago
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).
jayp1418 6y ago
More is being discussed here at mailing list thread https://mail-index.netbsd.org/tech-userlevel/2020/05/02/msg012333.html https://mail-index.netbsd.org/tech-userlevel/2020/05/02/msg0...

43 points by jayp1418 6y ago

als0 6y ago

> My goal was to ensure that we have collected from as many potential sources of randomness as possible to ensure a quality initial seed for userspace random number generators. So, it includes everything, including sources considered "low value", like interrupt timings. 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.

CJefferson 6y ago

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.

libeclipse 6y ago
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.
- dfox 6y ago
  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.
  - loeg 6y ago
    +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.
- loeg 6y ago
  You can't just use naive XOR, but if you take slightly more effort, yes, sure.
- a1369209993 6y ago
  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.
dfox 6y ago
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.

jbirer 6y ago

I liked the article but I did not like that the author ended it with "im a chick". Gender is irrelevant to tech and we should avoid emphasizing things that distract from it and bring us personal attention.

blandflakes 6y ago
I think it might say something about your priorities that the word that stands out to you in the conclusion is "chick".
metalliqaz 6y ago
Rather than downvote or try to dunk on you, I will give an honest response that might be worth your consideration. The author concludes by helpfully pointing out that the above article is not written by a security expert and thus should not be relied upon for serious security matters without additional study. She chose a lighthearted and slightly deprecating, "I'm just some hacker chick" to do so. It's pretty normal for a blog. Try and picture a slightly different scenario: "I'm just some hacker dude." In this situation, it's very likely that you wouldn't have looked twice at the sentence and would have skimmed to the end of the article without any concern whatsoever. You wouldn't have bothered to post about how the article should just say "hacker" without any further qualification. That's called the status quo. What is "normal" doesn't seem like a personal or political bias, but it is. It's the slightest reinforcement of that status quo. A little bit every day. Something that strikes you as different might seem as an affront, but in reality it is no more than an inclusion of another person's perspective that hasn't been exposed much in the culture. It's not better or worse, it's just different. You can test for this. In this case, replace "chick" with "dude" and see how it looks. If it doesn't appear to have an agenda that way, then you are just running up against an internal bias.
- washbear 6y ago
  thank you :)

throwaway2048 6y ago

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).

ahoka 6y ago
NetBSD also supports this via the rndseed boot option.
mlyle 6y ago
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.
- throwaway2048 6y ago
  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.
  - loeg 6y ago
    See ahoka's sibling comment.
flatiron 6y ago
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.

29athrowaway 6y ago

Buy a hardware source of entropy.

loeg 6y ago
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.
- 29athrowaway 6y ago
  What Theodore Ts'o said about it: https://web.archive.org/web/20180611180213/https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J https://web.archive.org/web/20180611180213/https://plus.goog... (This Theodore Ts'o: https://en.wikipedia.org/wiki/Theodore_Ts%27o https://en.wikipedia.org/wiki/Theodore_Ts%27o)
  - a1369209993 6y ago
    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.
  - loeg 6y ago
    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.
Tomte 6y ago
Hardware has random failures, software only systematic ones. Aging is an issue, as is EMR and power supply.
washbear 6y ago
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

loeg 6y ago

If you like this sort of thing, here's a zoo of other designs: * http://aka.ms/win10rng http://aka.ms/win10rng (Windows 10, PDF) * https://en.wikipedia.org/wiki/Fortuna_(PRNG) https://en.wikipedia.org/wiki/Fortuna_(PRNG) (FreeBSD) * https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/f... (NIST) * https://github.com/torvalds/linux/blob/master/drivers/char/random.c#L55-L307 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)

cipher_314159 6y ago

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).

jayp1418 6y ago

More is being discussed here at mailing list thread https://mail-index.netbsd.org/tech-userlevel/2020/05/02/msg012333.html https://mail-index.netbsd.org/tech-userlevel/2020/05/02/msg0...