How Brittle Are LCG-Cracking Techniques?

Question

There are published techniques for cracking LCGs, but to my eye those techniques seem very brittle — very minor changes can add nonlinearity that renders techniques like the LLL algorithm unusable. Or, am I mistaken, are these variations still easy to crack?

Background

One thing that perplexes me somewhat about the cryptographic community is how people seem to hate LCGs and write them off without much effort to repair their flaws, and yet also like LFSRs and have repaired them often.

Raw LCGs and LFSRs Are Both Weak

In Schneier's Applied Crypography (1996), he writes damningly about LCGs:

Unfortunately, linear congruential generators cannot be used for cryptography; they are predictable. Linear congruential generators were first broken by Jim Reeds (1977, 1979a, 1979b) and then by Joan Boyar (1982). [...]

Other researchers extended Boyar’s work to break any polynomial congruential generator (Lagarias & Reeds 1988, Krawczyk 1989, Krawczyk 1992). Truncated linear congruential generators were also broken (Frieze et al 1984, Hastad & Shamir 1985, Frieze et al 1988), as were truncated linear congruential generators with unknown parameters (Stern 1987, Boyar 1989). The preponderance of evidence is that congruential generators aren’t useful for cryptography.

In contrast, the book sends mixed messages about LFSRs, saying positive things like:

Because of the simple feedback sequence, a large body of mathematical theory can be applied to analyzing LFSRs. Cryptographers like to analyze sequences to convince themselves that they are random enough to be secure. LFSRs are the most common type of shift registers used in cryptography.

but also saying:

On the other hand, an astonishingly large number of seemingly complex shift-register-based generators have been cracked. And certainly military cryptanalysis institutions such as the NSA have cracked a lot more. Sometimes it’s amazing to see the simple ones proposed again and again.

More recently, Schindler 2009 concurs with this latter advice, saying:

Consequently, LFSRs do not fulfill requirement R2 [lack of predictability], and they are absolutely inappropriate for sensitive cryptographic applications.

More Secure Variations…?

Much of the rest of the RNG chapter of Applied Crypography, focuses on LFSR variants that combine LFSRs in complex non-linear ways to make them more challenging to crack.

But in what seems to me like a strange contrast, it is completely dismissive of attempts to improve LCGs, saying:

Various people examined the combination of linear congruential generators (Wichmann & Hill 1982, L’Ecuyer 1988). The results are no more cryptographically secure, but the combinations have longer periods and perform better in some randomness tests.

A source of surprise to me here is that unlike much of the rest of the book, the claims aren't supported by the citations. Neither paper cited mentions security or cryptography at all, so where is Schneier getting the claim that “results are no more cryptographically secure”?

It's interesting because Knuth 1985 made a quite different claim, saying:

Although we have seen that linear congruential sequences do not lead to secure encryptions by themselves, slight modifications would defeat the methods presented here. In particular, there appears to be no way to decipher the sequence of high-order bits generated by linear congruential sequences that have been shuffled [...]

Of course, these references are quite old, but most discussions I see seem to refer back to the 1980s and 1990s for their dismissal of LCGs.

How Brittle Are LCG-Cracking Techniques…?

So, this leads (finally) to my question. Just how brittle are these techniques for cracking LCGs? Are they really so fatally flawed that they can't be repaired?

Let's make it real with some example C code:

#include <stdio.h>
#include <stdint.h>

int main()
{
     uint32_t result;
     uint64_t state = SEED;
     for (int i=0; i < 32; ++i) {
         state = state * MULT + INC;
         result = state >> 32;
         result ^= XOR;
         printf("0x%08x, ", result);
     }
     printf("\n");
}

Case 0: Everything Known

Thus, if we set SEED=0x35e647cfd3423fd0ull, MULT=0xc278c0d1c04a88d9ull, and INC=0 XOR=0, the program produces

0x59502137, 0xb6152ece, 0xbbd2cb88, 0xef05249f, 0x3ec02cd5, 0x2b0eca82, 0x0a3120be, 0x5116f6fb, 0x8b06b68c, 0x01367995, 0xca5789bd, 0xa40f57ff, 0x5f6d75bb, 0x544951f7, 0x8f9e70c8, 0x74307957, 0x70aab16c, 0x0ec42e72, 0x9bb2a42d, 0x2c5aa6aa, 0xe3cff469, 0x37881c03, 0x8d7853ba, 0xd6beb049, 0xa9fc0e6e, 0xbbc5bd2b, 0x33462a03, 0xad508c7e, 0xe31313e9, 0xf30418ae, 0xbefc1b02, 0xc0134d22, 

Case 1: Trivial Case

Now SEED is unknown, MULT=0xc278c0d1c04a88d9ull INC=0 XOR=0, and the output is

0x8b1294a5, 0xae5cbf0d, 0x2da164bd, 0xcbe27c6d, 0x6d800d17, 0x8f576a33, 0x6ea4915b, 0x97ada3d5, 0x8ab31e5d, 0x0bb313d2, 0xfbee8ebf, 0xf1d09659, 0x5a54428e, 0x34d32f9a, 0xe800efdb, 0x5a313abd, 0x844a1328, 0xed9cf267, 0x5883910f, 0x7a44aa80, 0x0e34d575, 0x7e3453df, 0x2267bf41, 0x8c234c85, 0xa359f8b8, 0xf78f0126, 0x7902934e, 0x5ae97dc1, 0x1ba40108, 0x67f5ca64, 0x7aed8c5e, 0xceccf54b, 

The above should be trivial to break. Even brute force is practical since we only need to search 2^32 possible states.

Case 2: Known Techniques

Now SEED and INC are unknown, MULT=0xc278c0d1c04a88d9ull and XOR=0, and the output is

0x8c005b3e, 0x27e3338e, 0x1bb199bb, 0x46449299, 0x4b747cca, 0x290032ca, 0x2a6e907f, 0x6b1bd36f, 0xab7f4d33, 0x9b7a73be, 0xe9ae522c, 0x171e7e55, 0x95b0dcd2, 0xd93e6986, 0xddd1a6d2, 0xf2e197e5, 0x8e621adc, 0x0ac2dd7e, 0x31fafcce, 0xc7e19a1a, 0x5f9b0788, 0x9f3a790e, 0xe0e76b17, 0x6fcf2716, 0x0106a4fb, 0x3e64838a, 0x508cc169, 0x690a7b96, 0xde80a6cc, 0xbbcc6546, 0x76e80fe9, 0x6683486d, 

This should also be breakable, but we need to use techniques from the literature because a brute force approach is infeasible. I would love to see code that actually breaks this and works out what the next numbers will be.

Case 3: Added Nonlinearity (Harder?)

Now SEED, INC and XOR are unknown, MULT=0xc278c0d1c04a88d9ull, and the output is

0x5e3af925, 0x1b7f8e1a, 0x268c64d1, 0x4b614b92, 0xba6c7a4d, 0xe4103860, 0xfe373528, 0x768f9a04, 0xedab3415, 0x2605ff3f, 0xb01e70bb, 0xff65e40a, 0x50980bee, 0xe9fb0d78, 0xdf3754bd, 0x46cce80d, 0xfe1395ac, 0x2e663615, 0xdebea707, 0x4d2cd17d, 0x30f0c21c, 0xb15a64ee, 0x21d38d72, 0xbb8e8c6d, 0x114447d1, 0x5362837c, 0xed46a733, 0x37526997, 0xf7ac14c2, 0xc33e7134, 0x96a9d739, 0x3ee606ba

So, this is the crux of my question. How much harder is this variation than the previous one? From my reading of the standard techniques for breaking truncated LCGs, this added nonlinearity is a problem. We can cancel-out the XOR but that breaks the subtraction we were already doing to cancel-out the increment; we can cancel one or the other, but not both.

(If it's still easy, what are my constants? Want to share actual code that breaks it?)

Case 4: Any Harder?

So, now SEED, INC, XOR and MULT are all unknown, and the output is

0xc325ad70, 0x5ac2c779, 0xafa3561b, 0xa39f9107, 0x256264b5, 0x8d07c2e8, 0x55d53f9e, 0xb090eacc, 0x8b5a28a9, 0xa5e2a296, 0xc0650347, 0x0718efdb, 0x66c331c5, 0xd00236cf, 0x22118dc5, 0x4f9d67d0, 0xa6793bfe, 0x00ad774d, 0xd8337c8f, 0x49aab5b3, 0x96e419c8, 0xd6a9385b, 0x47108063, 0xde06326f, 0x2d4cd28c, 0xb0f97be8, 0x494f5df1, 0x8d53de30, 0x0eee9cbc, 0x9ea6beb1, 0xbefa03b6, 0x5a3d1fea, 

How hard is this to break? (If it's still easy, what are my constants? Want to share actual code that breaks it?)

Previous StackExchange Questions

I'm aware of previous discussion here, here, and here, but none of these answers match this question, they address the question of how weak a particular kind of LCG is (often starting with an easily broken example), rather than the brittleness of the techniques used.

Update: Question Clarified

(Some users wanted to close my original question as “Too broad”, so I clarified it, resolving the issue.)

So, to be clear, my question is:

I know that Case 1 is easy, and Case 2 has published techniques for solving it. But, my questions are:

• Are there any efficient known techniques for cracking Case 3 or 4? If so, what are they?
• Is there any implementation code out there for cracking Case 2.

I hope that this is straightforward enough to be answerable, or for people to say “I've done lots of work in cryptography and I don't know of an answer”.

Answer 1

This answer addresses Cases 1 and 2 from the question to provide a baseline, leaving Case 3 (which is the one I'm most interested in), unresolved.

Case 1, Zero Increment

In this case we'll consider a simple Lehmer-style LCG (a.k.a. an MCG), with a seed $s_1$, multiplier $a$ and $b$ bits of state and $r$ bits returned. The modulus $M = 2^b$, and the internal states are $s_1, a s_1, a^2 s_1, a^3 s_1, a^4 s_1, \ldots \mod M$. The output values are produced by integer division by $m = 2^{b-r}$.

If we say that the known high-order bits are $h_1, h_2, h_3, h_4, \ldots$ and the unknown low-order bits are $l_1, l_2, l_3, l_4, \ldots$, we can thus say:

$$ \begin{eqnarray*} s_1 & = & h_1 m+l_1 \mod M\\ a s_1 & = & h_2 m+l_2 \mod M\\ a^2 s_1 & = & h_3 m+l_3 \mod M\\ & \vdots & \end{eqnarray*} $$

In the given example, $a = 14013162247670106329$, $b = 64$, $r = 32$, $M = 2^{64}$, $m = 2^{32}$.

LLL Formulation

In the LLL formulation, we'll take the equations

$$ \begin{eqnarray*} M s_1 & = & 0 \mod M\\ a s_1 - s_2 & = & 0 \mod M\\ a^2 s_1 - s_3 & = & 0 \mod M \end{eqnarray*} $$

and represent them as the lattice $L$ where each row $L_i . (s_1, s_2, s_3) = 0$.

$$ L = \left( \begin{array}{ccc} M & 0 & 0 \\ a & -1 & 0 \\ a^2 \bmod M & 0 & -1 \end{array} \right) $$

In the example, this becomes

$$ \left( \begin{array}{ccc} 18446744073709551616 & 0 & 0 \\ 14013162247670106329 & -1 & 0 \\ 9716750713725077489 & 0 & -1 \\ \end{array} \right) $$

If we apply lattice reduction (e.g., LatticeReduce in Mathematica), we get:

$$ \left( \begin{array}{ccc} 238170 & 2443922 & 662052 \\ -2629560 & 974809 & -465865 \\ 341923 & -550461 & 2727218 \\ \end{array} \right) $$

This tells us that

$$ \begin{eqnarray*} 238170 s_1 + 2443922 s_2 + 662052 s_3 & = & 0 \mod M \\ -2629560 s_1 + 974809 s_2 + -465865 s_3 & = & 0 \mod M \\ 341923 s_1 + -550461 s_2 + 2727218 s_3 & = & 0 \mod M \end{eqnarray*} $$

In some sense this is “better” because it's nicer system of linear equations, but for actually solving the problem at hand, I didn't find it useful because my equation solver (Mathematica) doesn't struggle to solve the equations even when we don't use lattice reduction.

Direct Solution

Given our equations, we can just write, in Mathematica,

SolveMCG[a_, b_, r_, h1_, h2_, h3_] := 
 With[{M = 2^b, m = 2^(b - r)}, 
  Solve[{    s == l1 + h1 m,
           a s == l2 + h2 m + k2 M, 
         a^2 s == l3 + h3 m + k3 M,
         l1 >= 0, l1 < m,
         l2 >= 0, l2 < m, 
         l3 >= 0, l3 < m},
        Integers]]

And then run

SolveMCG[14013162247670106329, 64, 32,
         2333250725, 2925313805, 765551805]

Producing the following result (in about one hundredth of a second):

{{k2 -> 7612682177356138107, 
  k3 -> 106677750491238099311986697652283092078,
  l1 -> 3882613991, l2 -> 3819575247, l3 -> 2041194103,
   s -> 10021235561125903591}}

Here it's correctly inferred the low order bits and the initial seed, and we've done so using only three 32-bit outputs.

Actually, three outputs was arguably overkill. We can actually pretty-much solve it using only two outputs! Given the similar definition:

SolveMCG[a_, b_, r_, h1_, h2_] := 
 With[{M = 2^b, m = 2^(b - r)}, 
  Solve[{  s == l1 + h1 m,
         a s == l2 + h2 m + k2 M, 
         l1 >= 0, l1 < m,
         l2 >= 0, l2 < m}, 
        Integers]]

Running

SolveMCG[14013162247670106329, 64, 32, 2333250725, 2925313805]

(which we can even solve with Wolfram Alpha), gives

{{k2 -> 7612682176901725222, l1 -> 3284430794, l2 -> 491393594, 
  s -> 10021235560527720394},
 {k2 -> 7612682177356138107, l1 -> 3882613991, l2 -> 3819575247,
  s -> 10021235561125903591}}

The only problem is that in this case we have two solutions to the system (the second one is the one we actually want).

Three outputs gives us a unique solution (in this case), and actually we still have a unique solution with three outputs even if we drop down to 24 bits.

It's interesting to look at what happens as we further reduce the number of output bits. For 16 bits of output from our 64-bit state, we need four outputs to find a unique solution. Similarly, 12-bit output needs six outputs, 10-bit output needs seven, 8-bit output needs eight (solving in 0.5 seconds), and 4-bit output needs sixteen (but requires a minute to solve!). These latter cases are interesting because some authors have claimed that LCGs can be secure if we only return $\log_2 b$ bits, but $\log_2 64 = 6$ and we can still easily solve the problem at that point.

But perhaps these claims do have some basis in reality—3-bit output needed twenty-two outputs (which isn't that many), but needed 76 minutes to solve, which leads me to guess that solving it for 2-bit output would take nearly two months, and (if my extrapolation is correct!), if we only take the high bit, it'd take Mathematica about half a billion years to solve. Ouch!

Case 2, Unknown Increment

The trick here is to observe that if $$ \begin{eqnarray*} s_2 & = & a s_1 + c \mod M\\ s_3 & = & a s_2 + c \mod M\\ s_4 & = & a s_3 + c \mod M\\ & \vdots & \end{eqnarray*} $$ then $$ \begin{eqnarray*} s_2 - s_1 & = & ((a - 1) s_1 + c) \mod M\\ s_3 - s_2 & = & a ((a - 1) s_1 + c) \mod M\\ s_4 - s_3 & = & a^2 ((a - 1) s_1 + c) \mod M\\ & \vdots & \end{eqnarray*} $$ In other words, if we take the differences between successive values, we'll have a Lehmur-style LCG again.

One wrinkle is that subtracting the truncated high-order bits may not produce the same result as subtracting the actual values and then truncating that (due to a missing borrow), so we have to search slightly. But that is easily done:

SolveLCG[a_, b_, r_, lh1_, lh2_, lh3_, lh4_] := 
    Flatten[Table[SolveMCG[a, b, r, h1, h2, h3],
                 {h1, Mod[{lh2 - lh1 - 1, lh2 - lh1}, 2^(b - r)]},
                 {h2, Mod[{lh3 - lh2 - 1, lh3 - lh2}, 2^(b - r)]},
                 {h3, Mod[{lh4 - lh3 - 1, lh4 - lh3}, 2^(b - r)]}], 3]

For our problem, running

SolveLCG[14013162247670106329, 64, 32,
         2348833598, 669201294, 464624059, 1178899097]

produces

{{k2 -> 8533036703073522045, k3 -> 5916822271048598914, 
  l1 -> 111392721, l2 -> 2094520361, l3 -> 3114664641, 
  s -> 11232778258835814353}}

This result doesn't completely solve the problem because it only calculates what low-order bits of the differences will be, without telling us the low order bits of the original seed. Nevertheless, it will let us very closely approximate the output of the RNG.

Notice, however, that our subtraction technique is defeated by the xor in Case 3.

Also, note that before I tried Mathematica, I attempted to use several ILP solvers (e.g., lp_solve, GLPK and Mathematica's LinearProgramming), instead and had far less success. ILP solvers work best at optimization where the number of feasible solutions is large. In this case, there is only one feasible solution, and LP doesn't help the solver find it, so the solvers didn't find the solution without help that amounted to telling them the answer. Alas, Mathematica's Solve function doesn't say how it found the solution.

Answer 2

This is a work-in-progress, mostly trying to address Case 3 in the question, since the problem of Case 2 is dealt with in another answer, and has been thoroughly researched:

• Jacques Stern: Secret linear congruential generators are not cryptographically secure, in proceedings of the 28th Annual Symposium on the Foundations of Computer Science, 1987 (try a blind web search);
• Alan M. Frieze, Johan Hastad, Ravi Kannan, Jeffrey C. Lagarias, Adi Shamir: Reconstructing truncated integer variables satisfying linear congruences, in SIAM Journal on Computing, Volume 17 Issue 2, 1988, also freely available from the first author's website;
• Scott Contini, Igor E. Shparlinski: On Stern’s Attack Against Secret Truncated Linear Congruential Generators, in proceedings of ACISP 2005.

---

I'll first establish a characteristic of Linear Congruential Generators: states of a LCG distant from $t$ steps are linked by simple relations (of complexity independent of $t$ if we know the multiplier), when for CSPRNGs built using an iterated cipher the complexity balloons with $t$. Combined with a straightforward partial exposure of a LCG's internal state, that's a reason why LCGs are generally considered poor from a cryptographic standpoint.

Let $\forall j\in\mathbb N,\ s_{j+1}=\big(s_j\cdot a+c\big)\bmod M$ be the recurrence relation of a LCG. It follows that
$\ \ \ \ \ \forall j\in\mathbb N,\ s_{j+2}=\big(s_j\cdot a^2+c\cdot(a+1)\big)\bmod M$
$\ \ \ \ \ \forall j\in\mathbb N,\ s_{j+3}=\big(s_j\cdot a^3+c\cdot(a^2+a+1)\big)\bmod M$
and by induction $$\forall j\in\mathbb N,\forall t\in\mathbb N,\ s_{j+t}=\big(s_j\cdot a^t+c\cdot{a^t-1\over a-1}\big)\bmod M$$ This derives future states from current state without explicitly computing intermediary steps; further, if $\gcd(a,M)=1$ (as it should) this equation link states distant by $t\in\mathbb Z$ steps with equations $s_{j+t}=s_j\cdot a_t+c\cdot b_t\bmod M$, with $a_t$ and $b_t$ simple known functions of the multiplier $a$, and $t$.

---

For a concrete solution of Cases 3 as worded (with $M=2^{64}$, $a=\text{c278c0d1c04a88d9}_{16}$, unknown 64-bit INC=$c$, unknown 32-bit XOR=$x$, and 32 consecutive outputs), an idea worth trying is building an expression of the problem in the framework of boolean satisfiability. I conjecture that it is advantageous to

• make the problem strongly over-specified by incorporating many of the relations $s_{j+t}=s_j\cdot a_t+c\cdot b_t\bmod M$ with $a_t$ and $b_t$ pre-computed (the hope is that the SAT solver will take advantage of the extra relations);
• perhaps change the variable $c$ to an equivalent $c'$ that slightly simplifies the multiplicative constants $b_t$;
• perhaps trim the givens to some degree, in order to correspondingly trim the size.

Tentative sketch:

• knowing $a$, compute $a_t$, $b_t$ for $0<|t|<32$, such that $s_{j+t}=s_j\cdot a_t+c\cdot b_t\bmod M$, using the formulas above;
• pick $r$ distinct values $j_p\in\{1,32\}$ corresponding to the indexes of the $s_j$ we keep (by an entropy argument we need $5\le r\le32$, so that we have at least as many given bits as unknowns; I'd experiment starting with $r\approx8$); for a given $r$, it is advantageous that at least some of the $a_{j_p-j_q}$ have low Hamming weight;
• choose some odd 64-bit $z$ so that the Hamming weight of at least some $b'_t=z^{-1}\cdot b_t\bmod M$ is very low; we'll use $c'=z\cdot c\bmod M$ rather than INC/$c$ as the unknown for the increment, and the equations become $s_{j+t}=s_j\cdot a_t+c'\cdot b'_t\bmod M$;
• allocate the SAT variables:
  • 64 variables for $c'$,
  • 32 variables for XOR/$x$ (notice that these variables are the upper 32 bits of the $s_{j_p}$ within a polarity change determined by givens);
  • 32 variables for the lower 32 bits of each of the $r$ states $s_{j_p}$ picked
• express the $r\cdot(r-1)$ relations $s_{j_p}=s_{j_q}\cdot a_{j_p-j_q}+c'\cdot b'_{j_p-j_q}\bmod M$ for $p\ne q$ as relations between binary variables, translated into SAT clauses:
  • modular reduction is entirely free since $M=2^{64}$;
  • multiplication by known constants $a_{j_p-j_q}$ and $b'_{j_p-j_q}$ is simple, reducing to binary addition of bits of $s_{j_p}$ or $c'$;
  • our basic building block is the full binary adder with 3 inputs and 2 outputs $S=(I_0\wedge I_1\wedge I_2)\vee(I_0\wedge\overline{I_1}\wedge\overline{I_2})\vee(I_1\wedge\overline{I_2}\wedge\overline{I_0})\vee(I_2\wedge\overline{I_0}\wedge\overline{I_1})$ and $C=(I_0\wedge I_1)\vee(I_1\wedge I_2)\vee(I_2\wedge I_0)$, though some adders need no $C$ output or no $I_2$ input;
  • for each relation we need about $65\cdot32$ binary adders (a good choice of the $j_p$ and $z$ slightly cuts on that);
  • for each adder we need at most 2 extra variables (one for each used output, except those that are a bit of $s_{j_p}$);
  • especially in the low bits there will be a few duplicated variables, that we can removed;
• feed to a state of the art SAT solver, and hope that it spits the solution!

The resulting system clearly remains of manageable size; but I can not prove that it can be efficiently solved, short of trying!

Answer 3

tl;dr: Case 2 and 3 aren't any appreciable degree more secure than Case 1.

I suspect that the issues people are having with SMT-based solutions is that these LCG problems are very under-constrained:

1. The high-bit of the XOR is always unconstrained.
2. The bitwise-negation of a valid XOR is always valid. Together these yield 4 guaranteed valid XORs regardless of the number of outputs available.
3. Additionally, any LCGs with an unknown increment are very under-constrained with only 32 outputs.

Breaking Case 3

The follow are results for Case 3 from the original post:

$ time ./breaklcg
......
xorstate = 54e3e355, diff = 44c352df2ab9dd75.........................
state[0] = 0ad91a70c3b723ed, incr = fb9919619a9ba57d, xorstate = 54e3e355........
Success! 386624648 solutions
.....................
xorstate = 2b1c1caa, diff = bb3cad20d546228b.......
state[0] = 7526e58f30c325cf, incr = b5cb57a4d6b243e3, xorstate = 2b1c1caa..........................
Success! 386624648 solutions
......
Success! 773249296 solutions

real    3m21.893s
user    3m19.457s
sys     0m0.927s

(Note that state[0] above is not equivalent to SEED, but is SEED * MULT + INC. It was faster.)

There are 773 million different tuples (initial state, increment, xorstate) that match all outputs, distributed over the 4 possible xorstates (high bit flips not shown). The printed solutions are just the first found with that xorstate (aka an example).

This algorithm is a complete break (state recovery) against Case 2 and 3 LCGs with a search effectively over the hidden seed (bits of seed - bits of output + 2). You don't get any real gains from hidden increments or XORs since we can solve them sequentially. As you can see, at <4 mins the problem is quite tractable with a 64-bit seed and 32-bit output.

However, since this is a search, it doesn't scale if more state is hidden. And if only the high bit is output per round, then this algorithm actually devolves into a full brute-force through the (initial state, increment) tuples.

Breaking Case 2

Just for fun, here are the results for Case 2:

$ time ./breaklcg
.
xorstate = 00000000, diff = 9be2d85006a3b7d1..........
state[0] = 8c005b3e4d5b6951, incr = ba801c1c0025d379, xorstate = 00000000.......................
Success! 1582435690 solutions
...............................
xorstate = 7fffffff, diff = 641d27aff95c482f.................
state[0] = f3ffa4c1837b8ffa, incr = fd4a9dc24659fd3f, xorstate = 7fffffff................
Success! 1582435690 solutions
.
Success! 3164871380 solutions

real    4m2.416s
user    3m59.766s
sys     0m0.927s

Since it was given that xorstate==0, only half of the first set of results are valid, but that's still 791 million solutions. It's also a different solution than @Thomas M. DuBuisson gave. :-)

I don't know how to solve the Case 4 LCG, but I suspect its ridiculously under-constrained with only 32 outputs. Anyway, out of time for today, but I'll try to come back soon with the theory behind the algorithm, the actual code, and some experimental results on how many outputs you need to fully constrain these problems!

Algorithm

Fundamentally it's the "layering" of the unknowns which lets us attack them sequentially.

First, we'll attack the unknown XOR via LCG': the LCG of the differences between the outputs of the original LCG. LCG' has a zero increment by definition (since it cancels out). It's still not very feasible to guess both XOR and initial state simultaneously since it's at least 64 bits of entropy. Note however that LCG and LCG' are triangular functions: a bit of the new state only depends on lower bits of the state and increment and the single bit of the XOR. So we'll start by guessing the lowest 2 bits of the XOR, and if we find a state + 2 bits of xor that work, we'll guess the higher bits till we have it all. Average work is around 2^33 state updates.

Now that we have the XOR and the initial state of LCG', we can immediately compute the high 32 bits of the initial state of LCG (output[0] ^ XOR). If we knew the whole state, we could compute the increment by some simple math since we already have the initial state of LCG'. So the final step is we just guess the low 32 bits of the initial state -- approximate work 2^31 state updates.

How under-constrained are these?

A lot :-) Even with 2^32 outputs generated with randomly chosen XOR, increment and initial state, there were always multiple identical LCGs with exactly the same output. It took upwards of 2^34 outputs before a LCG was uniquely determined. This is completely consistent with how the cost of breaking is dramatically smaller than suggested by the entropy of the unknowns.

Summary

I think it's fair to say that the inclusion of an unknown increment gets you about 1 bit of security, and the inclusion of an unknown XOR gets you about 2 bits of security -- barely worth the hassle. Only increasing the amount of hidden state makes this particular attack harder. Since this is not really a sophisticated attack -- it's basically brute-force, the techniques are trivial, and is in fact my first non-toy cryptanalysis effort -- I suspect that similar analytical techniques to those that can be used against a plain LCG will make this whole construction about as insecure as a plain LCG. Which is very. ;-)

Answer 4

Putting some of my comments into writing. This is less than an answer but too much for a comment. In the comments I had claimed to apply SMT to solve case 1 - this is false, I was mistaken. I have had cases 2 and 3 running SMT (boolector, Z3, CVC4, yices) for some time without success. The closest thing to success is the identification of seeds that produce matching output for the first ~96 bits. Past that point the solvers appear to take geometrically (or worse) more time matching seed per additional bit of matching output. The formulation is a naive use of Cryptol:

lcg : {n} (fin n) => [64] -> [64] -> [64] -> [64] -> [n][32]
lcg seed inc ex mult =
    [rand | (_,rand) <- take`{n} (drop`{1} seq) ]
 where
 seq = [(seed,0)] # [(st * mult + inc, drop (((st * mult + inc) >> 32) ^ ex)) | (st,_) <- seq]

harderOutput : [4][32]
harderOutput = [0x5e3af925, 0x1b7f8e1a, 0x268c64d1, 0x4b614b92]

harderMult : [64]
harderMult   = 0xc278c0d1c04a88d9

knownMult : [64]
knownMult = 0xc278c0d1c04a88d9

knownXor : [64]
knownXor = `0x0

knownOutput : [4][32]
knownOutput = [0x8c005b3e, 0x27e3338e, 0x1bb199bb, 0x46449299]

trivialMult : [64]
trivialMult = 0xc278c0d1c04a88d9

trivialOutput : [4][32]
trivialOutput = [0x8b1294a5, 0xae5cbf0d, 0x2da164bd, 0xcbe27c6d]

doneSeed : [64]
doneSeed = 0x35e647cfd3423fd0

doneMult : [64]
doneMult = 0xc278c0d1c04a88d9

doneOutput : [4][32]
doneOutput = [0x59502137, 0xb6152ece, 0xbbd2cb88, 0xef05249f]

// case 1:
// :sat \s -> lcg s zero zero trivialMult == trivialOutput

// case 2:
// :sat \s i -> lcg s i knownXor knownMult == knownOutput

// case 3:
// :sat \s i x -> lcg s i x harderMult == harderOutput

And an example, which terminates quite quickly, in which we find initial values producing an identical first 3 words (96 bits) includes:

Main> :sat \s i x -> lcg s i x harderMult == take `{3} harderOutput
(\s i x -> lcg s i x harderMult ==
       take`{3} harderOutput) 0x897c9820380325ef 0xa75286c029abc35f 
                  0x00000000dd1aa469 = True

Notice it is actually harder (well, slower) for this method to obtain a solution in which the only unknown is the seed:

Main> :sat \s -> lcg s zero zero trivialMult == take `{3} trivialOutput
... still waiting after many minutes ...

So contrary to my earlier comment it appears a @Charphacy's mental power plus Mathematica has done better on this problem than the typical SMTs.

EDIT: And one of my stupidly-long running SAT sessions, case 2 running for just under two weeks, finished with

:sat \s i -> lcg s i knownXor knownMult == knownOutput
(\s i -> lcg s i knownXor knownMult ==
     knownOutput) 0x48f0d1a3afc9565e 0x2f21de6409b2bc69 = True 

So the seed is 0x48f0d1a37afa2b67 and increment is 0x25eff26152b834d1.

... so the real seed is 0x48f0d1a3afc9565e and increment 0x2f21de6409b2bc69 (unless I typoed something).