Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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.

share|improve this question
    
I think your question does fit here. I think your question may have a better chance of being answered at math.stackexchange.com. Cross-posting is generally frowned upon, but I'd encourage ignoring that convention in this particular case. I don't think anybody will bark at you. –  Jeff Ferland Jun 2 '11 at 13:47
1  
@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." –  nealmcb Jun 2 '11 at 15:14

2 Answers 2

up vote 16 down vote accepted

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 = (a-1) sn mod m, and tn+1 = (a-1)2 sn mod m, and tn+2 = (a-1)3 sn mod m. Therefore tn+2 tn - t2n+1 = 0 mod m, i.e., |tn+2 tn - t2n+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/π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?

share|improve this answer
4  
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... –  Thomas Pornin Jun 3 '11 at 15:35
    
Thanks. Please share your pointer of why this works. I should add, that I only use the LNG as a simple illustration of a PRNG and stress that it is no longer used. –  csgillespie Jun 5 '11 at 19:48
1  
aaagghh, too much math! +1, anyway... ;) –  AviD Jun 6 '11 at 22:44
1  
@csgillespie, OK, I added the math. @AviD, avert your eyes! :) –  D.W. Jun 7 '11 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.