H. Peter Anvin's educated guess was that some MSR flag, that has the effect of controlling this instruction, is not being saved and restored in the processor across a suspend, and the result is a processor state where it signals that the instruction is succeeding but it is not actually returning random values.
Sounds like a bit of code which was hard to trigger the negative test and therefore the fallback failed to work properly.
Not sure how the kernel devs generally go about testing the “this virtually never happens” code paths without adding debug switches to every unhappy path.
Certainly I doubt they are using DI/IoC to wrap an interface to RDRAND which allows unit testing the failure modes.
At least the result is a failure to generate a key, not a compromised key.
> At least the result is a failure to generate a key, not a compromised key.
In fact, the result is a compromised key -- the bug report is due to colliding "globally unique" identifies generated through a flawed random gathering process.
The 'edit-compile-run-debug' cycle is so expensive, chip design is all about simulation.
Chip vendors, and the tools they use to design them, actually do a significant amount of work for error cases. This is important not just for correctness, but for production yield, reliability, temperature and radiation hardness, etc. As chips get larger and more dense this becomes more and more important.
i don't see any reason to not xor rdrand output with a prng if rdrand is available. please enlighten us why you think otherwise as i'm really interested in assumptions that lead to this conclusion.
Do you mean if a PRNG is available? Because the answer is obvious if RDRAND is available: you don't do that because sometimes it fails, failure is almost always catastrophic but sublte, and CSRPNGs are not a bottleneck in almost all cases.
Is there a good reason this doesn't just use urandom/getrandom? This doesn't look like it's in the "we're so early in boot I haven't restored the random seed yet" case, for example.
BTW, the reason we use RDRAND in some cases instead of getrandom() [which we use in many others] is that we need to generate uuids early on (since every service we starts gets one passed, the "invocation ID", and for other stuff too), but getrandom complains in dmesg or blocks if we call it before the pool is initialized. Since systemd is one of the earliest programs that runs and thus very likely comes into contact with an uninitialized pool we attempt to avoid that by using RDRAND when generating uuids, since it should be good enough for that, as the usecase needs a "mid-quality" rng source: not crypt quality and not totally guessable either.
Worst case, they could run RDRAND in a loop and write() it into /dev/random until getrandom() is unblocked. Then they're still using the ordinary kernel random device, more or less. They wouldn't have these catastrophic collisions due to near-zero entropy.
For the lazy, this is a link to a comment by Theodore Ts'o, kernel dev, who says:
> I am so glad I resisted pressure from engineers working at Intel to let /dev/random in Linux rely blindly on the output of the RDRAND instructure. Relying solely on an implementation sealed inside a chip and which is impossible to audit is a BAD idea. Quoting from the article...
Theodore Ts'o is maintainer of the ext filesystems (particularly ext4), as well as, IIRC, /dev/random and other CSRNG related components of the kernel.
Theodore Ts'o is responsible for perpetuating the myth that entropy/randomness can run out, leading systemd (and other software) to do crazy things, such as trying to use RDRAND, to avoid "drain[ing] randomness from the kernel pool". The bugs and security vulnerabilities resulting from this myth probably neutralize the benefit that came from from his resistance to RDRAND in the kernel.
> Given that RDRAND is allowed to fail, it seems to me that you should either try it only once, or only a few times, before falling back to whatever code is used when RDRAND is not implemented.
... which is what the systemd code actually does. The problem is that there appears to be a possible AMD processor state, caused by suspend+resume, where the instruction succeeds but the data returned are not in fact random.
There is no mention anywhere, in this thread nor the one from 2014, of it returning non-random data from the issue reporters, just assumptions from onlookers.
Oh, this could be really bad. I wonder if any private keys are compromised this way - would certainly be nice to know what rdrand is returning if it isn’t random data.
Sure it does... read all the posts. Also read all the history.
Also read this from 2013
"
I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction... Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea.
"
And this is why cryptography has increasingly reduced its reliance on randomness. Strong CSPRNG that only need a single seed to be secure, signing constructions that use deterministic hashes, deterministic derived keys, DAE-secure ciphers that fail-safe when IVs are re-used, etc.
Randomness is definitely something we took for granted for too long.
Suspend/resume seems to be the cause of a whole host of bugs; I run into obnoxious suspend problems frequently on all platforms except maybe Windows. It's so common that I've pretty much stopped using suspend on most of my machines. It's a bit inconvenient to power down / power up things each day, but I'd rather deal with that than have intermittent wifi issues, display problems, etc.
I consulted once for a hospital that was experience seemingly random network outages. After a few questions with the staff there it seemed to happen whenever a person stepped away from their windows (Lenovo) workstations for too long. Say, after lunch or breaks. After a wireshark of the network I determined it was a network card driver that was causing a broadcast flood on the network from multiple points for stations with the same driver version. While not the fault of Windows (I dont think anyways, as an update of the driver fixed the issue) your comment did remind me of this experience.
Bet the vendor made sure the drivers "worked" for suspend/resume, but only from the user point of view.
I may have just been lucky with Windows on my particular hardware. A quick search turns up a bunch of different problems. I think suspend/resume may just be a particularly difficult thing to get right.
Well, not handling collisions helps a lot with exposing bad CSPRNGs. If they (and e.g. OpenSSH as mentioned in the original 2014 bug report) did handle collisions, it could've remained unnoticed.
There shouldn't be collisions. I mean that really: if you see a collision it's so much more likely that your computer / program / source of randomness is faulty [as in this case] than that the two random numbers collided that it's not worth considering the collision case.
RDRAND is not guaranteed to always succeed (and never was). You’re supposed to retry on failure.
(Although linked in that thread systemd code has fallback anyway, so I’m not sure how it fails at all).
Edit: not to mention that it’s better just to not use it, ever. Quite sane and sensible thing.
The instruction is signalling success, but returning FFFFFFFFFFFFFFFF as the random value.
* https://github.com/systemd/systemd/issues/11810#issuecomment...
H. Peter Anvin's educated guess was that some MSR flag, that has the effect of controlling this instruction, is not being saved and restored in the processor across a suspend, and the result is a processor state where it signals that the instruction is succeeding but it is not actually returning random values.
* https://bugzilla.kernel.org/show_bug.cgi?id=85911#c4
> The instruction is signalling success
Let’s wait for clarifications how that person has done the tests.
However: the bug is about systemd failing to get entropy, not getting nonsense entropy.
6 replies →
Sounds like a bit of code which was hard to trigger the negative test and therefore the fallback failed to work properly.
Not sure how the kernel devs generally go about testing the “this virtually never happens” code paths without adding debug switches to every unhappy path.
Certainly I doubt they are using DI/IoC to wrap an interface to RDRAND which allows unit testing the failure modes.
At least the result is a failure to generate a key, not a compromised key.
> Sounds like a bit of code which was hard to trigger the negative test and therefore the fallback failed to work properly.
No; it turns out that's giving systemd too much credit (sadly). See [1].
The problem appears to be that RDRAND was signalling success, but producing a nonrandom value. This is bad and a violation of the specification.
Can't speak to Linux kernel development, and in this particular case, that isn't the problem.
The linked bug involves systemd using the world's worst random number generator. A security engineer goes into more detail on this twitter thread[1]: https://twitter.com/FiloSottile/status/1125840275346198529 (or unrolled: https://threadreaderapp.com/thread/1125840275346198529.html?... ).
> At least the result is a failure to generate a key, not a compromised key.
In fact, the result is a compromised key -- the bug report is due to colliding "globally unique" identifies generated through a flawed random gathering process.
4 replies →
The 'edit-compile-run-debug' cycle is so expensive, chip design is all about simulation.
Chip vendors, and the tools they use to design them, actually do a significant amount of work for error cases. This is important not just for correctness, but for production yield, reliability, temperature and radiation hardness, etc. As chips get larger and more dense this becomes more and more important.
Single Event Upset (where one bit flips) is an example of the type of error. https://en.wikipedia.org/wiki/Single_event_upset
Virtual machines perhaps.
To be fair from that thread I can't infer whether they check if the call succeeded. It might very well be it returns success but still yields -1.
i don't see any reason to not xor rdrand output with a prng if rdrand is available. please enlighten us why you think otherwise as i'm really interested in assumptions that lead to this conclusion.
Do you mean if a PRNG is available? Because the answer is obvious if RDRAND is available: you don't do that because sometimes it fails, failure is almost always catastrophic but sublte, and CSRPNGs are not a bottleneck in almost all cases.
2 replies →
So - are they not checking for error in this case, and using a value anyway?
They are checking for an error and there is none, but the value returned is bogus (always the same, causing collisions).
Is there a good reason this doesn't just use urandom/getrandom? This doesn't look like it's in the "we're so early in boot I haven't restored the random seed yet" case, for example.
No. There's a bad reason though. Want to guess what? https://github.com/systemd/systemd/blob/master/src/basic/ran...
Yes, the old "draining entropy" fallacy.
Why do you say draining entropy is a fallacy? It is certainly true that entropy recorded from I/O sources accumulates at a very limited rate.
21 replies →
Quoting from https://github.com/systemd/systemd/issues/11810#issuecomment...
BTW, the reason we use RDRAND in some cases instead of getrandom() [which we use in many others] is that we need to generate uuids early on (since every service we starts gets one passed, the "invocation ID", and for other stuff too), but getrandom complains in dmesg or blocks if we call it before the pool is initialized. Since systemd is one of the earliest programs that runs and thus very likely comes into contact with an uninitialized pool we attempt to avoid that by using RDRAND when generating uuids, since it should be good enough for that, as the usecase needs a "mid-quality" rng source: not crypt quality and not totally guessable either.
Why not use getrandom() with GRND_NONBLOCK?
Worst case, they could run RDRAND in a loop and write() it into /dev/random until getrandom() is unblocked. Then they're still using the ordinary kernel random device, more or less. They wouldn't have these catastrophic collisions due to near-zero entropy.
2 replies →
Or better yet, the getrandom syscall, which has better semantics and avoids the filesystem.
I mentioned getrandom.
I'd love to read a "cryptographic doom principle"-esque latacora blog post on all the failures over the years of not using your OS provided CSRNG.
https://sockpuppet.org/blog/2014/02/25/safely-generate-rando...
https://news.ycombinator.com/item?id=6336505
For the lazy, this is a link to a comment by Theodore Ts'o, kernel dev, who says:
> I am so glad I resisted pressure from engineers working at Intel to let /dev/random in Linux rely blindly on the output of the RDRAND instructure. Relying solely on an implementation sealed inside a chip and which is impossible to audit is a BAD idea. Quoting from the article...
Theodore Ts'o is maintainer of the ext filesystems (particularly ext4), as well as, IIRC, /dev/random and other CSRNG related components of the kernel.
Thank you, Theodore Ts'o.
Theodore Ts'o is responsible for perpetuating the myth that entropy/randomness can run out, leading systemd (and other software) to do crazy things, such as trying to use RDRAND, to avoid "drain[ing] randomness from the kernel pool". The bugs and security vulnerabilities resulting from this myth probably neutralize the benefit that came from from his resistance to RDRAND in the kernel.
8 replies →
Note that the corresponding kernel bug was reported already in 2014.
https://bugzilla.kernel.org/show_bug.cgi?id=85911
Later in the thread:
> Given that RDRAND is allowed to fail, it seems to me that you should either try it only once, or only a few times, before falling back to whatever code is used when RDRAND is not implemented.
... which is what the systemd code actually does. The problem is that there appears to be a possible AMD processor state, caused by suspend+resume, where the instruction succeeds but the data returned are not in fact random.
There is no mention anywhere, in this thread nor the one from 2014, of it returning non-random data from the issue reporters, just assumptions from onlookers.
1 reply →
The other problem is that systemd's fallback is a non-random PRNG.
1 reply →
Oh, this could be really bad. I wonder if any private keys are compromised this way - would certainly be nice to know what rdrand is returning if it isn’t random data.
Catchy title. Nowhere it says it returns non-random data. It just fails.
Sure it does... read all the posts. Also read all the history.
Also read this from 2013 " I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction... Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea. "
And this https://www.theregister.co.uk/2013/09/10/torvalds_on_rrrand_...
So, uh, this isn't news, and isn't limited to AMD.
Sure it'd be nice to fix.
1 reply →
And this is why cryptography has increasingly reduced its reliance on randomness. Strong CSPRNG that only need a single seed to be secure, signing constructions that use deterministic hashes, deterministic derived keys, DAE-secure ciphers that fail-safe when IVs are re-used, etc.
Randomness is definitely something we took for granted for too long.
Suspend/resume seems to be the cause of a whole host of bugs; I run into obnoxious suspend problems frequently on all platforms except maybe Windows. It's so common that I've pretty much stopped using suspend on most of my machines. It's a bit inconvenient to power down / power up things each day, but I'd rather deal with that than have intermittent wifi issues, display problems, etc.
I consulted once for a hospital that was experience seemingly random network outages. After a few questions with the staff there it seemed to happen whenever a person stepped away from their windows (Lenovo) workstations for too long. Say, after lunch or breaks. After a wireshark of the network I determined it was a network card driver that was causing a broadcast flood on the network from multiple points for stations with the same driver version. While not the fault of Windows (I dont think anyways, as an update of the driver fixed the issue) your comment did remind me of this experience.
Bet the vendor made sure the drivers "worked" for suspend/resume, but only from the user point of view.
I may have just been lucky with Windows on my particular hardware. A quick search turns up a bunch of different problems. I think suspend/resume may just be a particularly difficult thing to get right.
Wow, so when would be the worst time to suspend your computer?
The only time I imagine this, is when generating a private key for a production environment.
My reading is that systemd uses the cryptographically secure rng to generate a unique id for a filename, and doesn't handle collisions properly.
sigh
Well, not handling collisions helps a lot with exposing bad CSPRNGs. If they (and e.g. OpenSSH as mentioned in the original 2014 bug report) did handle collisions, it could've remained unnoticed.
There shouldn't be collisions. I mean that really: if you see a collision it's so much more likely that your computer / program / source of randomness is faulty [as in this case] than that the two random numbers collided that it's not worth considering the collision case.
3 replies →
But it's cheaper!