221 comments
Do we now learn that they fixed "always generate all 1s" with "never generate all 0s"??
EDIT: I've been unable to reproduce the problem on my CPU, FWIW. It's a Ryzen 5 3600.
EDIT2: OK, update, I can reproduce it with rdrand16, rdrand32 is fine but rdrand16 can never generate all 0s. So my CPU does have this problem!
But it looks like the rdrand16 instruction can produce zeros just fine, it just sets CF=0 erroneously (indicating an error and that the user program should retry).
So keep that in mind when you try to reproduce it too and use some abstraction that could implement retries internally.
Zen 5 rdrand16/32 return zero with CF=1 on entropy exhaustion and their recommended approach directly leads to the issue you observed: treat all-zero result of rdseed as if cf=0 (failure) and re-roll the dice, effectively recreating the zen 1/zen 2 issue all over again!
They say this might be addressed by a future microcode update… meaning there’s a chance they’ll just patch it to do just that in software. Maybe that’s how they got into this mess in the first place?
Also, am I a complete idiot or is asserting the relative distribution of a mere 64k possible results a rather easy black box validation test that I would’ve assumed they’d be doing? When I used to write cycle-accurate emulators in the past, that would have been an obvious test to include. This isn’t some arcane instruction no one uses or a really complicated case with deep dependency and/or timing issues; it’s like getting rdtsc wrong.
return 4 # Determined by fair dice roll. $ ./a.out | rg '\b\-?\d\b' | sort -n | uniq -c
15281 -2
15192 -1
15273 0
15243 1
15269 2
I used the GCC intrinsic ( _rdrand16_step ), #include <immintrin.h>
short rdrand16() { // gcc -mrdrnd
short ret;
while (1 != _rdrand16_step(&ret)) { }
return ret;
}I.e., we had `random.trust_cpu=off nordrand` in `GRUB_CMDLINE_LINUX`.
I thought the kernel would not replace anything just because it adds a potentially bad source.
E.g. if you have rand source A, and xor it with rand source B, then you get, at worst, the best of A and B,
Basically I'm wondering if it's a bug in the version of the instruction that writes to a 16-bit reg, or a bug in the underlying RNG
It takes entropy from multiple different sources, makes it all input to the XOF, then the XOF uses cryptography to output a stream that has as much entropy as the combined entropy of all of its sources of randomness. So if an XOF, for example, takes 100 runs of rdrand16, along with the system time in microseconds and the number of milliseconds between receiving 100 packets over the network, the XOF will output a completely random stream without artifacts like never returning 0x0000, even if rdrand16 never outputs 0x0000.
I fail to see why one should either rely on a single random source nor roll their own.
The only legitimate reason to roll your own is when you're developing for an embedded system or a bootloader or something like that where there is no kernel API available.
getrandom() is often times suggested, but alas isn’t a standardized function, i.e. it’s not part of the POSIX specification. Considering how the C23 changes to the C specification caused a lot of perfectly good C code to no longer compile, I’m very anal about sticking to specs; I use '-std=C99' for my code these days (even though it can compile as C23 code) and stick to POSIX functions (except chroot() and setgroups(), but both of those predate POSIX, and even here I have a compile-time option to compile my code without those non-POSIX syscalls).
The code using a secure XOF (the algorithm was developed by the same team which later on made SHA-3, and includes people who helped make AES) has been around for nearly two decades (the code where I roll my own RNG to make secure random numbers has been around for over 25 years, but used AES before XOFs existed) and not one security problem has found with the RNG code has ever been found. [1] “Don’t roll your own RNG” is a suggestion, but it is possible to do so securely if one knows what they are doing (i.e. they have read Applied Cryptography and keep current with cryptographic developments).
For anything vibe coded (my code is 100% human written, for the record), rolling one’s own RNG is a really bad idea.
[1] There was a theoretical issue with cache timing attacks over two decades ago, so I put mitigations in place, and then chose to use an XOF for newer code.
[2] There was an issue where a separate implementation I made of this XOF would generate incorrect test vectors in clang, but only at some optimization levels. I now test the XOF in both GCC and clang at multiple optimization levels to make sure it acts correctly.
If anyone is interested in this topic please just read the code[0]. It has a lot of interesting tricks that you would not have just rolling your own.
[0]https://github.com/torvalds/linux/blob/master/drivers/char/r...
But if you're using a custom kernel that has a custom KRNG based on an XOF, sure, whatever, I guess.
Oh, I guess you have to ensure the inputs aren’t correlated, or they’ll cancel out?
The sources of entropy can be correlated and won’t cancel out with a well designed secure XOF. SHAKE-256 is an example of a secure XOF.
hash = sha256(current_time());
for i := 0; i < n; i++ {
hash = sha256(hash.append(current_time()))
}
This is because the number of nanoseconds between hashes is actually itself variable, and this is true for physics reasons that are basically beyond the control of any attacker trying to manipulate your entropy. If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy. If your time() function has a resolution of milliseconds, you need to let this run for more like 20 milliseconds, and if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.The reason I like doing it this way is that it happens entirely in userspace, it's genuinely a secure method of generating entropy, and it has no dependencies on potentially buggy firmware or microcode outside of the time() call, which is both fairly narrow, fairly heavily used (meaning a bug is likely to be discovered during testing, as the implementation is likely heavily scrutinized), and also fairly easy to test independently - just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance. The above suggestions are assuming about 2.5 bits of variance between calls, meaning there should be a range of at least 20 nanoseconds between your slowest and fastest hash call. This has been true on every CPU I've ever measured, including microcontrollers.
The security of your system depends on time() providing enough entropy, even though that's not what it's designed to do. It's built on top of the wrong primitive from the start.
> The reason I like doing it this way is that it happens entirely in userspace
On Linux this is often true, but there is no portable way to get the current time that is _guaranteed_ not to do any system calls.
> If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy.
You haven't proven that at all. It's easy to imagine that on a CPU running at a fixed frequency the interval between reads is constant, so if anyone knows (or can guess) the start time the resulting seed is entirely predictable.
This is completely independent of timer resolution. You seem to realize that as you were writing that:
> just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance
Oh yes, because evaluating the quality of a random number generator is such a trivial thing to do, it's not like there is decades of research behind it or anything.
And assuming you are able to verify the statistical variance: are you going to put that logic in the loop, making it significantly more complex?
Or are you going to do this test on your machine and then ship your code on the assumption that if it works on your machine, it will work everywhere else, too?
> if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.
So not only is it insecure, it's agonizingly slow by design. Why do a system call that takes milliseconds at best, when we can run a loop in userspace for 5 seconds?
All this just so you can avoid writing the obviously correct oneliner:
if (getentropy(&seed, sizeof(seed)) != 0) abort();The nice thing about using multiple entropy sources with a secure XOF is that the resulting entropy is at least as strong as the most secure entropy source given to the XOF.
I am happy to have a discussion with you at the deepest technical levels of applied cryptography, this is not something I blindly made up on my own. I'm well studied in the field and can readily defend this technique.
In some protocols that rely on random input when encrypting (like the EC flaw that broke the PS3) it may cause an observable statistical bias after 2^70 encryptions or so.
" I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the article below:
"By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors...."
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. "
https://web.archive.org/web/20180611180213/https://plus.goog...
Putting a backdoor into CSPRNG is a favored way to break crypto, for example Dual_EC_DRBG.
"
Weaknesses in the cryptographic security of the algorithm were known and publicly criticised well before the algorithm became part of a formal standard endorsed by the ANSI, ISO, and formerly by the National Institute of Standards and Technology (NIST). One of the weaknesses publicly identified was the potential of the algorithm to harbour a cryptographic backdoor advantageous to those who know about it—the United States government's National Security Agency (NSA)—and no one else. In 2013, The New York Times reported that documents in their possession but never released to the public "appear to confirm" that the backdoor was real, and had been deliberately inserted by the NSA as part of its Bullrun decryption program. In December 2013, a Reuters news article alleged that in 2004, before NIST standardized Dual_EC_DRBG, NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default in the RSA BSAFE cryptography library, which resulted in RSA Security becoming the most important distributor of the insecure algorithm. RSA responded that they "categorically deny" that they had ever knowingly colluded with the NSA to adopt an algorithm that was known to be flawed, but also stated, "We have never kept this relationship [with the NSA] a secret and in fact have openly publicized it."
"
[edit to add]: Also, the bulletin is solely about RDSEED zeros, whereas the OP is also reporting RDRAND zeroes.
https://github.com/systemd/systemd/pull/12536/commits/1c53d4...
https://www.phoronix.com/news/AMD-Releases-Linux-Zen2-Fix
https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...
No idea what happened after. And that also means that you suddently need information about user systems BIOS/Microcode.
Read the full thread on Hacker News →
Related stories
- SHISHUA: The Fastest Pseudo-Random Generator In the Worldespadrine.github.ioLobsters · 13 points · over 6 years ago
- Lobsters · 3 points · almost 11 years ago
- Lobsters · 12 points · over 5 years ago
- Hacker News · 1 points · 7 days ago
- Hacker News · 2 points · 11 days ago
- Hacker News · 2 points · 8 days ago