Predicting PRNG given some of its previous output

Question

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 $Y$s is valid or not (also according to the previous equation).

After some reading I learned 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, what is the "reduced state" of the generator, and how can I use that "reduced state"?

Answer 1

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

Answer 2

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 then use a SAT solver. SAT solvers are available from the following links: MiniSAT, CryptoMiniSat 2 or the SAT competition. This scheme will work fine even if we have only 4 consecutive output values, none of which with $(u_j,v_j)=(0,0)$.

Answer 3

The two seeds add up to 56 bits but the fact that the random number is generated by xor'ing constrains the problem to 28 bits. With my machine running all 28 bit numbers xor the generating number gives every possible x and y in about 90 seconds. In python:

    P, out1, out2 = 295075153, 210205973, 22795300
    def search():
        for i in range(P):
            if ((2*i+5)%P) ^ ((3*(i ^ out1)+7)%P)  == out2:
                print('\nFound it! x =', i, ' y =',(i^out1))
                print()
                x = i
                y = (i^out1)
                print('output #1:',x ^ y)
                for j in range(2,11):
                    x = (2*x + 5) % P
                    y = (3*y + 7) % P
                    print ("output #%d: %d" % (j, x^y))          
                return
    search()

Answer 4

In these times of ecological awareness, I'll sketch a pain and paper ™ solution which does not require brute force nor power supply :-D On top of that, the complexity of this solution is linear in the seed size, not exponential as that of brute force solutions.

Let me denote by $[v]_i$ the $i$-th lower bit of $v$ and the internal state at iteration $n$ by $(x_n,y_n)$. We observe that $$ x_{n+1} \oplus y_{n+1} = (2x_n+5 \mod p) \oplus (2y_n+5+y_n+2 \mod p) $$

Unfortunately for the cryptanalyst (but then a nice tool for designers: see e.g. ARX designs such as Salsa20 and the analysis of Snow 2) the mixture of $+$ and $\oplus$ does not commute so that one can forget about directly equating $x_{n+1} \oplus y_{n+1}$ to $2(x_n\oplus y_n)+y_n+2 \mod p$ as she might dream to be able to do.

However, assuming no folding due to $p$ took place, which happens with very high probability, the display equation above gives: $$ [x_{n+1}\oplus y_{n+1}]_0 = [y_n]_0 $$ which yields the lowest bit of $y_n$ and hence that of $x_n$ since we know $x_n\oplus y_n$; then: $$ [x_{n+1}\oplus y_{n+1}]_1 = [x_n]_0 \oplus [y_n]_1 \oplus 1 $$ which now directly yields $[y_n]_1$ and hence $[x_n]_1$ since we know $x_n\oplus y_n$; then: $$ [x_{n+1}\oplus y_{n+1}]_2 = [x_n]_1 \oplus [y_n]_2 \oplus [y_n]_0 \oplus [y_n]_0 [y_n]_1 $$ which now directly yields $[y_n]_2$ and thus $[x_n]_2$, etc.

Taking account of the carries and proceeding bottom-up allows to recover the internal state solving only linear equations in a single unknown over $\text{GF}(2)$ at each stage.