This is not the first RNG bug on Zen 2, I recall after I first got mine that some application or other would quit immediately at startup because rdrand always returned -1, i.e. all 1s. It was fixed with a microcode update.
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.
Funny. Look up errata AMD-SB-7055: RDSEED Failure on AMD “Zen 5” Processors.
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.
If I remember correctly, we had a setting in every Linux server we owned to remove CPU as a RNG seeder for the kernel because of those bugs with AMD CPUs.
I.e., we had `random.trust_cpu=off nordrand` in `GRUB_CMDLINE_LINUX`.
Yes it does. rdrand32()%65535 was my first attempt, and generated zeroes at about the expected rate, that's why I initially erroneously thought my CPU did not have this problem.
This is why I use, in security critical contents of my software (where the numbers have to be computationally infeasible to produce), a type of random number generator called an XOF (extendable-output function).
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.
Yes, on any modern system you should use the kernel provided random number sources.
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.
Yes, /dev/(u)random is supposed to do that, but what if there’s a bug in a kernel (e.g. some embedded system which may not even be running Linux) which causes /dev/(u)ramdom to be less than secure? There’s also issues where, for example, it may no longer be possible to read /dev/(u)random after putting the process in a chroot() sandbox (chroot() isn’t defined in POSIX so its behavior is not guaranteed to be consistent across multiple operating systems).
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.
Well that very similar to how the Linux kernel does it. The linux kernel does it a little differently in that it uses the chacha8 stream cipher instead of a XOF. The chacha8 stream key is frequently reseeded by hashing the entropy pool with blake2b over the collected randomness from all sources but a lot comes from the nanosecond timing of hardware interrupts. Depending on configuration the blocking rng does not return unless 256 bits of trusted randomness are mixed into the entropy pool.
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.
If you're building a userland XOF RNG to extend the kernel's RNG (that has the same security properties) you are reducing security, not improving it. The kernel has advantages for managing and securing a secret "entropy" pool that you won't replicate in userland.
But if you're using a custom kernel that has a custom KRNG based on an XOF, sure, whatever, I guess.
Nifty! Out of curiosity, how much different is that from taking several partly-random streams and XORing them together? I always assumed what was going on was essentially a fancier version of that.
Oh, I guess you have to ensure the inputs aren’t correlated, or they’ll cancel out?
The advantage of a secure XOF is that a malicious source of entropy needs to do a good deal more work than a simple XOR to generate controlled PRNG output (the attacker needs to do 2^n XOF operations to generate n bits of PRNG output, and that’s only if the attacker knows the output of all other sources of entropy—someone with that level of access can do far more effective attacks).
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.
You can effectively achieve the same result with this simple operation:
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.
This comment demonstrates everything that's wrong with people trying to be clever and rolling their own crypto.
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();
I wouldn’t trust it as a sole source of entropy, but it can be one of multiple entropy sources to feed in to an XOF to get secure numbers.
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 know that there's a really strong culture in the software world around downvoting anything that looks or smells like "hand-rolled cryptography", but this is my actual profession and specialization within the software world, and most of what I'm seeing in this thread is knee-jerk reactions to an unexpected technique rather than careful intellectual commentary and consideration of the merits of the technique.
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.
Even if you use these directly for cryptography, most cryptography is not practically affected by being unable to receive a zero word. For instance you can choose a private or symmetric key from any random distribution you like, as long as it's got enough entropy to be unguessable. The fact that your private key can't have a zero half makes no difference because that was extremely unlikely to happen anyway.
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.
According to Theodore Ts there was pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction.
"
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.
"
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."
Not sure if this finding is new, but the author from FASM Thread apparently has a Zen 2 (He doesn't directly mention anything besides "Ryzen 7", some other poster mentions it is a 4800HS). There were a number of articles about RDRAND being broken on Zen 2 and earlier generations but fixed via Microcode from about 6 years ago:
I remember setting up a new git CI build server many years ago, which at the time rather quickly started failing build pipelines in a nodejs css frontend build script, turns out there was something funky with the AMD processor's RDRAND. A motherboard BIOS flash update fixed it.
I always wonder how hardware bugs like this happen with the sheer amount of hardware validation that's done. It'd be fascinating to know how it slipped through the cracks, though I know almost nothing about this side of the industry sadly
Validation can't be better than the quality of the specification. Humans don't create comprehensive, unambiguous specifications for the same reasons that we don't write bug-free code, and need formal validation.
Brooks talks about this in _Mythical_Man-Month_... if you really could "just implement the specification", then the specification itself would be complete enough to serve as your code. There will always be bugs in both.
That "sheer amount of hardware validation" is always less-than-perfectly spread across a whole lotta billions of transistors, and combinatorics is a harsh mistress.
It's most likely a quick patch for a previous bug where the RNG would fail but misreport it as a success with all 0 bits. The quick patch is to make all 0s a failure.
I'm getting 16-bit zeros on my Zen 3 chip (+1:3821, 0:3893, -1:3895), I will wait to get some statistically significant samples for the 32-bit values and update the forum thread. Maybe it was fixed after Zen 2?
Does anyone have access to an HPC cluster with thousands of Zen2 chips? We might want to check 64-bit ones with that - should take just a couple years depending on the size of the machine.
Anyone from the High-Performance Computing Center Stuttgart willing to play on the 720,320 Zen2 cores?
AMD's random number generator probably can't generate a 0 ;)
Anyways, I think it is good practice to consider the output of any hardware RNG to be biased and to only use it indirectly as a source of entropy. The actual numbers come from a PRNG, secure of not depending on your needs, that have a guaranteed distribution.
It can still cause problems if badly used, or, ironically fix problems if badly used in a different way.
Looks like they tried 16-bit numbers. Does the odd behavior happen also on 32 and 64 (might take a long time to check - I'd start scratching my head after a couple hundred years of no zeroes) ones? Is the zero masking as some other fixed number, increasing its output count? Is RDRAND implemented as multiple reads of an internal state so that a larger random number takes longer?
> Yes, when using either 32-bit or 64-bit number, the lowest portion can output a zero, as I suggested on the attached example file as a modification to fix the problem.
But a true zero (fitting the requested size), on AMD, never happens.
Another person (on page 2) confirms those results on an older AMD processor (but failed to reproduce on a very new one, 9950X3D).
So what? The point is to be non predictable not to pick all the numbers in the range with exactly the same probability. Would it be a problem if it never generated 16542?
By your argument, it would not be a problem if the RNG never generated 0. So, it must follow that it would also not be a problem if it never generated {1, 2, 3, ..., 253}.
That means that our RNG now only generates the values 254 and 255. Which of the values is generated is unpredictable on any given call. However, 7 of the 8 output bits are now always fixed and so completely predictable. Can you imagine how an attacker could exploit that?
Failing to generate only the number 0 is a weaker version of the same class of flaw.
“Pick all the numbers in the range with exactly the same probability” is a very important property of RNGs. Yes, skipping 16542 would be equally bad.
You can frame it around being “non predictable”, but then you need to define those words. It’s not, for example, a poker game where it’s trying to bluff you, right? It’s also not about just making predictions < 100% reliable and declaring victory. It must specifically make all predictions no better than random guessing, and that entails picking any number in range with equal probability, otherwise predictions like “it will be {hot spot}” or “it won’t be {cold spot}” do better than random chance. In this case, specifically, I can predict with 100% accuracy that the result won’t be 0, and that’s a flaw in its unpredictability. I can also predict a bunch of other things with slightly higher accuracy than random guessing, like that it will be odd or greater than max ÷ 2.
It's not a 2^16-sided weighted die. But a 2^16 - 1 sided fair die.
I am not saying there is no bug. I am saying the bug has no practical impact.
Sure if you are that one guy that is getting these values raw from the instruction and comparing to zero for some purpose then you are in trouble. But I am pretty sure no one is doing that, especially given that the bug surfaced after 6 years of millions of users.
It is literally the first Peano axiom that 0 is a natural number. In fact it is the only natural number that is defined in and of itself. All other natural numbers are defined by using the “successor” operation to add things to zero.
Usually you do "rdrand % <some-number>" anyways, and in that case you will still get zeroes. True, your result might be skewed by 1/(maxint/some-number) but I guess that's not a big problem in practice
If you want uniformly-distributed random numbers, computing the remainder works only when the modulus is a power of two.
Otherwise, a slightly more complicated algorithm is necessary, where you reject a range of numbers either before computing the remainder (to make the set of possible values a multiple of the modulus) or after computing the value modulo some power of two (to reject values greater than your target).
Besides these 2 variants based on the remainder of division of integers, there are also 2 corresponding algorithms using multiplication of the input interpreted as a fraction, followed by taking the integer part of the result.
Example: to get a number between 0-2 (3 values) with a 4-bit RNG (16 values, 0-15) you can split the set 0-14 into 3 groups of 5 (doesn't matter if you use modulus or divide) but if you get 15 you need to re-roll.
It is just possible they decided crypto code that uses it was safer to skip zeros. (Whist mathematically it should be no more likely; it is vastly more likely someone will actually try that key).
It is also possible that their code was generating too many zeros and the easiest fix was to discard them all.
Can you clarify what you mean by "it is vastly more likely someone will actually try that key"?
I'm guessing you don't think there are people calling rdrand in a loop and throwing away the output with high probability except when it is 0, but I can't see how else you imagine people would be vastly more likely to use the output when it is 0?
In lots of scenarios I know the software used to generate the key; the only unknown is the random numbers used. If I am searching for weaknesses it is highly likely I would try keys with different seeds; zero, one, are going to me much more likely choices here then hoping I can guess the right values.
This is not the first RNG bug on Zen 2, I recall after I first got mine that some application or other would quit immediately at startup because rdrand always returned -1, i.e. all 1s. It was fixed with a microcode update.
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!
I can reproduce it too with rdrand16 on Zen2.
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.
Funny. Look up errata AMD-SB-7055: RDSEED Failure on AMD “Zen 5” Processors.
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.
2 replies →
Good observation, that seems like the most likely explanation. Do you ever see "true" CF=0 (with nonzero arg) or did they just take the lazy approach?
2 replies →
So it sets too many 0's
I always think of https://www.reddit.com/r/ProgrammerHumor/comments/5yhl93/ran...
https://xkcd.com/221/ for those not in the know
7 replies →
Zen 4 reporting in. I'm unable to reproduce it (7840U).
I used the GCC intrinsic ( _rdrand16_step ),
If I remember correctly, we had a setting in every Linux server we owned to remove CPU as a RNG seeder for the kernel because of those bugs with AMD CPUs.
I.e., we had `random.trust_cpu=off nordrand` in `GRUB_CMDLINE_LINUX`.
Adding bad randomness can't degrade good randomness, can it?
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,
18 replies →
Does rdrand32 and then taking the lowest 16 bits of its result yield any zeroes?
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
Yes it does. rdrand32()%65535 was my first attempt, and generated zeroes at about the expected rate, that's why I initially erroneously thought my CPU did not have this problem.
3 replies →
You probably recall https://news.ycombinator.com/item?id=19848953 .
Even if you reproduce the issue, it is not a proof it can't generate a zero - just that it's very unlikely.
To prove it, we'd need to examine the chip and its microcode.
This is why I use, in security critical contents of my software (where the numbers have to be computationally infeasible to produce), a type of random number generator called an XOF (extendable-output function).
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.
Isn’t this effectively what systems like /dev/(u)rand do? Pool multiple random sources together to hedge against these things?
I fail to see why one should either rely on a single random source nor roll their own.
Yes, on any modern system you should use the kernel provided random number sources.
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.
1 reply →
Yes, /dev/(u)random is supposed to do that, but what if there’s a bug in a kernel (e.g. some embedded system which may not even be running Linux) which causes /dev/(u)ramdom to be less than secure? There’s also issues where, for example, it may no longer be possible to read /dev/(u)random after putting the process in a chroot() sandbox (chroot() isn’t defined in POSIX so its behavior is not guaranteed to be consistent across multiple operating systems).
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.
45 replies →
Well that very similar to how the Linux kernel does it. The linux kernel does it a little differently in that it uses the chacha8 stream cipher instead of a XOF. The chacha8 stream key is frequently reseeded by hashing the entropy pool with blake2b over the collected randomness from all sources but a lot comes from the nanosecond timing of hardware interrupts. Depending on configuration the blocking rng does not return unless 256 bits of trusted randomness are mixed into the entropy pool.
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...
If you're building a userland XOF RNG to extend the kernel's RNG (that has the same security properties) you are reducing security, not improving it. The kernel has advantages for managing and securing a secret "entropy" pool that you won't replicate in userland.
But if you're using a custom kernel that has a custom KRNG based on an XOF, sure, whatever, I guess.
Nifty! Out of curiosity, how much different is that from taking several partly-random streams and XORing them together? I always assumed what was going on was essentially a fancier version of that.
Oh, I guess you have to ensure the inputs aren’t correlated, or they’ll cancel out?
The advantage of a secure XOF is that a malicious source of entropy needs to do a good deal more work than a simple XOR to generate controlled PRNG output (the attacker needs to do 2^n XOF operations to generate n bits of PRNG output, and that’s only if the attacker knows the output of all other sources of entropy—someone with that level of access can do far more effective attacks).
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.
You can effectively achieve the same result with this simple operation:
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.
This comment demonstrates everything that's wrong with people trying to be clever and rolling their own crypto.
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:
25 replies →
I wouldn’t trust it as a sole source of entropy, but it can be one of multiple entropy sources to feed in to an XOF to get secure numbers.
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.
3 replies →
I know that there's a really strong culture in the software world around downvoting anything that looks or smells like "hand-rolled cryptography", but this is my actual profession and specialization within the software world, and most of what I'm seeing in this thread is knee-jerk reactions to an unexpected technique rather than careful intellectual commentary and consideration of the merits of the technique.
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.
Embarrassing, but probably little practical impact, since these hardware random numbers are typically not used directly and instead seed a CSPRNG.
Even if you use these directly for cryptography, most cryptography is not practically affected by being unable to receive a zero word. For instance you can choose a private or symmetric key from any random distribution you like, as long as it's got enough entropy to be unguessable. The fact that your private key can't have a zero half makes no difference because that was extremely unlikely to happen anyway.
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.
With ecdsa the number of signatures needed to attack biased nonces seems low, hundreds or thousands? https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-ca...
1 reply →
According to Theodore Ts there was pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction.
" 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."
"
https://en.wikipedia.org/wiki/Dual_EC_DRBG
https://www.amd.com/en/resources/product-security/bulletin/a...
The OP says they discovered this on a Zen 2, which is not covered by that bulletin (?)
[edit to add]: Also, the bulletin is solely about RDSEED zeros, whereas the OP is also reporting RDRAND zeroes.
Older AMD processors had issues as well:
https://github.com/systemd/systemd/pull/12536/commits/1c53d4...
4 replies →
Not sure if this finding is new, but the author from FASM Thread apparently has a Zen 2 (He doesn't directly mention anything besides "Ryzen 7", some other poster mentions it is a 4800HS). There were a number of articles about RDRAND being broken on Zen 2 and earlier generations but fixed via Microcode from about 6 years ago:
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.
Here are dieharder results from zen 2 (with slow rdseed, unpatched) for rdrand. Totally broken also.
https://rurban.github.io/dieharder/QUALITY.html
I remember setting up a new git CI build server many years ago, which at the time rather quickly started failing build pipelines in a nodejs css frontend build script, turns out there was something funky with the AMD processor's RDRAND. A motherboard BIOS flash update fixed it.
https://github.com/sass/libsass/issues/3151
I always wonder how hardware bugs like this happen with the sheer amount of hardware validation that's done. It'd be fascinating to know how it slipped through the cracks, though I know almost nothing about this side of the industry sadly
Validation can't be better than the quality of the specification. Humans don't create comprehensive, unambiguous specifications for the same reasons that we don't write bug-free code, and need formal validation.
Brooks talks about this in _Mythical_Man-Month_... if you really could "just implement the specification", then the specification itself would be complete enough to serve as your code. There will always be bugs in both.
That "sheer amount of hardware validation" is always less-than-perfectly spread across a whole lotta billions of transistors, and combinatorics is a harsh mistress.
Me too. Hardware bugs that arise out of unanticipated module interactions are understandable. But this is a "you had one job" moment.
It's most likely a quick patch for a previous bug where the RNG would fail but misreport it as a success with all 0 bits. The quick patch is to make all 0s a failure.
The verification plan did not make 0 a bin to cover.
Almost definitely an off by one bug.
I'm getting 16-bit zeros on my Zen 3 chip (+1:3821, 0:3893, -1:3895), I will wait to get some statistically significant samples for the 32-bit values and update the forum thread. Maybe it was fixed after Zen 2?
Does anyone have access to an HPC cluster with thousands of Zen2 chips? We might want to check 64-bit ones with that - should take just a couple years depending on the size of the machine.
Anyone from the High-Performance Computing Center Stuttgart willing to play on the 720,320 Zen2 cores?
AMD's random number generator probably can't generate a 0 ;)
Anyways, I think it is good practice to consider the output of any hardware RNG to be biased and to only use it indirectly as a source of entropy. The actual numbers come from a PRNG, secure of not depending on your needs, that have a guaranteed distribution.
It can still cause problems if badly used, or, ironically fix problems if badly used in a different way.
Chased a similar bug in a KDF once and only caught it by histogramming the 16 bit draws, statistical suites never flagged it.
Your suites didn't even do a https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_tes... which is what you did?
I have a couple questions:
Looks like they tried 16-bit numbers. Does the odd behavior happen also on 32 and 64 (might take a long time to check - I'd start scratching my head after a couple hundred years of no zeroes) ones? Is the zero masking as some other fixed number, increasing its output count? Is RDRAND implemented as multiple reads of an internal state so that a larger random number takes longer?
That first question is answered in the thread:
> Yes, when using either 32-bit or 64-bit number, the lowest portion can output a zero, as I suggested on the attached example file as a modification to fix the problem. But a true zero (fitting the requested size), on AMD, never happens.
Another person (on page 2) confirms those results on an older AMD processor (but failed to reproduce on a very new one, 9950X3D).
Another random boundary case: SQLite's RANDOM() won't generate the minimum i64 value, because:
Since RANDOM() is used with ABS(), that floor value is lopped off. (Can you imagine if it weren't, and you got a bug 1 in every 2⁶⁴ calls?)
https://sqlite.org/lang_corefunc.html#random
https://sqlite.org/forum/forumpost/4c0b09747a670652
[flagged]
[flagged]
[dead]
[dead]
So what? The point is to be non predictable not to pick all the numbers in the range with exactly the same probability. Would it be a problem if it never generated 16542?
Consider an 8-bit RNG.
By your argument, it would not be a problem if the RNG never generated 0. So, it must follow that it would also not be a problem if it never generated {1, 2, 3, ..., 253}.
That means that our RNG now only generates the values 254 and 255. Which of the values is generated is unpredictable on any given call. However, 7 of the 8 output bits are now always fixed and so completely predictable. Can you imagine how an attacker could exploit that?
Failing to generate only the number 0 is a weaker version of the same class of flaw.
This is the “what’s the big deal if I lost $100k in a casino, it’s really the same thing as if I had lost $5” argument.
I don’t think you can rebut “you only lose one of many values” with “it’s the same as only having one left”.
3 replies →
> So, it must follow
It certainly does not.
A never-zero RNG is something one should know about, so that it can be mitigated if necessary, but it's not inherently a dealbreaker.
The value space goes from 2^16, 2^32, 2^64 to 2^16 - 1, 2^32 - 1, and 2^64 - 1 respectively.
The bug has zero practical impact.
2 replies →
“Pick all the numbers in the range with exactly the same probability” is a very important property of RNGs. Yes, skipping 16542 would be equally bad.
You can frame it around being “non predictable”, but then you need to define those words. It’s not, for example, a poker game where it’s trying to bluff you, right? It’s also not about just making predictions < 100% reliable and declaring victory. It must specifically make all predictions no better than random guessing, and that entails picking any number in range with equal probability, otherwise predictions like “it will be {hot spot}” or “it won’t be {cold spot}” do better than random chance. In this case, specifically, I can predict with 100% accuracy that the result won’t be 0, and that’s a flaw in its unpredictability. I can also predict a bunch of other things with slightly higher accuracy than random guessing, like that it will be odd or greater than max ÷ 2.
"Random" is used by most people to mean "random with an even distribution".
A weighted die is still random, but with an uneven distribution. This is effectively a 2^16-sided, weighted die.
My argument to follow your analogy is.
It's not a 2^16-sided weighted die. But a 2^16 - 1 sided fair die.
I am not saying there is no bug. I am saying the bug has no practical impact.
Sure if you are that one guy that is getting these values raw from the instruction and comparing to zero for some purpose then you are in trouble. But I am pretty sure no one is doing that, especially given that the bug surfaced after 6 years of millions of users.
2 replies →
What are you talking about? The point is in fact to pick all the numbers in the range with exactly the same probability.
See section 7.3.17 of the Intel SDM, and how NIST SP800-90A (which the SDM refers to) defines "random number".
Betty from accounting will have words.
What does Betty from accounting care about RNGs?
1 reply →
That may well be a problem, yes.
“Predictable” and “not pick all numbers in range with exactly the same probability” are synonyms here.
I would be very concerned if an RNG simply produced a natural 0.
I would be very concerned if an RNG simply produced a natural 1.
I would be very concerned if an RNG simply produced a natural 0xf379aa46d1086bca.
I would be very concerned if an RNG simply produced a natural 2.
Why would that be any more concerning than the RNG producing any other number?
"Maybe some C?O person executed RDRAND"
is an amusingly gross misunderstanding of what a C?O person does on a daily basis.
0 is not a number, it's undefined
It is literally the first Peano axiom that 0 is a natural number. In fact it is the only natural number that is defined in and of itself. All other natural numbers are defined by using the “successor” operation to add things to zero.
https://en.wikipedia.org/wiki/Peano_axioms
[flagged]
Are you a time traveler from the 5th century?
353 BCE
1 reply →
the what?
That's a thing some people used to believe, I guess some of them still do.
I wonder if this, or something like it, is the issue:
> 32-bit XorShift should usually not be used to produce 32-bit numbers, because it only produces each number once, and never produces zero.
(From this page I found while trying to see if this was a common flaw in PRNGs: https://www.pcg-random.org/other-rngs.html )
Usually you do "rdrand % <some-number>" anyways, and in that case you will still get zeroes. True, your result might be skewed by 1/(maxint/some-number) but I guess that's not a big problem in practice
If you want uniformly-distributed random numbers, computing the remainder works only when the modulus is a power of two.
Otherwise, a slightly more complicated algorithm is necessary, where you reject a range of numbers either before computing the remainder (to make the set of possible values a multiple of the modulus) or after computing the value modulo some power of two (to reject values greater than your target).
Besides these 2 variants based on the remainder of division of integers, there are also 2 corresponding algorithms using multiplication of the input interpreted as a fraction, followed by taking the integer part of the result.
Example: to get a number between 0-2 (3 values) with a 4-bit RNG (16 values, 0-15) you can split the set 0-14 into 3 groups of 5 (doesn't matter if you use modulus or divide) but if you get 15 you need to re-roll.
The probability of generating a zero is incredibly low if you use the normal distribution curve.
So it is not necessarily that it doesn't generate zero, they did not run enough times to increase the probability of actually generating a zero.
From what I can see they were trying to generate 16bit integers, so the probability is 1 in 65536 and they were running the test for 11 hours.
You definitely would expect a roughly equal number of 0s as any other of those numbers since it's uniformly distributed. And definitely not 0
> You definitely would expect a roughly equal number of 0s as any other of those numbers since it's uniformly distributed.
How would random numbers be uniformly distributed?
9 replies →
This also seems to happen for 16 and 32 bit numbers, so you should be able to see zeros easily.
They also write:
> Running the same programs on an Intel processor, and the 0's are there with no problem.
Why would it be a normal distribution?
should be a discrete uniform distribution right?
It is just possible they decided crypto code that uses it was safer to skip zeros. (Whist mathematically it should be no more likely; it is vastly more likely someone will actually try that key).
It is also possible that their code was generating too many zeros and the easiest fix was to discard them all.
Can you clarify what you mean by "it is vastly more likely someone will actually try that key"?
I'm guessing you don't think there are people calling rdrand in a loop and throwing away the output with high probability except when it is 0, but I can't see how else you imagine people would be vastly more likely to use the output when it is 0?
In lots of scenarios I know the software used to generate the key; the only unknown is the random numbers used. If I am searching for weaknesses it is highly likely I would try keys with different seeds; zero, one, are going to me much more likely choices here then hoping I can guess the right values.
5 replies →
this is not how crypto works