Attacks on LCG with "self-XOR" output function?

Question

Consider an ordinary LCG modulo $2^n$ with an internal state of $n$ bits and an output of $n/2$ bits, with the twist that instead of simply truncating the state to produce an output, we take the upper and lower $n/2$ bits of the state and XOR them together.

$$X_{i + 1} = A X_i + C \bmod{2^n}$$ $$Y_i = (X_i / 2^{n/2}) \oplus (X_i \bmod 2^{n/2})$$

Has this kind of pseudorandom number generator been analyzed in a paper somewhere? What are the core ideas to attacking it when $n$ is large (e.g. 64 or 128 bits or larger)? I am particularly interested in an output prediction or state recovery break, but a distinguisher is nice to have too. We may assume both LCG parameters (multiplier and increment) are known and odd.

It seems that the usual methods (e.g. lattice) fail to apply in this case due to the added state-dependent, nonlinear operation.

---

I made an attempt at approaching this as follows:

We're trying to recover the initial state $X_0$. We may collect a number of outputs $\{ Y_i \}$ and take a guess at the LSB of $X_0$. This immediately fixes the LSB of all other $X_i$ since $X_{i + 1} \equiv X_i + 1 \pmod{2}$, and thus fixes the LSB of the upper half of all $X_i$ by definition of the output function.

Some arithmetic shows that for all $i \geq 0$ we have

$$X_i \equiv A^i X_0 + C \sum_{k = 0}^{i - 1} A^k \equiv A^i X_0 + C_i \pmod{2^n}$$

We can now ignore every bit beyond the LSB of the upper half (T-function property) and focus on the first $n/2 + 1$ bits. If we find that there does not exist an assignment of the remaining $n/2 - 1$ bits of $X_0$ such that, for all $Y_i$ collected, $$\mathrm{MSB}[\left ( A^i X_0 + C_i \right ) \bmod{2^{n/2 + 1}}] = \mathrm{LSB} \left [ Y_i \right ] \oplus \left ( \left ( X_0 + i \right ) \bmod{2} \right ) \tag{1}$$ then we have certainly guessed incorrectly. There's probably a better way to do this but we could just check satisfiability twice, once using our guess and once with the alternative guess, adding more $Y_i$ until either system becomes unsatisfiable, and thus recover two bits of $X_0$. Rinse and repeat on the next least significant bit until all bits of $X_0$ are recovered, in principle.

Checking for satisfiability exhaustively takes $O(2^{n/2})$ time, so if we need $m$ outputs at most recovering the state through this method in the most naive way takes time $$O((n/2) \cdot 2^{n/2} \cdot m)$$ which is much faster than brute-forcing the internal state (assuming $m$ is reasonable; I have no proof of this but I suspect that $m$ is proportional to or at least polynomial in $n$). It should be (barely) viable for $n = 64$, whereas the $n = 128$ case remains hopelessly out of reach.

Using an SMT solver as part of the algorithm (I tried Z3 and boolector) doesn't really give any speedups and is in fact slower than an exhaustive search. This makes sense intuitively because the multiplication by the different $A^i$ is highly nonlinear over bitvectors so the solver just gets bogged down expanding and processing an ever-growing, exponential number of clauses.

Can we do better? What are some ideas that could be applied here?

Answer 1

To answer my own question, after some research and experimentation I came up with a fast algorithm to break such constructions (in fact the approach below works even if the increment $C$ is unknown).

1. As a preprocessing step, find a set of $m$ small weights $\lvert w_i \rvert < W$ such that

$$\sum_{i = 1}^{m} w_i A^i \equiv 0 \pmod{2^{n/2 + k}} \tag{1}$$

where $k$ is some small integer defined later. Such a set of weights can be found rather efficiently (and in polynomial time in general) through lattice basis reduction, e.g. running LLL on the following lattice basis:

$$ \begin{bmatrix} K A & K A^2 & \dots & K A^m & K \cdot 2^{n/2 + k} \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & 0 \\ 0 & 0 & \dots & 1 & 0 \end{bmatrix} $$

for sufficiently large $K$, as shown by Lagarias and Odlyzko. In practice we expect such weights to exist when

$$m \log_2(W) \approx n/2 + k$$

2. Guess the lower $k$ bits of $X_0$, and use the LCG property to derive the lower $k$ bits of all $X_i$.

3. Use the $Y_i$ to obtain the lower $k$ bits of the upper half of all $X_i$. Denote $X^*_i$ as $X_i$ masked to only include those guessed upper bits, that is, $X^*_i = 2^{n/2} \times \mathrm{guess}$.

4. If we do some basic algebra we can notice that the congruence below follows from (1)

$$ \sum_{i = 1}^{m} w_i \left [ X_{i + 1} - X_i \right ] \equiv 0 \pmod{2^{n/2 + k}} \tag{2} $$

5. Since the $w_i$ are bounded by $W$ and we know the most significant bits of the variables involved, we can approximate this sum using our $X^*_i$. In fact we can evaluate it to within $\pm 2 m W \cdot 2^{n/2}$. Compute:

$$ Z = \sum_{i = 1}^{m} w_i \left [ X^*_{i + 1} - X^*_i \right ] \bmod{2^{n/2 + k}} $$

and let $\Delta$ be the difference between $Z$ and either 0 or $2^{n/2 + k}$, whichever is closest to $Z$.

6. If $\Delta \geq 2mW \cdot 2^{n/2}$, our guess to the lower bits of $X_0$ is certainly incorrect. Otherwise, it is correct with probability $1 - 2mW \cdot 2^{-k}$ (this makes some assumptions about the distribution of the $Y_i$, but works in practice).

7. Try all $2^k$ guesses against different windows of outputs $Y_i$ (adjusting accordingly, note that the relation (1) still holds even if you shift all exponents by a fixed constant) until all but one fail to pass the test in step 6. The final candidate guess will be the lower bits of $X_0$.

8. Repeat all steps, guessing successively higher bits of $X_0$ until the entire internal state is recovered.

This turns out to be very fast as $k$ can be set to be not too much larger than $\log_2{mW}$, for the probability of a false positive in step 6 to be sufficiently small, e.g. 0.5; if $k$ is too small then we extract no information.

Given the above, we should try to force $W$ to be as small as possible in step 1 to minimize the number of bits $k$ to guess, so that, for example, $W \approx 2$, $m \approx n/2 + k$ so $k \approx \log_2(n)$ showing that this attack should scale very well with $n$.

I've implemented this and it works well and successfully recovers the internal state as expected for $n = 128$.

Also it's possible to extend this to unknown increment $C$, the only thing that changes is we need to guess the lower bits of $C$ at the same time as the lower bits of $X_0$ to be able to perform step 2, and everything else stays the same; we recover $C$ and $X_0$ simultaneously through the same process.

---

References

This approach was adapted from techniques described in "Lattice Reduction: a Toolbox for the Cryptanalyst". This paper contains even more sophisticated techniques for attacking similar kinds of problems and is fairly readable.