Posted by BruceEel 7 hours ago
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”.
If you want a casino example, then consider a roulette wheel that always lands on 36 but still pays out as usual. I think you'd want to play on it. Now consider one that always lands somewhere between 30 and 36. Still worth it, right? With careful bets and a good starting float you're still coming away from the table up (with a very high probability).
In fact for a roulette wheel you only need two dead pockets for the player to get an edge. Bias is exploitable.
When the original point was that a tiny fractional loss in an RNG is not going to make a practical difference. Which I believe is also true. And it is also true that a large loss in an RNG is catastrophic.
They can both be true.
And roulette is 2 out of 38, 5.2%. That’s 17 times more than the 1/256 here, which was already a simplification of the (I think) 1/65536 in question.
> a tiny fractional loss in an RNG is not going to make a practical difference
I'm not so sure this is true. I don't think either of us is in a place to say whether this vulnerability has practical applications or not. A 1/65536 bias might seem like nothing important to you. It seems very far from nothing to me, in a world where an attacker can potentially generate terabytes of data.
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 bug has zero practical impact.
You could be correct that the very small bias here is not enough to be exploitable. But, given the history around this, it would be wrong to handwave it away as trivial.
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.
See section 7.3.17 of the Intel SDM, and how NIST SP800-90A (which the SDM refers to) defines "random number".
A weighted die is still random, but with an uneven distribution. This is effectively a 2^16-sided, weighted die.
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.
pick = rnrand16() - 0x7fff
if pick > 0...
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.
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
How would random numbers be uniformly distributed?
Think about the odds of a uranium atom decaying in a given second. Certainly a random event, yet for most seconds, the value is False, not True.
With a few (say 10, so 655360 runs), you will not get a uniform distribution, and some numbers (like 0) might not appear.
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?