Rendered at 11:47:18 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
jstanley 1 hours ago [-]
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 think that one is referencing a run of six 9's in the digits of pi, which occur much earlier than one would "expect" them to show up in a truly uniform distribution.
matja 27 minutes ago [-]
CVE-2008-0166 (Debian OpenSSL Predictable PRNG Vulnerability) inspired xkcd/221 but this sort of thing happens a lot :)
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
jstanley 47 minutes ago [-]
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.
goalieca 43 minutes ago [-]
You should be using &0xFFFF for masking. Your mod is off by 1 too.
RandomOnyx 46 minutes ago [-]
How about* rdrand32()%65536? Taking the remainder by 65535 doesn't take the lowest 16 bits after all
*: missed a word the first time around
rbanffy 21 minutes ago [-]
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.
strenholme 26 minutes ago [-]
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.
stingraycharles 19 minutes ago [-]
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.
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?
CodesInChaos 1 hours ago [-]
Embarrassing, but probably little practical impact, since these hardware random numbers are typically not used directly and instead seed a CSPRNG.
leonidasrup 19 minutes ago [-]
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."
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?
rbanffy 8 minutes ago [-]
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?
20k 53 minutes ago [-]
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
hnacobsxph 36 minutes ago [-]
Chased a similar bug in a KDF once and only caught it by histogramming the 16 bit draws, statistical suites never flagged it.
29 minutes ago [-]
1 hours ago [-]
Plainharbor21 54 minutes ago [-]
[dead]
Ledgermellow 47 minutes ago [-]
[dead]
dark-star 1 hours ago [-]
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
throwawayffffas 51 minutes ago [-]
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?
gnfargbl 36 minutes ago [-]
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.
brookst 17 minutes ago [-]
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”.
throwawayffffas 8 minutes ago [-]
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.
Hugsbox 29 minutes ago [-]
That may well be a problem, yes.
swader999 34 minutes ago [-]
Betty from accounting will have words.
throwawayffffas 7 minutes ago [-]
What does Betty from accounting care about RNGs?
antiloper 43 minutes ago [-]
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".
ExoticPearTree 1 hours ago [-]
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.
blensor 1 hours ago [-]
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
zygentoma 1 hours ago [-]
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.
matja 1 hours ago [-]
Why would it be a normal distribution?
throawayonthe 60 minutes ago [-]
should be a discrete uniform distribution right?
60 minutes ago [-]
m_antis89 29 minutes ago [-]
0 is not a number, it's undefined
ZiiS 1 hours ago [-]
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.
jstanley 49 minutes ago [-]
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?
ZiiS 16 minutes ago [-]
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.
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!
Most of the console hacking talks are great, both informative and entertaining.
That presentation is awesome though, worth a watch either way!
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
*: missed a word the first time around
To prove it, we'd need to examine the chip and its microcode.
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.
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?
" 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
Anyone from the High-Performance Computing Center Stuttgart willing to play on the 720,320 Zen2 cores?
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.
I don’t think you can rebut “you only lose one of many values” with “it’s the same as only having one left”.
The bug has zero practical impact.
See section 7.3.17 of the Intel SDM, and how NIST SP800-90A (which the SDM refers to) defines "random number".
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.
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
They also write:
> Running the same programs on an Intel processor, and the 0's are there with no problem.
It is also possible that their code was generating too many zeros and the easiest fix was to discard them all.
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?