alt Hacker NewsAMD's random number generator can't generate a 0?
Comments
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.
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.
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.
Embarrassing, but probably little practical impact, since these hardware random numbers are typically not used directly and instead seed a CSPRNG.
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?
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
Chased a similar bug in a KDF once and only caught it by histogramming the 16 bit draws, statistical suites never flagged it.
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?
[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?
"Maybe some C?O person executed RDRAND"
is an amusingly gross misunderstanding of what a C?O person does on a daily basis.
I would be very concerned if an RNG simply produced a natural 0.
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
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.
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 )
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.
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!