A Quick Look at Xoshiro256**

On May 4, David Blackman and Sebastiano Vigna announced new members of the Xoroshiro family and a new test for random number generators (based on the z9 test from gjrand) that their previous work fails, all described in a new paper. They claim to have now developed an “all-purpose, rock-solid generator”. In this post, having had less than a day to review their work, I'll present a few preliminary thoughts on this news, mostly looking at their best new generator, xoshiro256**.

Flaws in Prior Work

One good thing about Blackman & Vigna's new paper is that they finally seem to be conceding that Xoroshiro128+ is a flawed generator. They have also updated the constants used in Xoroshiro128+ to create a new version of this PRNG (somewhat confusingly labeled “Version 1.0”), with different output, that gives some improvements to its performance in their new statistical test (which it still fails). Vigna appears to have also edited the Wikipedia page for Xoroshiro128+ to reflect the updated comments and caveats in the updated source and delete some of the other content from the page.

One thing Vigna doesn't seem to have conceded is that his interleaving-only approach to testing with TestU01 is insufficient, and that when a more comprehensive testing approach is used, Xoroshiro128+ fails TestU01.

But enough about the old, what about the new…? Have they really now come up with an all-purpose, rock-solid generator?

Some Good Things about xoshiro256**

Blackman & Vigna claim that xoshiro256** is fast. I haven't tested its speed, but I have every reason to believe that it's quick. The four-dimensional equidistribution seems like a neat property, too.

Some Bad Things about xoshiro256**

So what about the bad things? There are a few things that should be no surprise, but there is one thing that surprised me a good deal.

Typical LFSR Issues

Being based on a (G)LFSR, this PRNG will always have the “bad initializations” problem. In particular, you must avoid initializing it with an all-zeros state, but LFSRs always have “zeroland issues” to some degree.

Here's an example of the underlying xoshiro256 generator struggling as it crosses zeroland; the 32 lines below show how the generator moves from one state to the next. Each line shows the 256-bit internal state of the generator.


If state transitions were properly random, it would appear that each line was completely independent of the previous one, but you can see that we have a significant cluster of states with lots of zeros. There are many similar state sequences. Here is another:


There is also some clustering around the all-ones state (although the clustering effect is less pronounced):


Thus, in behavior that is typical for an LFSR, the state-space of the underlying xoshiro256 generator is littered with statistically very unlikely clusterings of states. It's what I mean when I sometimes say that LFSRs are “too lumpy”—that all-zero states tend to be clustered together.

If all-zero states tend to be clustered together, that means they won't be showing up elsewhere, with subtle effects on the entire generator. Of course, with 256 bits of state, we would expect this generator to be well into “too big to fail” territory where the flaws are there in theory but hard for a typical PRNG test suite to discover in practice.

A good output function can do a lot to mask these issues, so we should move on to looking not just at the underlying (G)LFSR but the at xoshiro256** as a whole.

Trivial Predictability

Like their previous work, xoshiro256** is trivially predictable. That means that given only four outputs from this PRNG, we can know its prior outputs and predict all future outputs.

I know that Vigna has argued that trivial predictability is a nonissue; that it doesn't matter to anyone. But that's not what I've found. In my conversations with most programmers (and nonprogrammers) the idea of a PRNG that can be easily predicted seems like an oxymoron. But on the other hand, it is true that for many situations (e.g., running a physics simulation), predictability probably doesn't make the slightest difference—after all, the physics simulation code isn't going to turn adversarial and try to outwit the PRNG it uses. But Vigna claims to have made an “all-purpose, rock-solid generator”. An all-purpose PRNG may have to work in a world where there are things like algorithmic complexity attacks and thus not being trivially predictable matters.

On the positive side, we can use this predictability to have some fun and make it do party tricks. If we set the initial state array s[] to { 0x01d353e5f3993bb0, 0x7b9c0df6cb193b20, 0xfdfcaa91110765b6, 0xd2db341f10bb232e }, we get a nice authorship notice letting us know who wrote the generator:

0000  dd 51 b2 b7 d9 30 3a 37  eb d9 63 66 a6 70 fd 50  |.Q...0:7..cf.p.P|
0010  26 e7 29 1f 21 21 c0 35  36 c1 2d 03 77 b1 41 d3  |&.).!!.56.-.w.A.|
0020  43 33 2f 77 f7 fe 97 01  1e 93 c3 ce e4 df fc c4  |C3/w............|
0030  db 6c 06 54 08 25 6f 5a  0e 86 82 4d 1c 72 c9 50  |.l.T.%oZ...M.r.P|
0040  20 ae ca 84 d9 24 87 b9  51 96 93 ae ae d2 8f ce  | ....$..Q.......|
0050  57 37 c1 5c f4 cc 5c d6  2a 29 72 cb f0 c5 f8 f8  |W7.\..\.*)r.....|
0060  46 1e 33 a2 5d b1 66 b4  15 6f 3b ed 93 e4 70 ba  |F.3.].f..o;...p.|
0070  11 be 24 b0 20 64 13 86  71 72 92 31 d8 be 03 a9  |..$. d..qr.1....|
0080  78 6f 73 68 69 72 6f 32  35 36 2a 2a 20 62 79 20  |xoshiro256** by |
0090  42 6c 61 63 6b 6d 61 6e  20 26 20 56 69 67 6e 61  |Blackman & Vigna|
00a0  bd 9a f9 bd 3a 79 52 d3  76 50 5e 1e 55 6a 36 48  |....:yR.vP^.Uj6H|
00b0  9f c0 39 c2 5c db 99 a3  5c d5 4b a2 15 35 53 9c  |..9.\...\.K..5S.|
00c0  da dd c6 0b bf 33 ef a7  82 eb 06 52 6d 6d 31 2b  |.....3.....Rmm1+|
00d0  24 7a 0c 3f 70 43 d1 6f  aa c6 88 7e f9 30 ee ff  |$z.?pC.o...~.0..|
00e0  22 31 af c6 1f e5 68 22  e9 6e 30 06 f6 7f 9a 6e  |"1....h".n0....n|
00f0  be 19 0c f7 ae e2 fa ec  8e c6 22 e1 78 b6 39 d1  |..........".x.9.|

Interestingly, if we run it with an initial state of { 0x4685307f2e2c9b43, 0xa999f3abba9e66fe, 0xf74ff5fab0e603da, 0x6dc878990b1ea4db }, we get:

0000  68 54 0d ec e6 97 ea 07  9c 0f 5c 78 31 0e 43 50  |hT........\x1.CP|
0010  6e e0 96 20 76 bd 6f 4e  a8 12 59 5b 35 32 a1 f4  |n.. v.oN..Y[52..|
0020  27 c7 28 c3 e4 75 64 e6  32 5f 75 f2 bb ec fb d1  |'.(..ud.2_u.....|
0030  59 47 b1 87 dd 70 fc 8d  7f 94 f6 f4 62 d2 9a ae  |YG...p......b...|
0040  e5 7b 44 63 a2 63 e3 f4  67 1d 22 2b 8b 7b ad 55  |.{Dc.c..g."+.{.U|
0050  0b 08 cb 1e ac 02 d7 e6  80 47 38 8b 0d 7e 3d 3f  |.........G8..~=?|
0060  f8 24 f5 c2 83 f8 74 36  f6 64 a0 58 a8 e1 a9 c0  |.$....t6.d.X....|
0070  59 2f ca 6d 2c e7 51 94  9d cd d6 be c3 68 08 62  |Y/.m,.Q......h.b|
0080  20 20 50 4c 45 41 53 45  20 64 6f 6e 27 74 20 20  |  PLEASE don't  |
0090  20 6d 75 6c 74 69 70 6c  79 20 62 79 20 35 37 20  | multiply by 57 |
00a0  f5 e4 2f cc 41 8f 49 8c  2a 10 7c 47 7c af 50 1f  |../.A.I.*.|G|.P.|
00b0  ee 88 32 34 ea 58 e7 b6  5b 2a 55 c2 20 f7 b7 c2  |..24.X..[*U. ...|
00c0  1e f6 9c 25 81 fa 2e 30  29 c6 a8 4e e2 56 f8 f3  |...%...0)..N.V..|
00d0  1f 58 09 46 b3 b3 74 95  2c bf e1 c3 de 3b cc 98  |.X.F..t.,....;..|
00e0  1a be 7b 72 d0 21 45 ad  69 e4 60 e3 15 ad 68 59  |..{r.!E.i.`...hY|
00f0  89 c6 88 d3 39 40 fb ec  76 e6 34 d8 fc d2 5d 02  |....9@..v.4...].|

Which provides a great segue to our next, and worst issue.

Invertible Output Function — Don't Multiply by 57

The ** output function for xoshiro256** is coded as follows:

result_starstar = rotl(s[1] * 5, 7) * 9

What may be less obvious is that this output function is trivially invertible. We can rearrange the above as:

s[1] == rotl(result_starstar * 0x8e38e38e38e38e39, 57) * 0xcccccccccccccccd

This code works because 0x8e38e38e38e38e39 is the multiplicative inverse of 9, 57 is the rotational inverse of 7, and 0xcccccccccccccccd is the multiplicative inverse of 5.

In other words, all the work that the output function does to improve the output can be easily undone, returning us to the original (G)LFSR with all of its flaws.

But in fact we don't have to fully invert the output function to see problems. I tried just multiplying by 0x8e38e38e38e38e39 and found that xoshiro256** failed statistical tests. Then I tried just multiplying by 0x8e39 and that failed too. Finally, I tied multiplying by 0x39 (a.k.a. 57) and that failed as well—in only 9.5 seconds.

Here's the run:

unix% ./xoshiro256ss57  | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x3a44e83d
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0x3a44e83d
length= 128 megabytes (2^27 bytes), time= 2.0 seconds
 no anomalies in 148 test result(s)

rng=RNG_stdin64, seed=0x3a44e83d
length= 256 megabytes (2^28 bytes), time= 4.7 seconds
 no anomalies in 159 test result(s)

rng=RNG_stdin64, seed=0x3a44e83d
length= 512 megabytes (2^29 bytes), time= 9.5 seconds
 Test Name                         Raw       Processed     Evaluation
 [Low16/64]BRank(12):1536(1)       R=+583.3  p~=  1.2e-176   FAIL !!!!!!    
 ...and 168 test result(s) without anomalies

It's not just 57, it's any number where the low-order byte is 57. As just one example, suppose the prime 32569 feels like a nice number to multiply by and you choose to multiply by that:

unix% ./xoshiro256ss32569 | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x9d9da8ee
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0x9d9da8ee
length= 128 megabytes (2^27 bytes), time= 2.1 seconds
  no anomalies in 148 test result(s)

rng=RNG_stdin64, seed=0x9d9da8ee
length= 256 megabytes (2^28 bytes), time= 4.7 seconds
  no anomalies in 159 test result(s)

rng=RNG_stdin64, seed=0x9d9da8ee
length= 512 megabytes (2^29 bytes), time= 9.4 seconds
  no anomalies in 169 test result(s)

rng=RNG_stdin64, seed=0x9d9da8ee
length= 1 gigabyte (2^30 bytes), time= 18.3 seconds
  no anomalies in 180 test result(s)

rng=RNG_stdin64, seed=0x9d9da8ee
length= 2 gigabytes (2^31 bytes), time= 35.1 seconds
  no anomalies in 191 test result(s)

rng=RNG_stdin64, seed=0x9d9da8ee
length= 4 gigabytes (2^32 bytes), time= 67.2 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low16/64]BRank(12):3K(1)         R= +2650  p~=  9.8e-799   FAIL !!!!!!!   
  ...and 200 test result(s) without anomalies

There are over 72,000 trillion 64-bit integers that it's bad to multiply by.

Does this seem like a rock-solid PRNG to you?


I was excited to learn that after two years of effort, Blackman and Vigna had a new PRNG. I really did want it to be good—the more good ones out there the better (and I happily celebrate good alternatives to PCG), but having looked at this work very briefly, I'm a bit disappointed because nothing I'm saying here in this critique is really new. Trivially invertible output functions aren't a good thing.

That said, most people who choose xoshiro256** are unlikely to be aware of any serious problems arising from using it. But as to the claim that xoshiro256** is an “all-purpose, rock-solid generator”, no, it's not all-purpose and it's not rock-solid.


Lest I be accused of hypocrisy, I should point out that the issue with having an invertible permutation function also affects the PCG generators officially labelled pcgXX_once_insecure. The PCG paper (from 2014) notes this, saying:

In a cruel twist of fate, we will give it the rottenest job, generating 32 bits of randomness from 32 bits of state. It’s cruel because the generator has no choice but to perform its permutation in an invertible way (because the number of output bits and the number of state bits are the same), and so all of its statistical goodness can be undone by anyone who knows its permutation function, unmasking the lowly LCG it has inside (but given the intricateness of the permutation, that is unlikely to happen by accident). […] Notwithstanding its speed and compactness, all but the most space-constrained applications should prefer a more secure generator, unless the “every number appears only once” property is especially useful.

In fact, the every-number-appears-only once property should also cause the _once_insecure generators to fail statistical tests that look for missing repeats. In a future blog post, I'll discuss how to write an efficient test for missing repeats in a 64-bit PRNG (even though you can usually tell that the issue would occur from just looking at the code).

Thus the concerns I expressed here are entirely consistent with concerns I expressed about specialized PCG variants in 2014.