, 22 min read
“Cracking” random number generators (xoroshiro128+)
25 thoughts on ““Cracking” random number generators (xoroshiro128+)”
Mads Andersson says: Could a cryptographic rng be “cracked” with the help of a quantum computer? What would the code look like if you were trying to find the unhashed variable that’s Sha-256 encrypted? A normal computer wouldn’t solve it for hundreds of years. Just wondering what the code would look like.
-
I am unaware that quantum computing can crack sha-256. Do you have a reference?
Sebastiano Vigna says: BTW, can you substantiate your claim
XorShift128+ is a weak random number generator with faulty statistical properties.
There’s a published paper with BigCrush results. So I expect you have in mind another paper.
-
Thanks for your comment. I have rephrased to “XorShift128+ is a relatively weak random number generator. Blackman and Vigna recommend upgrading to the stronger xoroshiro128+.” You wrote: “This generator has been replaced by xoroshiro128plus, which (…) has better statistical properties.” Moreover, in my tests, it fails big crush, e.g., MatrixRank. It also fails Pratical Random. I have another blog post on this.
-
Sebastiano Vigna says:
I’d like then to see the code, because it doesn’t fail my BigCrush tests at 100 starting points, and TestU01 results are very replicable.
Yes, I know that some far-range test of PractRand fail—that’s why suggest xoroshiro128+, which doesn’t. The level of concern about those specific tests for me is very low—lower than, say, not generating all 64-bit values or failing more interesting tests.
-
Daniel Lemire says: The level of concern about those specific tests for me is very low
Sure. That’s very reasonable.
Great work Daniel, just by looking at the comments your findings made quite a mess. Debates are interesting and I think that there should be stronger algorithms when it comes to randomness.
Sebastiano Vigna says: Dear Daniel,
Do you think I’m stupid? Or I can’t read? The complete quote from the paper is
“are usually easy to crack by standard statistical tests”
Of course, “crack” here has nothing to do with what you mean. L’Ecuyer has decades of experience and would never use words so carelessly.
The other quotation is another nice trick, but short lived: it is a famous paper, and the actual title is
“Cracking” a random number generator.
Notice the quotes. The author know what’s taking about.
This is not a scientific discussion, and I’m out of it. You can of course delete this comment (as you disabled replies in the other thread).
-
Of course, “crack†here has nothing to do with what you mean. L’Ecuyer has decades of experience and would never use words so carelessly.
Ok, so if I find that a generator fails at a statistical test, I can say that I cracked it and you will find the term acceptable?
I personally prefer my own use of the word “crack”.
Notice the quotes. The author know what’s taking about.
It is true that he uses quotes whereas I did not except in my first use the term, but Reeds (who is famous, of course) uses the term with exactly the same meaning as I do here. I’ll revise my blog post so that there are quotes around the word “crack” on every single use of the term. This will put me on par with Reeds.
This is not a scientific discussion, and I’m out of it.
I’m sorry if you are offended. That was not my intention.
You can of course delete this comment (as you disabled replies in the other thread).
I did no such thing as disabling replies in any thread regarding this post.
my first dev work was for a startup online gambling site. and yes, this was one thing they highlighted – we didn’t rely on XorShift128+ for same reason you covered.
Big thanks for code on the Github.
I’ve looked once at xoroshiro128+ and couldn’t believe what I saw. Why on they decided to sum and return result before shuffling? What was the rationale for such horrible decision?
If I would make xoroshiro128+, code would be
uint64_t next(void) {
const uint64_t s0 = s[0];
uint64_t s1 = s[1];
s1 ^= s0;
s[0] = rotl(s0, 55) ^ s1 ^ (s1 << 14); // a, b
s[1] = rotl(s1, 36); // c
return s[0] + s[1];
}
Can you elaborate?
LOL that’s exactly the same generator, with the output shifted by one position. 😂
What you suggest is actually what happens in the xorshift128+ algorithm. Essentially that is the only difference of the two algorithms.
If you read their website they say that the change makes the algorithm performance better due to CPU pipelining instructions.
Essentially the shift instructions will happen out of order and the calling code will get the result faster
I really cannot understand all this fuss. For 20 years people have been proud of “maximal equidistribution”, a nice property that tells you that the generator produces all possible distinct k-tuples it can actually generate, given its state space. The Mersenne Twister, the WELL family, have all been designed with this goal. Which of course implies that after any k outputs you can predict the generator. Now this property has renamed by this lady “crackable generators”.
Whatever.
If you mean that “I (Daniel Lemire) make a fuss”, then I have to disagree with you. If you mean that O’Neill is making a fuss, then please be specific.
Here is what I wrote:
I trust that you are in agreement with this statement?
You write: “the generator produces all possible distinct k-tuples it can actually generate, given its state space (…) Which of course implies that after any k outputs you can predict the generator.”
I am trying to parse this statement and I am having difficulties. What is the value of k in this instance (xoroshiro128+)?
Hey, Daniel, I said “this lady”. Clearly I’m not referring to you!
I completely agree with your statement. But your title is “Cracking random number generators (xoroshiro128+)”, not “Cracking the Mersenne Twister”. And “cracking” the Mersenne Twister is even easier. So I think that the way you are presenting the material is very misleading. But, hey, it’s your blog.
Do you agree with me that renaming “equidistributed” (20 years of history) with “crackable” is a bit of a stretch?
xoroshiro128+ is not maximally equidistributed in its maximal dimension: it emits all values the same number of times, but not all pairs of values (it is 1-equidistributed, but not 2-equidistributed). For instance, the Mersenne Twister is: it’s actually stated in the title of the paper:
“Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator.”
So after 623 inputs you can predict, and it’s impossible to do it before due to state space size (every 622-tuple is followed by all possible values).
I’m not a big fan of equidistribution: I argued in my paper on TOMS that’s vastly overestimated as a feature of a PRNG. I got through *four* rounds of refereeing in two years to get my ideas through. But they were discussed with expert in the fields before being published, as it should happen.
I completely agree with your statement. But your title is “Cracking random number generators (xoroshiro128+)â€, not “Cracking the Mersenne Twisterâ€. And “cracking†the Mersenne Twister is even easier. So I think that the way you are presenting the material is very misleading. But, hey, it’s your blog.
It is less interesting to crack SplitMix or the Mersenne Twister because it is obvious how if you have some working knowledge of computer arithmetic. (And see James Roper’s post about cracking the Mersenne Twister.)
Do you agree with me that renaming “equidistributed†(20 years of history) with “crackable†is a bit of a stretch?
I’m sorry if you are offended by the terminology, that was not my intention.
So you are saying that “equidistributed†is synonymous with being computationally easy to invert?
No, but maximally equidistributed in the output dimension implies predictability, and all examples I’ve seen so far for generators with large state space involve some kind of equidistribution.
I think it’s very dangerous to make people believe that there are “easily predictable”, “less easy to predict” and “secure” generators. There are secure and non-secure generators, period. The difficulty of predicting a generator, given that it can predicted feasibly, is irrelevant. You want secure? Use Fortuna, or something like that. Making people believe that a *slight less predictable* generator (like PCG) will solve their security problems will meet harsh comments from people working on security.
It feels to me like there is no significant disagreement between us that I can see.
I take it that you might feel that using the term “cracking” might be pejorative. But xoroshiro128+ is not secure (by your own admission, surely), so it is reasonable to talk about “cracking it”.
You object that the same can be said of many other functions, but my posts says so, explicitly. Let me recopy my statement once more:
You would prefer, it seems that I give as a title to my post “xoroshiro128+ is maximally equidistributed”. But I don’t think it is correct. That’s not what I illustrate. And I think you agree.
You write: “You want secure? Use Fortuna, or something like that.” Again, please go back to what I wrote: “Cryptographic random number generators should probably be used if you want to open a casino.”
We are saying the same thing!
I’m just saying you are “cracking” non-secure generators as much as you can crack a figue (as opposed to a walnut). I wouldn’t use that word in a referred scientific paper. But then again, it’s your blog!
L’Ecuyer uses the word “cracking” in some of his peer-reviewed papers in a similar (non-cryptographic) context.
In any care, we are arguing the choice of a term which feels like unsubstantive to me as far as disagreements go.
Can you point me at the papers please? I can’t find anything like that by keyword search…
See e.g.,
P. L’Ecuyer, Random Number Generation, Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, eds., Second Edition, Springer-Verlag, 2012, 35-71.
Relevant quote:
You find other instances by other authors such as
J. Reeds, Cracking a random number generator, cryptologia, 1977
He goes on to explain how to “crack” simple generators (that have not been claimed to be cryptographically strong).
James Roper has a whole Cracking Random Number Generators series. He shows how to crack the Mersenne Twister among other things.
I believe that it is a very reasonable term. You could, in fact, define a non-cryptographically secured generator as being easily cracked.
Note that people will definitively use such non-cryptographically strong generators for applications where a cryptographically strong generator is needed, precisely because they do not understand that they can get cracked.
What I illustrated in this blog post is not entirely trivial. Many engineers could very reasonably expect it to be difficult to infer the seed from the outputs of xoroshiro128+.
We need to educate people, and if the term “cracking” sounds a bit scary, then I say “good!”.
I submit to you that cryptographers will approve of my message. What they would criticize, if this would go through formal peer review… is the triviality of it all… They would say “oh! but of course it is easy to crack…”
They would point me to Reeds (1977) and say “we were cracking simple generators decades ago”.