# Predicting PRNG given some of its previous output

I a have a question about PRNGs and this is my very first experience with them. I have the following generator that takes a 56-bit seed 'p' during initialization and then chooses both X and Y randomly from the interval [0, p].

Every time it is called, it returns the output of the next function:

def next(self):
self.x = (2*self.x + 5) % self.p
self.y = (3*self.y + 7) % self.p
return (self.x ^ self.y)


I have the first 9 outputs of the generator and i need to predict the next output.

prng_output = [210205973, 22795300, 58776750, 121262470, \
264731963, 140842553, 242590528, 195244728, 86752752]


I have thought of the solution which turned out to be correct by VERY slow, so apparently there must be another way to solve it.

My solution was to constrain the range of values for p according to the given output. Also, generate all values for X and for every value of X, calculate the first 9 values according to the previous equation and XOR it with the output to get Y. Finally, check of the sequence of Ys is valid or not (also according to the previous equation).

After some reading i knew that a reduced state (reduce the number of bits) of the generator can be determined.

So my question is how to crack the given generator ? and what is the 'reduced state' of the generator and how to use it ?

So if someone can help me with some details or a 'useful' link to read to understand more, i would be thankful.

Thanks,

-
 Terminology nitpick: your $p$ is not a "seed", it's a parameter of the generator. Usually one would call it a "modulus", since that's how it's used in your algorithm. – Ilmari Karonen Apr 6 '12 at 14:51 Thanks, for the correction. – Samer Meggaly Apr 6 '12 at 22:10 The question is less than accurate: it turns out that p is 57-bit, not 56-bit (although that's not apparent from the known output, which happens to remain within 56 bits until the 28th output). Also, if the first self.x and self.y are chosen randomly in [0..p] rather than [0..p-1], that's an irregularity. – fgrieu Apr 7 '12 at 6:32 No, this is a mistake of mine, x and y and chosen randomly in [0..p-1] and the problem stated that p is 56-bits. – Samer Meggaly Apr 7 '12 at 6:43

I'm not familiar with the terminology "reduced state", so I can't address that half of the question.

However, this particular PRNG makes it easy to reconstruct the internal state; we note that the state function can be rewritten as:

x := 2*x + 5 - kx * p
y := 3*y + 7 - ky * p


for some small integers $k_x$, $k_x$ (in fact, $0 \le k_x \le 2$ and $0 \le k_y \le 3$. Once we do that rewrite, we notice that the lower bits no longer depend on the higher bits.

So, what we can do is:

• Iterate over the possible $k_x$, $k_y$ values used to generate the second, third and fourth outputs; a total of 1728 possibilities.
• For each set, we go through the possibilities for bit 0 of p and the initial x (note: because the initial y can be immediately deduced from the x and the first output, we don't have to iterate through that)
• Check to see if there's a combination that gives the bit 0's on the second, third and fourth outputs that we have; if there is, then start looking through the various possibilities for bit 1 of p and initial x.

When we manage to get through all 29 bits, and get all the bits of the output we observed, then we have the answer (and in fact, continuing the generate outputs will, in this case, continue to generate the listed outputs).

Going through the above procedure gives us the answers p = 295075153, x0 = 89059908, y0 = 164204369, next output = 231886864

-
 nice, Poncho's solution beats my explicit one, and convince me that the SAT solver would crunch the problem. – fgrieu Apr 6 '12 at 20:14 First, thanks a lot for the help. Second, i still have some points that i cant understand ... how did u determine the ranges for Kx and Ky ? ... Also, i don know whether i got the second step or not, so u mean that for all values of X [0, 2^56] and for all values of bit-0 of p {0, 1}, find 3 pairs of (Kx, Ky) that will generate the 2nd, 3rd and 4th outputs. – Samer Meggaly Apr 6 '12 at 22:01 @SamerMeggaly: well, because $0 \le x_0 < p$, then we know that $0 \le 2*x_0 + 5 < 3p$, and so doing the $\bmod$ reduction will cut out between 0 and 2 multiples of p (and similarly on the y side). As for step two, we start by iterating through the various possibilities of bit 0 of p and bit 0 of $x_0$, and once we've determined settings that works, we start on bit 1 of both, and work our ways up until we've recovered the entire value (or decided that the particular $k_x, k_y$ values weren't the right ones) – poncho Apr 6 '12 at 22:17

The generator can be re-stated as having a key $(p,x_0,y_0)$, the recurrences $x_{j+1}=(2\cdot x_j+5)\bmod p$ and $y_{j+1}=(3\cdot y_j+7)\bmod p$, and the output $r_j=x_j\oplus y_j$ known for $j\in\{1\dots 9\}$.

We define $(u_j,v_j)$ such that $x_{j+1}=2\cdot x_j+5-u_j\cdot p$ and $y_{j+1}=3\cdot y_j+7-v_j\cdot p$. Notice that $(u_j,v_j)$ can take only 12 values. At the beginning or the sequence, or if $p$ was chosen such that the Linear Congruential Generators $x$ and $y$ are maximal-length, $(u_j,v_j)=(0,0)$ has odds only slightly lower than $1/6$. It is reasonable to hope that $(u_j,v_j)=(0,0)$ occurs for some $j\in\{1\dots 8\}$. If so, we know both $x_j\oplus y_j$ and $(2⋅x_j+5)\oplus (3\cdot y_j+7)$, as these are $r_j$ and $r_{j+1}$. There can be at most one solution $(x_j,y_j)$ for that, and it can be found simply by determining bits of $y_j$ from right to left. Some of these solutions can be eliminated, for they lead to $x_j$ or $y_j$ too big for $(u_j,v_j)=(0,0)$ to hold.

Then, for many values of $(u_{j+1},v_{j+1})$, there will be few possible values of $p$ compatible with $(x_j, y_j, r_{j+2})$, which are known unless $j=8$. and these candidates for $p$ can be found reasonably efficiently, again by finding bits from right to left. The rest is pesky details. Among these, the given that $p$ is 56-bit turns out to be wrong.

Another option is to encode the problem in the formalism of boolean satisfiability, and throw that to some SAT solver, like theses ones. This will work fine even if we have only 4 consecutive output values, none of which with $(u_j,v_j)=(0,0)$.

-
 Thanks @fgrieu, i have two points that i tried to figure out, but i couldn't. First, how did u limit the range of p to [2^55, 2^56] ... Second, also the same for Xj and Yj. – Samer Meggaly Apr 6 '12 at 22:09 @SamerMeggaly: By definition of the remainder, what is the range for $(2\cdot x_j+5)\bmod p$? Assuming $p$ known, what's the range for $x_j$ when $j>0$?. Same for $y_j$. What's the highest known $r_j$? Consider the high bit of that: how was it formed? What does that tell us on the minimum value of $x_j$ or $y_j$? What does that tell us on the minimum value of $p$? Does the problem statement give us a maximum value for $p$? If it did not, could we make a plausible conjecture, and at what odds? – fgrieu Apr 7 '12 at 5:53 I know that the range for (2x + 5) mod p is [0..p-1], but wouldn't that make x < (p-5)/2 that is (2^56-5)/2 ? and the maximum value for p will be (2^56-1), please correct me if i am getting anything wrong. – Samer Meggaly Apr 7 '12 at 6:46 We know $x_j2^{57}$, and we can confidently assume $p\le 2^{57}$. Thus $u_j=0\Rightarrow 2⋅x_j+5<2^{57}\Rightarrow x_j\in[0\dots 2^{56}-3]$; similarly $v_j=0\Rightarrow y_j\in[0\dots(2^{57}-8)/3]$. – fgrieu Apr 7 '12 at 8:24