# How to attack a fixed LCG with partial output?

To show some colleague programmers exactly how broken C's rand() is (at least on Windows) I decided to break it. So everyone knows the exact parameters, MSVC's implementation is as follows:

uint32_t state;

int rand() {
state = state * 214013 + 2531011;
return (state >> 16) & 0x7fff;
}


Because the top bit never affects anything but the next top bit in the next state and is never returned you could see this as the LCG $X_{n+1} \equiv (214013X_n + 2531011) \mod 2^{31}$ where at each iteration we only get to see the top 15 bits.

The problem is, I have not found any references that attack fixed LCG's with partial output.

Of course it requires only 2-3 calls of the rand() function to enable a bruteforce attack with at most $2^{16}$ operations on the secret part of the state, but that's hardly a break. Something similar would not be feasible with larger constants and a larger modulus.

So far I've been unable to find a break that shows this generator to be severely broken. I'm interested in results on similar LCG's that can be transformed to an attack on this one.

P.S.: If an attack exists that could be done on a graphical calculator without any programming, it increases how convincingly I can show the generator to be broken. But this is just bonus points.

-

All quantities are non-negative integers.
$X_n$ is the 31-bit state with $X_{n+1}=(a·X_n+b)\bmod 2^{31}$, $a=214013$, $b=2531011$.
$R_n=\lfloor X_n/2^{16}\rfloor$ is the 15-bit output.
$S_n=X_n-2^{16}·R_n$ is the hidden 16-bit portion of the state.

Assume we have the first few outputs $R_0$, $R_1$.. and want to find $X_0$.

We derive: $$\big((2^{16}·R_1+S_1)\bmod 2^{31}\big)=\big((a·(2^{16}·R_0+S_0)+b)\bmod 2^{31}\big)$$ $$2^{16}·R_1-a·2^{16}·R_0-b+S_1\equiv a·S_0\pmod{2^{31}}$$ $$\exists! K, \big((2^{16}·R_1-a·2^{16}·R_0-b+S_1)\bmod 2^{31}\big)=a·S_0-2^{31}·K$$ Using that $S_1<a$, we derive
$$S_0=\Big\lfloor{{\big((2^{16}·R_1-a·2^{16}·R_0-b+2^{16}-1)\bmod 2^{31}\big)+2^{31}·K}\over a}\Big\rfloor$$ $$2^{16}-1-S_1=\Big(\big((2^{16}·R_1-a·2^{16}·R_0-b+2^{16}-1)\bmod 2^{31}\big)+2^{31}·K\Big)\bmod a$$

Therefore the following outputs the possible values for $X_0$ given the first two outputs $R_0$ and $R_1$

• compute $T=(2^{16}·R_1-a·2^{16}·R_0-b+2^{16}-1)\bmod 2^{31}$
• for $K$ from $0$ to $\lfloor (2^{16}·a-1-T)/2^{31}\rfloor$
• if $\big((T+2^{31}·K)\bmod a\big)<2^{16}$
• output $\big\lfloor(T+2^{31}·K)/a\big\rfloor+2^{16}·R_0$

This works for any $a\ge2^{16}$. With the parameters at hand, the loop is performed at most $7$ times, with typically $2\pm1$ outputs. I can run the algorithm with pen and paper, and some would be able to perform it mentally.

The method works regardless of the bit size $x$ of $X$, an output $R$ with $x/2$ high bits (give or take a constant), and $a$ big enough that the attack works: the cost is $O(x^2·a/2^{x/2})$ using standard arithmetic algorithms. I think we could avoid most values of $K$ that do not pass the test, bringing the cost to $O(x^2)$ even for huge $a$.

When $a$ is too small to carry that attack, a trivial attack applies, recovering the state $X_0$ from most to least significant bits, at a rate of about $\log_2a$ additional bits for each additional $R_n$.

Generally speaking, Linear Congruential Generators are very poor from a cryptographic standpoint, even when some post-processing is applied; see this answer for an example.

More often than not, Linear Congruential Generators are not even suitable for simulation purposes. To demonstrate this to the incredulous, generate a million values using the LCG in the question; count how many times each of the 32768 values is reached; and either compute the standard deviation of that, or graph the counts sorted by increasing values; repeat with a sound RNG, and compare.

-

You already answered your own question: given the output from 2 calls to the rand() function and $2^{16}$ steps of computation, you can recover the internal state completely, simply by brute-forcing the parts of the state that you are not aware of. That is a break.

You say it's "hardly a break", but that is too-narrow thinking. A break is a break; anything that suffices to predict future outputs of the generator is a break. It does break Window's rand() implementation.

Maybe you are wondering whether some other generator that looks sorta like Window's rand(), but is not Window's rand(), would be breakable. Well, that's a different question. The answer to that will depend upon what specifically you have in mind -- but regardless, at that point we're not talking about Window's rand() any longer. The break you've got is already good enough to show that Window's rand() should not be used for cryptographic purposes. It's plenty adequate to show how broken Window's rand() is.

If this doesn't count as "good enough" of an attack, then probably your question isn't really a question about cryptography, but something else -- because for cryptographic purposes, this is a valid break.

That said, there is a slight improvement on the attack. I believe you can build a meet-in-the-middle attack that needs about $2 \times 2^8$ steps of computation and 2 outputs from rand(), and that infers its internal state.

Here's the idea. Suppose you observe the top 16 bits of $X_0$. Now write $X_0 = c + 2^8 d + e$, where $0 \le d,e < 2^8$ and $c$ is a known constant. Notice that this means

$$X_1 = (214013 c + 2531011) + 2^8 \cdot 214013 d + 214013 e.$$

The first part ($214013 c + 2531011$) is a known constant, so we have

$$X_1 = \text{known} + \text{known} \times d + \text{known} \times e.$$

or in other words,

$$X_1 - \text{known} - \text{known} \times d = \text{known} \times e.$$

Now we're set up to do a meet-in-the-middle attack. We know the top 16 bits of $X_1$. We can enumerate all $2^8$ possibilities for $e$, calculate the resulting top 16 bits of the right-hand side, and store them in a table. We can then enumerate all $2^8$ possibilities for $d$, calculate the resulting top 16 bits of the left-hand side, and look it up in the table to check for a match. When we guess them right, we should find a match.

-
I'm looking to show that rand() is unsuitable for nearly any purpose, rather than just cryptographic purposes. And I'm looking for 2 things here: either a better attack requiring less computation (preferably to be done with just a graphical calculator), or some reference recommendations for breaking LCG's with partial output. And my "break" doesn't work anymore if we'd change state to uint64_t (and change the shift to 48). –  orlp Sep 28 '13 at 6:32
@nightcracker, in that case, it sounds like your question is not about cryptography per se, so I don't think it is on-topic here. The cryptographic aspect of the question has been answered.... –  D.W. Sep 28 '13 at 6:52
How so? The existence of a $2^{16}$ attack does not mean all further research on attacks should be stopped - especially considering that the internal state is only twice as large as that. –  orlp Sep 28 '13 at 8:24
@nightcracker, I think it does mean that. A $2^{16}$ attack means the generator is broken. It means absolutely no one should use the generator. At that point, who cares whether there is a $2^8$ attack? How will that affect your decision-making? If news of a $2^8$ attack will cause you to avoid the generator, when news of a $2^{16}$ attack wouldn't, then there is something wrong with your decision-making. P.S. If your question is about other generators like the Windows rand(), but different (say with larger parameters), then that's a different question: post a new question. –  D.W. Sep 28 '13 at 17:05

Related to "show some colleague programmers"

You could code and use a smaller 8-bit rng to show them a "mini version" of C's rand. The period will be shorter and therefore more obvious… you can print the complete period (256 bytes) on screen. Seeding the rng in +1 steps and printing the next 256 bytes will show them they're actually only rotating a sequence of 256 predicable bytes. After that, it shouldn't be a huge step to convince them that bigger numbers don't fix the predictability problem. Also, the 8-bit version provides a playground to build upon towards attacking MSVC's implementation.

Related to "references that attack fixed LCG"

There is a paper that might be interesting for you to take a look at:

It includes a C code example which allows the calculation of the seed used in an LCG.

Related to "graphical calculator"

Well, it is probably not what you were thinking of as it doesn't attack any LCG, but there is a piece of software that allows to experiment with the parameters of an LCG and which visualizes the subtle correlations between the pseudo-random numbers successively created by an LCG.

You can grab either the English or the German version at
http://www.vias.org/simulations/simusoft_lincong.html

-