0

Given one or two sequential Math.random outputs generated with Internet Explorer's linear congruential generator, is it possible to find the seed used in the LCG and find subsequent outputs? Here is the code given on the repo:

const double kdbl2to27 = 134217728.0;
uint64 sn;
sn = (seed * 25214903917 + 11) & 0x0000FFFFFFFFFFFFull; 
double res = double((uint)(sn >> 21)); 

seed = (sn * 25214903917 + 11) & 0x0000FFFFFFFFFFFFull;

res += (double)((uint)(seed >> 21)) / kdbl2to27;
res /= kdbl2to27;

res is then returned as the Math.random value. I have tried working out the math on reversing the last two lines to get the seed to no avail. I think there's an intuitive bruteforce method I'm missing utilizing the fact that I have two outputs. If it's possible to do with one output that would be nice too.

thriller
  • 1
  • 1
  • I can't comment on that algorithm specifically, but the general _design goals_ of a [PRBS](https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence) are that you cannot determine the seed given even a relatively large number of outputs, generally by keeping a lot of the seed's value "hidden" (obviously, there may be PRBS methods that fail to meet that goal). In this instance, at a _**very**_ crude 1st-approximation, you can see that 21 bits of the seed are not used to calculate the next value (but these are used to calculate the next value of the seed). – TripeHound Jul 18 '19 at 09:48
  • 5
    Possible duplicate of [Cracking a linear congruential generator](https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator)? – Clockwork-Muse Jul 19 '19 at 17:39

1 Answers1

-1

I can suggest trying to put all of the known data and formulas through something like Microsoft Z3 or other SMT solver. However I can’t predict how long the search would take.

Andrew Morozko
  • 1,759
  • 7
  • 10