ERL-603: Xoroshiro128+ Fails PractRand Even When Truncated

[OTP-Maintainer]

Original reporter: sdl.web@gmail.com Affected version: OTP-20.0 Component: stdlib Migrated from: https://bugs.erlang.org/browse/ERL-603

---

I ran into this article http://www.pcg-random.org/posts/xoroshiro-fails-truncated.html and am curious if the algorithms used by the rand module suffer any of the problems? Thanks.

[OTP-Maintainer]

raimo said:

The default {{rand}} generator is Xoroshoro116+.  It is a diminished special variant from the author of Xoroshiro128+, so it should have similar flaws, if there are any.

That article seems to be a sided view from the writer of a competing PRNG named PCG. I will not take sides in this discussion and do not have the knowledge to see who is right, but sense that both sides may be biased.

Most of the article attacks variants of Xoroshiro128+ that the author has modified himself, so those could be disregarded, if you are so inclined, as nonsence.  The part using upper 32 bits of unmodified Xoroshiro128+ can maybe be disregarded with the motivation that prof. Vigna said no *systematic* failures.  He says it fails randomly and should do so, or it would not be random.

I do not know how much of this that is a feud between M. E. O'Neil and Sebastiano Vigna, and how much that is hard facts...

It might be an idea to extend that {{rand}} module with some of O'Neil's algorithms, though...  Using ChaCha sounds interesting - should be unpredictable. Alas not high on my priority list.

[OTP-Maintainer]

raimo said:

The previous {{rand}} default algorithm, still available, named {{exsp}} (the Xorshift116+ corrected variant), is recommended as a good alternative (actually Xorshift128+)  by the PCG author.  So you could choose that, if in doubt.

[OTP-Maintainer]

sdl.web@gmail.com said:

Many thanks for the detailed comments. I thought it was someone genuinely point out flaws in Xoroshoro's. Didn't realise there was a feud of some sort.

I think this bug may be closed.

[OTP-Maintainer]

raimo said:

It may be genuine flaws.  Or a feud.  I can not know.

I do not think we have seen the last of this debate...

Thank you for pointing out the article!

[OTP-Maintainer]

raimo said:

I have contacted one of the creators of Xoroshiro+ (S. Vigna), and took some time during the weekend to read M. E. O'Neill's paper.

To me it seems the debate is about whether some known properties of Xoroshiro+ can be regarded as flaws.

O'Neill submitted a paper in 2014 to https://toms.acm.org and was rejected.  She may have annoyed PRNG people by using terms from cryptography where not applicable (in the field of Pseudo Random Number Generators).  The paper claims that many PRNGs are "trivially predictable", which I think is an already known property, and that the pcg-random.org PRNGs are not "trivially predictable" (but still not cryptographically unpredictable) while still being fast.

S. Vigna notes that O' Neill's paper was rejected, doubts O' Neill's benchmark results and thinks the pcg-random.org page has got / have had a bit too "boombastic claims".

So maybe the PRNG establishment dismisses O'Neill because of this middle ground approach of "not trivially predictable" but not cryptographically unpredictable that has no clear definition.

It boils down to what the PRNG is used for, and I think O'Neill has got a point (how important is the question) in that one migh for instance have a randomized quicksort that could be tricked into O(N^2) time complexity by external data from a malicious party, if the PRNG is trivially predictable.  And that this might be a problem that the PRNG establishment thinks should be solved with cryptographically unpredictable PRNGs, while O'Neill argues that they are to slow to be used e.g for a randomized quicksort and that no PRNG should have to be "trivially predictable".  And here the PRNG establishment argues that it costs too much performance to get into this unclear middle ground with unclear benefits...

It will be interesting to see how this smackdown develops...

I am interested in adding a cryptographically unpredictable PRNG using e.g AES-256, and to add some selected PRNG from O'Neill just in case, but it will be hard to get this prioritized...

[OTP-Maintainer]

jj1bdx said:

Some thoughts of mine, as a person who tested Vigna's PRNGs before OTP 18:

* I agree with Raimo's impressions, and I second his opinions and views.
* I believe the notion of _trivial predictability_ is still premature. 
* Predictability is not easy to define, and theoretically, all non-cryptographic PRNGs are predictable in some ways, so it should be defined quantitatively, e.g., by algorithmic complexity.
* For non-cryptographic PRNGs, the primary and only characteristic which should be assured is the uniformity, or the adherence to the given distribution condition, e.g., Gaussian distribution). Nothing else should be expected.
* Cryptographic security or non-predictability must be given explicitly by cryptographically hard functions such as by the one-way hash functions or by the strong cryptographic functions (AES, ChaCha, etc.).

[OTP-Maintainer]

jj1bdx said:

Possible contingency plans so far when Xoroshiro+ ({{exrop}}) is compromised (though I seriously doubt whether it would happen):

* Use {{exsp}}
* Use {{exs1024s}}
* Use [sfmt-erlang|https://github.com/jj1bdx/sfmt-erlang]
* I`ve terminated the development, but you can also use [tinymt-erlang|https://github.com/jj1bdx/tinymt-erlang]

[OTP-Maintainer]

raimo said:

I have for fun implemented a cryptographically non-predictable PRNG by encrypting an 128-bit counter with AES256.  When I cache the values I get performance about 0.6 times the speed of {{exrop}}/{{exsp}}, which is a bit faster than {{crypto:rand_seed_alg(crypto_cache)}} and significally faster than {{exs1024s}} (1/3 the speed of {{exrop}}.

This generator's basic operational principle is actually the same as Bruce Schneier's Fortuna generator https://www.schneier.com/academic/fortuna/

The {{crypto_cache}} generator I mentioned above uses strong random bytes and caches them.  It comes in OTP-21.0 and is also faster than {{exs1024s}}.

So, if you want speed and repeatability, use the default generator {{exrop}}.  This class of generators is externally predictable, though.

If you want cryptographical non-predictability use today {{crypto:rand_seed()}} (1/10 the speed of {{exrop}}, or from OTP-21.0 {{crypto:rand_seed_alg(crypto_cache)}} with about half the speed of {{exrop}}.  This generator is not repeatable, though.

If you want cryptographical non-predictability but still repeatability the new generator I wrote should work.  But since it is repeatable the seed is a cryptographical secret, and it also does not do any re-keying that is important for forward secrecy (if I got that right), so the question is how strong it's non-predictability can be in reality?  The properties of non-predictability vs. repeatability does not play nicely together...

What on earth would this kind of generator be useful for?  Exactly the same question should apply to the O'Neill pcg-random.org generators, and they can furthermore not claim to be cryptographically non-predictable...

Since I can not figure out a use case I am reluctant to add my new generator with the project name {{crypto_aes}} to the {{crypto}} application...