Lair Of The Multimedia Guru


Finding the increment of PCG/LCG/truncated LCGs and some (for me) surprising consequences about their structure.

For plain LCG the problem is trivial and an implementation shown in my last post. PCG falls in 2 categories, the PCG-XSL-RR which is based on an LCG, this was solved in the Paper by Bouillaguet, Martinez and Sauvage.
The remaining PCG generators are different and simpler, they are based on an truncated LCG. The problem of finding an increment and seed is marginally harder as it is for the corresponding truncated LCG. It can be done using Lattice reduction (even some half bastardized version seems to work). The problem and the surprise for me really is that the solution in general is not unique. I guess it was a surprise after reading in the original PCG paper how additional random streams can be created by changing the increment. This is really not true. Changing the increment does not really produce “different” random data, it just offsets it.

Let me first show an example with a plain LCG (using the multiplier 6364136223846793005 from PCG with 64bit state)

Seed 314159 314160
Increment 1442695040888963407 13525302890751722019
Output0 1758213515780721042 1758213515780721043
Output1 8369501526408240633 8369501526408240634
Output2 14286244372924288276 14286244372924288277
Output3 12908628925188209107 12908628925188209108
Output4 17643264774698309734 17643264774698309735
Output5 10761879962653451581 10761879962653451582
Output6 11615400545074122760 11615400545074122761
Output7 5243018629741398711 5243018629741398712
Output8 1055069346400300154 1055069346400300155
Output9 14628082432468752577 14628082432468752578

This is not a odd exception, no, for every choosen LCG and choosen offset (here it is +1) theres a seed and increment that will produce a offset sequence of random numbers.
You can use lcg-breach to find them by just asking it to find parameters for a modified sequence.
Now thats LCGs, What about truncated LCGs ? its worse because they discard the low bits. You get sequences that can be exactly equal for MANY values even with different increment and seed. And that is what the problem is in determining the increment for truncated LCGs and the corresponding PCGs. For PCG-XSL-RR the low LCG bits are XORed in so there remains a effect on the output and its possible to determine the increment but for 128/64 and 64/32 PCG-XSH-RR the low bits of the state do not affect the output as long as their effect stays limited to these low 27bit (for 64/32 bit) in future states they cannot be computed from the output. Or in other words the output from 2 PCG-XSH-RR with differing increments can be identical for a long time.

On top of that, there is also a set of seed,increment pairs that produce constant output.
consider this:

LCG         : out[i+1] = out[i] * m + a mod n
what we want: C        = C      * m + a mod n

just solve it:

C - C * m = a mod n

choose the constant C you want and this will tell you the increment a that will keep the generator at that constant when its started on it.

and how do we now create a offseted LCG ?
simply add it with the constant above

out[i+1]     =  out[i]      * m + A     mod n
           C =           C  * m +     a mod n
out[i+1] + C = (out[i] + C) * m + A + a mod n

And yes LCGs of the same multipler and modulo seem to form an abelian group with addition.

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 18:06

Powered by WordPress