Melissa O'Neill

The information in the above post is a merger of like, 20 different sources of information.

Your standard cryptographic books from any undergraduate program will tell you about the basics of confusion / diffusion, but I don't think the concept is very difficult at all.

Invertibility is hugely important but not discussed very much. It seems like crypto-experts 'obviously' know about it so they just don't talk about it? Knuth and Bob Jenkins both talked about the importance of invertibility to random number generators. EDIT: Invertibility is the basis of bijective / 1-to-1 and onto permutation functions. To be fair, I think everyone discusses the concept but maybe with different words.

Here's Jenkin's discussion on (non-crypto) hash functions, including a few paragraphs on "invertibility" (or "funnels" as they put it): http://www.burtleburtle.net/bob/hash/doobs.html

The "pcg-random" generator also has a large discussion on invertibility. Honestly, one of the best writeups on the subject, and I felt like my IQ went up severely after reading the paper end-to-end: https://www.pcg-random.org/paper.html

--------

The study of the invertibility of (data XOR (rotate-right data) XOR (rotate-left data)) is covered in many blogposts. https://marc-b-reynolds.github.io/math/2017/10/13/XorRotate.html

The study of invertibility in general was covered by Lemire: https://lemire.me/blog/2016/08/09/how-many-reversible-integer-operations-do-you-know/

-----

So as you can see,…

Thanks! It appears that Wikipedia has led me astray. The article in the top-level comment states, "if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures."

Following through to the document Wikipedia cites, I'm unable to find the original source for that claim. I suppose I'll look again after I have my coffee.

Ah. Found it. From the PCG paper, "also of note, RanQ1[42] and XorShift* 64/32 are essentially the exact same generator,
yet the former fails the test suite and the latter passes. The difference is that the
former markets itself as a 64-bit generator and fails because its low-order bits are
weak, whereas the latter only returns the top 32 bits." The claim of zero Big Crush failures also appears in Figure 2. http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

I suppose the next question is if the claim is wrong or I screwed up the implementation.

"Awful" was maybe hyperbole; mea culpa. I should have said: it's not great compared to other options available today. It shouldn't be your first choice anywhere.

In short:

* It has a huge state (~2kB per instance); compare 128-bit LCG at 128 bits or even a cryptographic PRF like Chacha at 64 bytes. This is a factor of 128x larger overhead (or 32x bigger than Chacha!) and hurts, say, L1 cache of more important data, especially with multiple instances.

* It has mediocre statistical properties (fails TestU01 BigCrush, fails PractRand). (128-bit LCG passes both.)

* And it has mediocre performance. (In the PCG benchmark, pg. 35: ~2.17 ns/op vs 128/64 LCG at ~1.05 ns/op. In that diagram, labelled "MCG" — but MCGs are just a subset of LCGs.)

Ref: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

See also: https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages

Here's the site for the random number generator.[1] It's basically a simple linear congruential random number generator (well known, but not very good) fed into a mixer. The mixer is new.

Most of the analysis is about the LCG or the final output. The suggested mixer is just

output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122);

That's simple, and the insight in this paper is that something that simple helps a lot. I would have thought that you'd want a mixer where changing one bit of the input changes, on average, half the bits of the output. The mixer above won't do that. DES as a mixer would probably be better, but it's slower. The new result here is that something this simple passes many statistical tests.

This isn't crypto-grade; both that mixer and a LCG generator are reversible with enough work.

[1] http://www.pcg-random.org/

I'm not sure which PRNG is used here, but some PRNGs have regularities in the lower bits.

This is e.g. the case for classical LCGs and the xoroshiro*+ family of PRNGs:

> If, however, one has to generate only 64-bit floating-point numbers (by extracting the upper 53 bits) xoshiro256+ is a slightly (≈15%) faster generator with analogous statistical properties. For general usage, one has to consider that its lowest bits have low linear complexity and will fail linearity tests (https://prng.di.unimi.it/)

> When m = 2k there is a further problem. The period of the bth bit of an LCG (where bits are numbered from the right, starting at one) is 2b , thus although the period is 2k, only the high bits are good and the lower order bits exhibit a clear repeating pattern. (https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf)

> Using /dev/urandom is not a good thing. It's only needed to get secure random numbers (CSPRGs) very slowly.

https://gist.github.com/sarciszewski/f7bd4c0358a44321787b

http://3v4l.org/j330O

mt_rand() performs worse than CSPRNGs, funny enough

Using a strong PRF we can take a 128-bit seed and turn it into an endless stream of random numbers. If /dev/urandom drains entropy, that's a bug that your OS should fix.

> Everybody should know by now that the first bits are good, and the last bits horrible. That's why you should not use modulo %, but rshift or better use Melissa E. O'Neill's PCG, which uses the first good bits to improve the latter worse bits. http://www.pcg-random.org/

Yeah, there is no pgc_random() function in PHP though.