RDRAND on AMD Ryzen 9 5900X is flakey
github.com
github.com
[1] - https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...
[2] - https://linuxreviews.org/RDRAND_stops_returning_random_value...
Windows doesn't use RDRAND.
Well, first problem is using RDRAND in this case. RDRAND isn't meant for seeds, its for a random number.
If you're seeding something, you're supposed to use RDSEED, which has more guarantees about seeding / entropy behavior. I don't think RDRAND was ever intended to be used as an entropy source.
(Think of it this way: RDSEED is kinda like /dev/random, while RDRAND is kinda-like /dev/urandom)
------
RDRAND is an older instruction than RDSEED. So that then brings up the question: what is the proper startup behavior of systems without RDSEED but with RDRAND? Well, since RDRAND never had entropy guarantees, I guess its up to other sources of entropy (see clock-entropy, such as RDTSC).
RDTSC isn't a source of entropy, its just a clock. But as a GHz-level precise timer, it can be used to capture entropy from some other source that does have time-based entropy. (IE: hard drive response rates, or something).
Will the hard drive respond in 10,000,000 clock ticks? Or 10,000,020 clock ticks? That's a source of entropy, a bad one, but maybe you have enough hard drive I/O going on that you can get enough entropy to boot up Systemd.
EDIT: Hmm... hard drives may not be on all systems. In that case, DRAM-latency could possibly be the answer. DRAM refreshes on a regular basis, locking the CPU out temporarily. As such, the amount of time it takes to access data from DRAM is actually somewhat random (in the scope of a GHz clock anyway). Maybe that could be used as an entropy-source of last resort? (as long as RDTSC exists anyway).
>you're right, after I've generated many randoms, I was able to get collisions.
RDRAND() = 0x0081da17 RDRAND() = 0x0081da17 RDRAND() = 0x0178d2ea RDRAND() = 0x0178d2ea RDRAND() = 0x02a91db5 RDRAND() = 0x02a91db5 RDRAND() = 0x06c4385b RDRAND() = 0x06c4385b RDRAND() = 0x095d1bf8 RDRAND() = 0x095d1bf8 RDRAND() = 0x0990b335 RDRAND() = 0x0990b335 RDRAND() = 0x0ab033e4 RDRAND() = 0x0ab033e4 RDRAND() = 0x0ac21fae RDRAND() = 0x0ac21fae RDRAND() = 0x0d39390b RDRAND() = 0x0d39390b RDRAND() = 0x0df2f5ce RDRAND() = 0x0df2f5ce RDRAND() = 0x109e5c8a RDRAND() = 0x109e5c8a
https://github.com/systemd/systemd/issues/18184#issuecomment...
>> If you can, please try it without using the C intrinsic. I have seen multiple compiler bug reports--https://patchwork.ozlabs.org/project/gcc/patch/2012052017042... is the easiest to find--that indicate that the intrinsics don't always return the right value.
Hypothetically, the sequence discussed there could be a compiler-bug, unrolling the loop and failing to treat the results of RDRAND as volatile.
So... yeah. Lets not overcomplicate things, but lets not undercomplicate things either. Without an actual disassembly of the code posted, there's no proof yet.
Birthday paradox says that you'll only need 2^16 (65,536) runs before you get a collision. 64-bit would have a collision in one in 2^32 (4-billion). With 2000 x 10 tests (== 20,000 tests per run), there's a pretty high chance of a collision actually.
There's a lot of issues complicating the testing of something like this. I'm sure the core fact (that RDRAND might be doing something wrong) is there. But to properly vet all issues and actually get to the bottom of this bug will take some effort.
If that is case, maybe RDRAND shouldn't be used for uniqueness.
The intrinsic used is the 32-bit version of RDRAND, which is... suboptimal... for a test like this. As you've noted.
Even then, RDRAND has no entropy guarantees (again: see my top comment about RDSEED vs RDRAND).
the thing about randomness is you can get two 0x00 answers in a row and they are 100% valid. Using random numbers for something which required Unique numbers is crazy.
The state of "we somehow generated two identical UUIDs" cannot be prevented in the real world. You can only reduce the chance to acceptable levels.
Compared to the risks that are accepted in basically all devices, the danger from using big random numbers is negligible. Which makes it not crazy to do.
And everyone runs on unreliable hardware.
So yes, I did compare them. Do you have a reason I shouldn't?
If cosmic rays will cause one collision per decade, and "allowed" random collisions will cause one collision per million years, then why care about the increase in risk?
And let's be clear. This github issue is not happening because of using truly random numbers to generate full-size UUIDs. The problem is something else.
In more precise mathematical language, RDRAND isn't meant for random numbers, it's for an arbitrary number.
That github issue contains a bunch of people who aren't even sure whether their methodology makes any sense, yet HN is already taking the title as a foregone conclusion.
In fact the current consensus on that github issue (for probably the next 10 minutes) is "it seems RDRAND is fine after all".
Let the poor people conclude their research before you go and make a big deal out of it. You will cause them great embarrassment if it turns out the cause was something less spectacular.
Thank you.
https://github.com/systemd/systemd/issues/18184#issuecomment...
https://github.com/systemd/systemd/issues/18184#issuecomment...
https://github.com/systemd/systemd/issues/18184#issuecomment...
edit: this was in reply to the _original_ parent comment, before it was edited, where they asked for a link to the comments stating RDRAND looked fine.
frustrating.
That said it's good that the faulty RDRAND was discovered. As pointed out this isn't the first time processors (AMD particular) have had such issues. Do we need to just be skeptical of this and run RDRAND tests every time a new processor comes out? Or perhaps even each microcode update?
[1] https://www.youtube.com/watch?v=aWmLWx8ut20
[2] https://www.openbsd.org/papers/hackfest2014-arc4random/index...
Yes and no.
Yes, OpenBSD is not vulnerable to this failure mode. But no, it's only because OpenBSD made assumptions that systemd couldn't.
The problem is not how well the random system performs once it started, but simply what to do when it's not initialized yet during early boot. From Page 20: Kernel initialization from boot, OpenBSD's initialization sequence is:
1. If available, use rdrand to generate random seeds.
2. Read random seed file from the disk, saved from the previous boots or installation, very early by the bootloader.
3. Read the Stack Protector cookie from the kernel binary, by the bootloader.
4. Mix them together. The pool is initialized at this point.
5. Keep collecting entropy from various sources of randomness, such as interrupts.
Nice, it ensures that you always get a initialized entropy pool, and hides all complexity away from the userspace. But do note that (2) and (3) provides no security during the first early boot if the same OS image is replicated across many machines.
---
Now what about Linux?
1. If available...
- use rdrand to generate random seeds. It's optional and can be disabled by the user.
- use hardware random number generators and TPMs, but only if they're compiled into the kernel (or loaded early enough) and trusted by the user.
- use the in-kernel jitter entropy collector, "a modern out-of-order CPU, even quite simple loops show a fair amount of hard-to-predict timing variability." But only available since Linux 5.3 released in 2019.
2. Read random seed file from the disk, saved from the previous boots. But it's the responsibility of the userspace to do that, this is problematic for systemd.
- systemd needs a source of randomness at an earlier time, before the entropy pool is seeded by the file. How did OpenBSD solve it? Instead of loading it after boot in userspace, OpenBSD loads the file early, really early, via the bootloader.
- systemd doesn't trust the file. The file is read, but by default, its entropy is not credited, because systemd doesn't want to take the responsibility if someone accidentally replicated the random file across millions of machines via a system image (OpenBSD seems to be okay with the lack of protection of image replication, but systemd is more cautious, probably because it has zero control over the rest of the system). As a result, the system may block at step 4 (entropy collection) during boot for a long time.
3. If Latent Entropy GCC plugin is used, Linux kernel can use entropy embedded in the kernel binary. It's a creative innovation by PaX/grsec, it uses a random seed inserted at build time, but also inserts local variables in every marked function, so that different runtime code paths and control flows create different entropy seeds. But it's only an optional feature and almost nobody uses it - PaX/grsec ideas are too radical to most people ;-)
- Note that it's security properties can still be seriously weakened by a replicated kernel binary. Also, it's entropy is seeded to the pool, but it's also not trusted and credited, since it's considered a workaround, not a solution.
4. Keep collecting entropy from various sources of randomness, such as interrupts.
As you can see, it's actually really similar to OpenBSD (I meant the concepts, not the implementation), the only difference is that almost everything is optional and nothing is guaranteed to work.
---
So as a tradeoff, systemd uses the following logic instead.
1. If available, bypass the kernel, use rdrand directly for non-crypto randomness.
2. For everything else (no rdrand machines & crypto), use the system's entropy pool, it may block for a long time before the pool is initialized, even with a random seed file or Latent Entropy, because their entropy is uncredited.
I think this is a reasonable tradeoff, but if rdrand is broken, everything breaks down.
I think the differences between OpenBSD and Linux is basically due to how much control you have over the operating system.
OpenBSD has the advantage you have when you're building an entire operating system, not just a kernel.
---
Update: As pointed out by the comment, systemd supports bootloader entropy too, but only uses it via systemd-boot on EFI systems since it's not vulnerable to the image replication problem. With UEFI, it can combine the seed file with a machine-specific EFI variable ("system token") in UEFI's NVRAM generated during system installation.
Systemd also criticizes NetBSD's bootloader entropy for being vulnerable to the image replication problem, see https://systemd.io/RANDOM_SEEDS/
> This is boring: NetBSD had boot loader entropy seed support since ages!
> Yes, NetBSD has that, and the above is inspired by that (note though: this article is about a lot more than that). NetBSD’s support is not really safe, since it neither updates the random seed before using it, nor has any safeguards against replicating the same disk image with its random seed on multiple machines (which the ‘system token’ mentioned above is supposed to address). This means reuse of the same random seed by the boot loader is much more likely.
Update 2: Rewrite the comment entirely.
I thought systemd-boot implemented this as well these days?
>During early OS boot the system manager reads this variable and passes it to the OS kernel's random pool, crediting the full entropy it contains. This is an efficient way to ensure the system starts up with a fully initialized kernel random pool — as early as the initial RAM disk phase.
https://man.archlinux.org/man/core/systemd/systemd-boot.7.en
> This is the advantage you have when you're building an entire operating system, not just a kernel.
I'm now convinced that systemd really is an operating system.
> When generating Type 4 UUIDs, systemd tries to use Intel’s and AMD’s RDRAND CPU opcode directly, [...] If RDRAND is not available or doesn’t work, it will use synchronous getrandom() as fallback, and /dev/urandom on old kernels where that system call doesn’t exist yet. This means on non-Intel/AMD systems UUID generation will block on kernel entropy initialization.
1. Why does systemd implement its own random number generation code?
https://github.com/systemd/systemd/blob/27231dc14c925935b669...
2. systemd uses RDRAND to generate UUIDs only. Why isn’t the algorithm robust to collisions?
https://github.com/systemd/systemd/issues/18184#issuecomment...
3. Why do you have to pass systemd args on the kernel command line?
https://github.com/systemd/systemd/issues/18184#issuecomment...
4. This is not the first time this happens. Why weren’t they able to provide a solution in 2 years?
https://bugs.launchpad.net/ubuntu/+source/systemd/+bug/18358...
2. What algorithm? It's just RDRAND.
3. Where else would you pass them?
4. What do you mean 'they'? CPU manufacturers?
You might also be interested in this comment: https://github.com/systemd/systemd/blob/bcac754d66374782a85a...
> UUID generation should be robust to random number collisions.
The UUID standards say that nowhere at all, it is only acknowledged that collisions may happen even if they are unlikely.
But you cannot use getrandom().
During early boot, the kernel will either block indefinitely and/or log the uninitialized urandom read as a security problem. It was the entire reason that brought systemd's rdrand code into existence.
3. You don't. The `nordrand` argument is a kernel argument that tells the kernel to disable rdrand; so then when systemd asks the kernel if rdrand is supported the kernel says "no". The `SYSTEMD_RDRAND=0` argument is indeed a systemd argument, but it's absolutely normal to pass init arguments on the kernel command line.
4. Because hacking around hardware bugs isn't systemd's job. It's the kernel's. You shouldn't be filing a systemd bug, you should be filing a Linux bug to disable rdrand on that cpuid. Why aren't you asking why Linux wasn't able to provide a solution in 2 years?
I recall discussions to maybe rely on something like jitter entropy when the pool is empty and getentropy() is called.
This ended up being implemented in 5.4 kernel: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
Systemd is literally the only software, that has this problem. I am not aware of any other software, that uses rdrand and expects high-quality cryptography-grade randomness. Precisely, because is does not work. Intel CPUs used to have very similar issues with rdrand and so did AMD. Furthermore, CPU implementation of rdrand is a very attractive targets for state backdoors, so most sensible developers either follow the "GNUPG way" (ask for randomness from user) or simply read from /dev/random.
The rdrand instruction is great for games, because it allows to make white noise without complex algorithms and system call overhead. It is also handy for few situations, like interrupt handlers, when you needs to create some semi-random value without using stack space or calling into outside code. Unfortunately, when it was introduced, rdrand was documented to generate "cryptographically strong random numbers" (did Intel developers ever knew, what that means?) Of course, most actual cryptography experts didn't buy into that. As a consequence, and because multi-platform software needed to have it's own RNG anyway, the instruction remained largely unused for actual cryptography. Unused = untested and sometimes broken. If I were in systemd developer's place, I would not hinge bootability of my systems on something like that.
I know it's in vogue to rip on systemd, but let's at least try to be fair.
Eh. You're looking at hundreds of cycles per use. That makes it slower than a secure software RNG, let alone an insecure one.
Please seek out and understand the reasons behind calling RDRAND in systemd before making statements like these. "High-quality crytography-grade randomness" is explicitly not required for the purposes of the PRNG at boot-time, which include UUID generation and seeding hash tables.
https://github.com/systemd/systemd/blob/61bd7d1ed595a98e5fbf...
- The clock might not be initialized; the justification for using rdrand specifically calls out embedded systems; embedded systems are also likely to have clocks that reset to some date every boot and get fixes as part of the boot process that happens later.
- The "node ID" (nominally, a MAC address) udev has not started yet and therefore has not initialized the network cards yet (in fact, if you configure it to randomize your MAC address (for privacy), the random_bytes() routine being discussed is the one that it will use to generate the MAC!) The filesystem hasn't yet been mounted, it can't use /etc/machine-id or anything like that either.
* RDRAND * Seed from previous boot * Jitter * Result of every sensor (for example temperature) attached to the machine * Seed from hypervisor (if we are in a VM) * Time & Date * Any information about the physical computer we are on (attached hardware)
Similar story for systemd of course, nobody would expect them to learn their lesson. How nice of an init system to keep your system dead because it apparently needs CPRNG generated job ids of all things.
So it does not really matter if it was intentional or not: regardless of the root cause of this bug, it should now be considered that rdrand should never be trusted (unless you truly don't care that your systems risk to randomly break or you risk to randomly generate compromised keys) and its mere usage (except maybe indirectly in mitigated ways designed by experts and audited for years) considered a very likely security vulnerability.
When PulseAudio introduces random crackles and scratches in sound output, they claim, that I have a misbehaving sound card. It does not "misbehave", when I use the same applications with ALSA, but whatever.
When rdrand fails to produce high-quality entropy — again and again, over and over — Poettering complains about buggy CPUs.
I hope, that this particular group never ends up working on network hardware.
I mean RDRAND is a great example here, if you never use it, you never encounter these bugs. It's not impossible that PulseAudio tries to play higher quality audio or simply uses the device differently.
> I hope, that this particular group never ends up working on network hardware.
I'd kinda love it, probably quite a few fun hardware bugs will be found.
https://devblogs.microsoft.com/oldnewthing/20050512-48/?p=35...
Pulseaudio mixes sound from several applications, unlike Alsa. Alsa just configures your soundcard for that one stream, Pulseaudio has no such luxury.
In order to mix relatively small buffers (because latency), it needs to do timing. If your soundcard has problem with timing (and many do!), you will get crackling. The good news is, that the problem with timing can be only at specific frequencies; in the past, I had a computer with Nvidia Ion and it did this with 44,1kHz audio. With 48kHz, everything was OK. So fixing the output at 48kHz by forcing Pulse to mix at this frequency fixed the crackling.
Dmix for alsa was buggy, because just like PA, it didn't know about quirks of the hardware out in the field. And it stayed buggy, because nobody used it in return. Yes, PA was forced on users, but in the result the quirks were found, implemented and today, we all are better off. I didn't have any problem with PA since 2012 or so, but quite enjoyed the features it brought to the desktop.
So, a PRNG with a semi-decent (not perfect) entropy pool is required at boot time, and systemd needs to run in environments where seeding that pool in software could take on the order of minutes. This is why RDRAND is used to seed the pool during boot.
https://github.com/systemd/systemd/blob/61bd7d1ed595a98e5fbf...
2. Use a tree instead of a hash-table; or just use RDRAND and hope you aren't presented with malicious inputs.
The comment in the code[1] about RDRAND being sufficient for the use-case of UUIDs is empirically false. To continue to rely upon it is to insist that the rest of the world conform to your beliefs, rather than to adjust your beliefs to match the rest of the world.
1: https://github.com/systemd/systemd/blob/bcac754d66374782a85a...
Ipse dixit. Can you provide an explanation?
2. https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...
3. https://linuxreviews.org/RDRAND_stops_returning_random_value...
4. There are also comments elsewhere on this page that older Intel RDRAND implementations had similar issues, but they did not cite their source.
https://github.com/systemd/systemd/blob/bcac754d66374782a85a...
int rdrand(unsigned long *ret) {
/* So, you are a "security researcher", and you wonder why we bother with using raw RDRAND here,
* instead of sticking to /dev/urandom or getrandom()?
*
* Here's why: early boot. On Linux, during early boot the random pool that backs /dev/urandom and
* getrandom() is generally not initialized yet. It is very common that initialization of the random
* pool takes a longer time (up to many minutes), in particular on embedded devices that have no
* explicit hardware random generator, as well as in virtualized environments such as major cloud
* installations that do not provide virtio-rng or a similar mechanism.
*
* In such an environment using getrandom() synchronously means we'd block the entire system boot-up
* until the pool is initialized, i.e. *very* long. Using getrandom() asynchronously (GRND_NONBLOCK)
* would mean acquiring randomness during early boot would simply fail. Using /dev/urandom would mean
* generating many kmsg log messages about our use of it before the random pool is properly
* initialized. Neither of these outcomes is desirable.
*
* Thus, for very specific purposes we use RDRAND instead of either of these three options. RDRAND
* provides us quickly and relatively reliably with random values, without having to delay boot,
* without triggering warning messages in kmsg.
*
* Note that we use RDRAND only under very specific circumstances, when the requirements on the
* quality of the returned entropy permit it. Specifically, here are some cases where we *do* use
* RDRAND:
*
* • UUID generation: UUIDs are supposed to be universally unique but are not cryptographic
* key material. The quality and trust level of RDRAND should hence be OK: UUIDs should be
* generated in a way that is reliably unique, but they do not require ultimate trust into
* the entropy generator. systemd generates a number of UUIDs during early boot, including
* 'invocation IDs' for every unit spawned that identify the specific invocation of the
* service globally, and a number of others. Other alternatives for generating these UUIDs
* have been considered, but don't really work: for example, hashing uuids from a local
* system identifier combined with a counter falls flat because during early boot disk
* storage is not yet available (think: initrd) and thus a system-specific ID cannot be
* stored or retrieved yet.
*
* • Hash table seed generation: systemd uses many hash tables internally. Hash tables are
* generally assumed to have O(1) access complexity, but can deteriorate to prohibitive
* O(n) access complexity if an attacker manages to trigger a large number of hash
* collisions. Thus, systemd (as any software employing hash tables should) uses seeded
* hash functions for its hash tables, with a seed generated randomly. The hash tables
* systemd employs watch the fill level closely and reseed if necessary. This allows use of
* a low quality RNG initially, as long as it improves should a hash table be under attack:
* the attacker after all needs to trigger many collisions to exploit it for the purpose
* of DoS, but if doing so improves the seed the attack surface is reduced as the attack
* takes place.
*
* Some cases where we do NOT use RDRAND are:
*
* • Generation of cryptographic key material
*
* • Generation of cryptographic salt values
*
* This function returns:
*
* -EOPNOTSUPP → RDRAND is not available on this system
* -EAGAIN → The operation failed this time, but is likely to work if you try again a few
* times
* -EUCLEAN → We got some random value, but it looked strange, so we refused using it.
* This failure might or might not be temporary.
*/RDRAND is rather slow, especially with the SRBDS microcode update. One instruction takes 1,200 ns on my system, that's 6.6 MB/s. A software implementation of a CSPRNG will do hundreds of MB/s, the general purpose PRNGs do several GB/s.
Torvalds seems to understand this, but now there is only so much he can do. Poettering's stance seems so oblivious (get a better hardware or fix from manufacturer), one wonders whether he should leave maintaining/programming to people who actually care about users. It has been accepted standard for decades that software should work around bugs in hardware and it makes sense - it is much easier to change software than to fix hardware.
So glad my CPU does not have RDRAND and operating systems I use do not require super random numbers to boot.
or just disable rdrand.
Systemd implemented RDRAND precisely because the kernel was previously not robust against all failure modes regarding to /dev/urandom - early boot may block indefinitely if there's a lack of adequate inputs (the fallback in-kernel jitter entropy collector was introduced many years later, in 2019). Also, the failure of RDRAND was virtually unheard of [0] at that time when that decision was made. It's why I said the decision was reasonable back then [1].
I agree that the context has changed after AMD's first RDRAND incident and that decision has became less reasonable.
[0] At least for non-crypto purposes, like systemd's uses. Compromised RDRAND is always a concern among cryptographers, but totally broken RDRAND was not.
[1] BTW, I bet implementing an entropy gathering code and a randomness algorithm in systemd would probably cause greater amount of criticism.
If this was a one-off bug in systemd, it could get a pass, but it isn't a one-off. Try to boot a Linux system using systemd when something is just slightly off, like one block device that's normally available is missing or when networking doesn't come up. systemd does not handle failures well, and it doesn't handle them because the main developer makes no effort to test failure modes. This incident is yet another example of this pattern of development style. When I write code, I have to make an effort to test what happens during unexpected failures. I expect the developer of the most critical component to booting a modern Linux system to do the same.
Fair enough.
HN: How dare you.[1]
Also HN: Criticizes systemd for implementing its own thing
Systemd just can't win.
The original crash report generates an error for a file name already existing. A simple PRNG algorithm, perhaps seeded with a "random" RDRAND number, should fit that purpose easily, shouldn't it?
A 32 bit random number, as used to generate the examples, isn't good enough to guarantee uniqueness anyway. It seems like the original reporter's specific CPU silicon or their loaded microcode does have a problem (because the boot fails on that particular chip so often) but the general dependency on RDRAND continues to confuse me.
(1) There's no evidence of anything wrong with AMD's RNG.
(2) Lots of people on Github and HN don't understand the birthday paradox.