# Cracking a linear congruential generator

I was recently listening to the security now podcast, and they mentioned in passing that the linear congrunential generator (LCG) is trivial to crack. I use the LCG in a first year stats computing class and thought that cracking it would make a nice "extra" problem.

Are there any nice ways of cracking the LCG that doesn't involve brute force?

I'm not sure if this question is OT, but I wasn't sure where else to post the question. Also, my tags aren't very helpful since I don't have enough rep to create new tags.

• @jeff I'm sure there are experts on this one here also, and this site focuses on the right mindset for the question. Note also that wikipedia notes "If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis." Jun 2, 2011 at 15:14

Yes. There are extremely efficient ways to break a linear congruential generator.

A linear congruential generator is defined by sn+1 = a sn + b mod m, where m is the modulus. In its simplest form, the generator just outputs sn as the nth pseudorandom number. If m is known to the attacker and a, b are not known, then Thomas described how to break it.

If none of a, b, m are known, one can still break a linear congruential generator, by first recovering m. It is an interesting exercise to derive how to do so efficiently; it can be done. I'll show how below; don't read on if you prefer to try to figure it out for yourself.

To recover m, define tn = sn+1 - sn and un = |tn+2 tn - t2n+1|; then with high probability you will have m = gcd(u1, u2, ..., u10). 10 here is arbitrary; if you make it k, then the probability that this fails is exponentially small in k. I can share a pointer to why this works, if anyone is interested.

The important lesson is that the linear congruential generator is irredeemably insecure and completely unsuitable for cryptographic use.

Added: @AviD will hate me even more :), but here's the math for why this works, for those who requested it.

The key idea: tn+1 = sn+1 - sn = (a sn - b) - (a sn-1 - b) = a sn - a sn-1 = a tn mod m, and tn+2 = a2 tn mod m, and tn+3 = a3 tn mod m. Therefore tn+2 tn - tn+12 = 0 mod m, i.e., |tn+2 tn - tn+12| is a random multiple of m. Nifty number theory fact: the gcd of two random multiples of m will be m with probability 6/π2 = 0.61; and if you take the gcd of k of them, this probability gets very close to 1 (exponentially fast in k). Is that cool, or what?

• Also, a linear congruential generator is often bad at producing statistically good randomness. If m is even, a and b are odd, then the least significant bits of the successive values of s follow the very non-random pattern 010101010101... Jun 3, 2011 at 15:35
• aaagghh, too much math! +1, anyway... ;)
– AviD
Jun 6, 2011 at 22:44
• @csgillespie, OK, I added the math. @AviD, avert your eyes! :)
– D.W.
Jun 7, 2011 at 19:19

A linear congruential generator is linear, which should say it all.

Namely, you have a state s, which is updated with: s ← as + b mod w, for two constants a and b, and a convenient modulus w (typically 232: s, a and b are 32-bit words); the output consists in the successive values of s. If you have three successive outputs (s0, s1 and s2), then you get two linear equations in two unknowns (a and b), which are easily solved with elementary arithmetics.

This can be extended to variants where you only get parts of the values s, possibly not consecutive. If a and b are two 32-bit constants, you only need about 96 bits worth of output to recompute the constants.

• You'll enjoy the DVSorder Vulnerability I posted as another answer.... Oct 14, 2022 at 20:02

Another method of solving for m comes from this paper.

Essentially, this method exploits the fact that the linear congruential generator dramatically fails the planes test. The determinant of a 3x3 matrix using 4 outputs is a multiple of m.

The gcd of two multiples (n_1 and n_2 of m is m if x_1 = n_1/m and x_2 = n_2/m are co-prime.

The probability that k integers are co-prime is given by 1/ζ(k) so the probability that x_1 and x_2 are co-prime is 1/ζ(2) or 6/π^2, about 61%.

Like @Thomas said, once m is found the remainder of the problem is easy.

For a great example of productive use of these techniques in real life, see The DVSorder Vulnerability, in which it is shown how a voting machine manufacturer totally botched their generation of "random" numbers. Note that multiple members of the team were able to independently reconstruct the complete PRNG algorithm. Available as an exercise for the reader (or a class in crypto) based on the example sequence given.

Hint: it is not nearly enough to substitute and shuffle digits in a deterministic linear sequence....

303001 720012 195008 857815 739854 611861 876852 483368 668355 040324

907271 224222 599278 956625 332644 513631 170642 385138 764145 149184

801991 722982 693998 858485 435414 617401 074412 481708 266715 042754