Lair Of The Multimedia Guru

2024-01-24

Breaking pcg-dxsm (no implementation)

All PCG implementations seem to allow more or less easy computation of the seed, but a new PCG implementation has appeared in 2019 or so.
PCG-DXSM, the source code tells us “This is a new, more powerful output permutation” and “This latter aspect means that the scrambling applied to the high bits depends on the low bits, and makes it (to my eye) impractical to back out the permutation without having the low-order bits.”
Ok. lets try
Heres for reference, what this is about:
multiplier is a odd 64bit constant, SHR1 is half the state bits, SHR2 is quarter the state bits and SHR3 is 3 eights of the state so 64, 32, 48 for the 128/64 bit variant and 32, 16, 24 for the 64/32bit one. inc is forced to be odd too.

    state = state * multiplier + inc;

    l1 = state | 1;
    h1 = state >> SHR1;
    h2 = h1 ^ (h1 >> SHR2);
    h3 = h2 * multiplier;
    h4 = h3 ^ (h3 >> SHR3);
    return h4 * l1;

l1 is forced to be odd as we can see, so what do we know if pcg_dxsm returns 0 ? When is X * (2Y+1) = 0 ? Yes when X is 0 so h4 has to be 0 (yes i jump over some details of rings) and what can h3 be ? only 0, and h2 ? again only 0 and h1 ? yes its 0.
So when pcg_dxsm() return 0 you just learned half its internal state.
This can be extended a bit, for example when it returns a odd number h4 must be odd, when it returns a number that contains a factor of 2x then so must h4.

Can we compute the seed and increment from this ? I did not try, but i think so.
Just consider this: we decide how many bits we want to look for in the data and we brute force the rest. (there quite possibly could be an easier way, thats just the obvious one)
if we want 16bits to be from the data we would look for about 100k output data values, look for the values that are multiplies of 65536, these points would have h4 a multiple of 65536 and thus the low 17bits of h4 would be known. If we now brutefoce the 32-17 that is 15 low bits of the state and increment, these together fully determine, first all the low 15bits of all states and together with that the cases where we know the low 17 bits of h4 we now can invert the multiply and find the rest of h4. For each known h4 its trivial to find the upper half of the state. And the rest is identical to finding the state and increment of a truncated LCG and after the upper bits are found the lower can be trivially found from the h4*l1.
As i have not implemented this it is very possible that i have missed something or made some mistake.

Btw i think PCG and other PRNGs are really great little math exercises. Some are also good PRNGs as long as one understands their limitations.

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 02:44

No Comments »

No comments yet.

RSS feed for comments on this post.

Leave a comment

Powered by WordPress