# How Brittle Are LCG-Cracking Techniques?

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”.

• I'm not sure how your quote is relevant. Lagged fibonacci generators are not linear congruential generators. And in any case, we're talking here about predictability rather than statistical quality. (It's possible to have RNGs that pass reasonable statistical tests yet are predictable.) – Charphacy Nov 27 '14 at 17:03
• In the current (3rd, 1998) edition of tAoCP, Question 7 at the end of Section 3.6 (volume 2, page 193) is the only place in the book where he talks about RNG-based encryption. The answer to that question (page 599) references his 1985 paper without any reservation and also cites many of the other papers Boyar, Frieze, etc. – Charphacy Nov 27 '14 at 18:29
• The problem is that you can't just pick INC to be anything because certain values will give you a reduced period. So in practice INC can be assumed a fixed constant. – Antimony Dec 2 '14 at 4:38
• @Thomas M. DuBuisson: My intuition is that even Case 3 could be solved using Cryptol and a SAT/SMT solver, as you did in this nice answer to a much more trivial problem. $\;$ If it indeed works, that would be a very convincing demo! – fgrieu Dec 7 '14 at 17:30
• fgrieu: I suspected the same thing and have learned 1) SMT solvers are pretty slow at this sort of thing (already known by others in the field, so I've found out) 2) There is a bug in either Cryptol or SMTs I used that caused Cryptol to exit with an exception when the solution was discovered instead of printing the seed etc. – Thomas M. DuBuisson Dec 7 '14 at 18:10

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.

• It is good to see the automation provided by Mathematica provides similar results as the SMT solvers I've tried - solving case 1 trivially and providing partial solutions to case 2. – Thomas M. DuBuisson Dec 9 '14 at 20:30
• Thomas, if you built a solution for cases 1 and 2 (e.g., in Cryptol), I'd love to see you write up an answer and post it, because it's great to see other ways the problem can be solved! – Charphacy Dec 9 '14 at 22:37
• If with enough output your method (or that of Stern improved by Contini & Shparlinski) could solve Case 2 with only say the 4 top bits of the output, then we could enumerate the $2^4$ possible values of the XOR mask, and solve Case 3 by solving Case 2 at most 16 times. – fgrieu Dec 10 '14 at 8:36
• @fgrieu, I think your idea would work for an XOR applied to Case 1, but for Case 2 (which is glossed over by most papers with “oh, just subtract!”), it's a bit more computationally intensive because of the possibility of borrow (from subtracting the low-order bits). We need sixteen terms to solve it, and sixteen unknown borrows, that makes $2^{16}$ possibilities. Coupled with our $2^4$ XORs, we have $2^{20}$ cases to search, at 1 minute each from my timings. That's is about two years work. It's actually faster to just brute-force the 32-bit XOR constant—you'd be done in 17 months! – Charphacy Dec 10 '14 at 18:05
• An improved attack: because $M=2^{64}$ is a power of $2$, we can remove the leftmost $32-r$ bits of every constant and variable in the problem, say with $r\approx6$. We now know $r/(r+32)$ of the state (in Case 3: within XOR with unknown $r$-bit XOR we can enumerate), rather than $r/64$ in my previous attack; and that's an easier problem according to Contini&Shparlinski. If the running time to solve Case 2 with $r/(r+32)$ exposed bits is $f(r)$, choose $r$ that minimize $2^r f(r)$ to minimize total time to find the right XOR. Then, finding the other bits one by one is very easy. – fgrieu Dec 10 '14 at 21:38

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:

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!

• First, thanks for being the first person to write an answer! For the LLL algorithm section, you mention the often-quoted results (Frieze, Stern, etc.), but it'd be good to carry it through to the end, because there are lots of parts after the LLL algoritm is used that are usually sketchy/hand-waved, and the devil is in the details! You also say “but I can not prove that it can be efficiently solved, short of trying”, and I think that actually trying to solve the problem is key. After all, any problem can that can be computed using digital logic can be construed as a SAT instance. – Charphacy Dec 8 '14 at 18:53
• @Charphacy: I have an itch to try the SAT approach (no insurance). I think that I can't use the LLL, because there is too little output to carry it, at least the way that I have sketched it (did not check the references in detail). – fgrieu Dec 8 '14 at 21:12
• FWIW, I've added my own answer for cases 1 and 2, showing that you can get a good answer for the first case with only three outputs, and a very-good approximation for the second case with only four outputs. I also mention a bit about the LLL algorithm, but I mostly don't use/need it. – Charphacy Dec 9 '14 at 9:55
• You say “complexity independent of t if we know the multiplier”, but this property amounts to the existence of jump-ahead, and is actually true for some cryptographically secure RNGs such as ChaCha20, so I don't think it necessarily follows that having jump-ahead implies insecurity. Possibly the simplicity of the jump ahead function might, but even for LCGs it's essentially an exponentiation operation. – Charphacy Dec 9 '14 at 17:56
• @Charphacy: I have adapted my answer per your last comment. – fgrieu Dec 9 '14 at 18:21

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).

• Thanks for writing up your code! I've put a generalized version of your lcg function on pastebin [no space to put it in this comment!], which may be useful for experimenting with different bit sizes to see how they affect performance. Using your code (and my tweaks), I confirmed that your 96-bit case is solved quickly (almost instantly by yices2) and the other ones are hard, but I think that's because it's very underconstrained (different solvers get different answers). – Charphacy Dec 11 '14 at 18:46
• @Charphacy See my edit. – Thomas M. DuBuisson Dec 22 '14 at 5:40
• Alas, the seed and increment found by your SAT solver aren't quite the right ones. The 8th and 9th outputs should be 0x6b1bd36f and 0xab7f4d33, but your solution produces 0x6b1bd36e and 0xab7f4d32. Only the high 32 bits of your seed are correct; the low order 32 bits and the entire increment don't match. – Charphacy Mar 2 '15 at 1:44
• @Charphacy Ah, so much for leaving out constraints to speed up the solver. I've posted newer numbers now. Obviously the SAT solver is not smart enough to figure this problem out quickly, though it is more efficient than brute force. – Thomas M. DuBuisson Apr 17 '15 at 3:08
• Nice work. Did it take longer when you added those constraints? Interestingly, although your constants reproduce the data I gave in my example, they aren't the ones I used. But to show a difference, we need to go much further out in the sequence. In fact, your output is off by one at the following positions (numbering the sequence starting at one): 94, 232, 292, 485, 633, 724, 797, 871, 944, 1325, 1409, 1421, 1549, 1575, 1803, 1883, 1897, 1992, 2069, 2106, 2140, 2159, 2297, 2479, 2546, 2615, 2626, 2663, …. It seems to stay “close enough” forever, but where the error occurs seems random. – Charphacy Jul 6 '15 at 17:29

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. ;-)

• Thanks for this! I look forward to the promised next installment!! – Charphacy Jan 22 '16 at 7:36
• I almost forgot about this! Thanks for the ping @Charphacy. I added all the details I could remember, but I finished working on this a while back. Hope it's useful! – Andrew Bortz Jan 24 '16 at 5:54