7
$\begingroup$

Given the outputs of the pseudorandom numbers generator how can one determine the type (e.g. Linear Feedback Shift Register), Multiply-With-Carry, Linear Congruential Generator etc.) and recover the function and the seed?

The given array of numbers is for sure generated by PRNG (not Cryptographically Secure) - this is known in advance. The outputs are clean, the PRNG is a black box returning consecutive numbers (no modified, no skipped values. Now the task is to find the function and seed from the values.

The simple idea is try all schemes until match is found, but I am interested in more algorithmic approach.

$\endgroup$
10
$\begingroup$

There's no single method to determine the type of the PRNG. Indeed, for a cryptographic-strength PRNG you can't distinguish its output from truly random, so you can't determine the type of such PRNGs solely by looking at their output.

Instead, for each of the schemes that you list, there is a way to recover the seed and predict future bits from its output. The way to do that is different for each type of PRNG. So, the natural approach is: for each candidate type, try the method for recovering the seed that works for that type of PRNG, and see if you're successful. If you are, you've figured out the type of PRNG.

I don't think there's a more efficient or general technique. And, frankly, I don't think a more efficient one is needed. For the types you list, there are very efficient algorithms for cryptanalyzing them, given enough output. So, I suspect it's going to be hard to beat the "try all schemes" approach.

This works if your set of PRNG types contains only PRNGs that are cryptographically weak, i.e., where it is possible to predict future outputs given enough past outputs.

For details of how to do this for any specific type of PRNG, I suggest you ask a separate question focused on that one type of PRNG. Here are some resources on some of the PRNG types you listed:

$\endgroup$
  • 1
    $\begingroup$ You could add a blurb about LCGs' output being highly organized in hyperplanes when plotted. Plots like this can be used to identify that one is dealing with LCGs and other types. $\endgroup$ – Iwillnotexist Idonotexist Jan 21 '17 at 1:54
  • 2
    $\begingroup$ @IwillnotexistIdonotexist, those plots are actually less effective than the method I link to, so I see no reason to use them if your goal is to identify use of a LCG: the plots require more outputs, and require someone to inspect the plot. The approach I link to requires only a handful of outputs and very little computation. $\endgroup$ – D.W. Jan 21 '17 at 4:35
  • $\begingroup$ True; The math is solid and will identify very quickly whether one is dealing with a given family. But it's nice to have a less mathematical, more visual demonstration that PRNGs are not all created equal, and this is one of the shining examples. $\endgroup$ – Iwillnotexist Idonotexist Jan 21 '17 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.