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?