Cracking a linear congruential generator

Question

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.

Answer 1

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

A linear congruential generator is defined by s_n+1 = a s_n + b mod m, where m is the modulus. In its simplest form, the generator just outputs s_n 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 t_n = s_n+1 - s_n and u_n = |t_n+2 t_n - t²_n+1|; then with high probability you will have m = gcd(u₁, u₂, ..., u₁₀). 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: t_n+1 = s_n+1 - s_n = (a s_n - b) - (a s_n-1 - b) = a s_n - a s_n-1 = a t_n mod m, and t_n+2 = a² t_n mod m, and t_n+3 = a³ t_n mod m. Therefore t_n+2 t_n - t_n+1² = 0 mod m, i.e., |t_n+2 t_n - t_n+1²| is a random multiple of m. Nifty number theory fact: the gcd of two random multiples of m will be m with probability 6/π² = 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?

Answer 2

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 2³²: s, a and b are 32-bit words); the output consists in the successive values of s. If you have three successive outputs (s₀, s₁ and s₂), 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.

Answer 3

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.