It's a weird paper. It's quite long and takes an eternity to reach this simple point. It's also littered with "security concerns" which are confusing at best and misleading at worst; in reality, none of the generators it discusses are suitable for "sensitive applications", even in the corner-case scenario it discusses of needing permutations of all the b-bit integers, a problem we already have cryptographic tools to solve.
But I'll confess to not really understanding what all the fuss is about insecure generators.
Linear congruential generators (x = k1*x + k2, unsigned with truncation on overflow) have some strange properties, some of which the paper explores. If you repeatedly take three sequential values from one and treat them as 3D coordinates, the points line up in parallel planes. (There's an explanation of why in Knuth.) Something has to be done to destroy that order. The solution here is to XOR the upper and lower halves of the 128-bit state to get 64 bits, then circular shift that by the high 6 bits of the 128-bit input. This passes most of the classic tests for random number generators.
The paper is really two papers. The first paper is a thoughtful and careful explanation of how we should consider judging pseudorandomness, and how to measure various criteria, along with a survey of many popular ten-lines-or-less PRNGs which PCG competes with. I found it interesting.
> But I'll confess to not really understanding what all the fuss is about insecure generators.
Based on things she's said on her site and in comments on John D. Cook's blog, it's all about algorithmic complexity attacks on randomized algorithms.
In other words, if you're doing quicksort on external input with a random pivot, and someone knows the PRNG state, they can make a pathological input that'll trigger quadratic behavior.
I don't know how likely this is to happen, but I know there were similar attacks on hash tables a few years ago.
And we addressed it with actual cryptography: SipHash. Since cryptographic random number generators are generated with very similar primitives, why wouldn't SipHash be the answer to those problems as well?
But I'll confess to not really understanding what all the fuss is about insecure generators.