Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have learnt that Linear Congruential Random Number Generators are not cryptographically secure - my understanding is that given an LCG of the form:

X_n = (aX_(n-1) + c) mod m

It is possible to predict future X_n given a number of past X_n (even without knowing a, c, m).

In most implementations however there are a couple of complicating factors:

  1. The values returned usually hide a certain number of the least significant bits of X_n
  2. In most cases the values are returned modulo a small integer p.

So rather than the internal states themselves we often have only the high order bits modulo p of each state.

My question is whether it is tractable to predict future values given a number of past values with these restrictions - with proof.

I have found this paper by J. Boyar, from what I can work out it only considers point (1) though.


@fgrieu has shown that is is indeed quite trivial if we know a, c and m and m is a power of two. I'm still interested if there is a more general solution.

share|improve this question
1  
See also security.stackexchange.com/q/4268/971 for more on cracking LCGs (though with a different set of assumptions). –  D.W. Oct 8 '13 at 6:33
add comment

2 Answers 2

up vote 7 down vote accepted

This answer relates to an earlier variant of the question, which at one point gave an example problem with a, c, m known, as follows:

Consider the following in Java that prints 100 random numbers from 0 to 5:
Random r = new Random(); // seeded by system time
for (int i=0; i<100; i++) System.out.println(r.nextInt(6));

r.nextInt(6)
is essentially the following:
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
// i.e. seed = (seed * multiplier + addend)
$\bmod 2 ^ {48}$
int bits = (int)(seed >>> (48 - 31));
return bits % 6;

Yes, it is possible to predict the output of that Linear Congruential Generator variant from its first outputs. For a start, the only unknown is the original value of seed, which is 48 bits. That could be brute-forced, given moderate resources (some CPU.days), and that we have plenty enough outputs (if the output was truly random, we'd have about $100\cdot {log}_2(6) \approx 258$ bits of information). However there are much better attacks possible, succeeding in seconds.

That problem itself has varied. Originally it used a small integer (the final modulus) of 8, instead of 6. We first study that, because it turns out to be easier, and a good intro for the version with 6.

Original problem, ending in return bits % 8

Here seed has 48 bits, bits is its leftmost 31 bits, and the result bits % 8 is the 3 lower bits of that. The top 28 bits of seed never have an opportunity to influence the output of the generator (in a LCG with modulus m a power of two, a bit change in seed never propagates to lower-order bits of seed). Thus for the purpose of predicting the output, seed behaves as a 20-bit (not 48-bit) state. Further, the 3 high bits of that reduced 20-bit state are directly known from the first output.

Now, since everything except the initial state of the RNG is known, brute forcing the remaining 17 bits is almost instant. There are smarter methods that avoid the guesswork.

This illustrates that when the output of a LCG using a power of two as its modulus m is taken modulus some power of two n, the output has a much smaller period than the original LCG (and other weaknesses that may be a disaster even for simulation purposes).

Update: It turns out that Java's nextInt(int n) method special-case what happens when n is a power of two, and then does something very different from what was shown in the original question. That's in order to avoid the effect described above.

Other problem, ending in return bits % 6

Here, all 48 bits of seed have an influence on the output sequence. But there is an easy way to break these 48 bits into two separately attacked segments.

Because the final modulus 6 is even, the low bit of bits is also the low bit of the output, and leaks directly. It is the high bit of the main LCG, reduced to the low 18 bits of seed. That allows recovering the low 18 bits of seed from the low bit of the first outputs (slightly more that 18, I guess). A simple approach is enumerating the $2^{18}$ values of the low 18 bits of seed and, for each, check which gives the correct parity of the first output values. That will recover the low 18 bits of seed well under a second, and is enough to predict the parity of further output. Again, there are smarter methods that avoid the guesswork.

Now we are left with the 30 high bits of seed unknown; that can be brute-forced in seconds. Likely there are smarter methods.

Update: It turns out that Java's nextInt(int n) method does not work exactly as was shown in the original question, even when n is not a power of two; that's in order to remove a bias in the output. However, the simplified description given is good enough that the cryptanalysis described has fair chance to work as is, and can be adapted to work reliably.


Update 2: The above works because m is a power of two, and the final modulus n is divisible by $2^k$ with $k>1$. This allows a separate attack of the $k+r$ lower bits, where $r$ is the number of right bits of seed not used to produce the output ($k=1$, $r=17$ in the above example). If a and/or c and/or $r$ was unknown, it would still be possible to make this separation, and find the $k+r$ lower bits of each of seed, aand c, and the value of $r$, from a number of consecutive outputs considered $\bmod 2^k$, irrespective of the other unknowns.


A more general approach, applicable also to odd n, and perhaps to unknown a and/or c, would be to encode the problem under the formalism of boolean satisfiability, and use one of the many automated solvers available. I can't predict the runtime, though. This flexible approach has broken some mildly serious ciphers, see e.g. this cryptanalysis of A5/1, or this one.


LCGs are seriously bad for cryptographic purposes. They are fine for continuous simulation purposes (where the output is turned into the mantissa of a floating-point number and used as such), but brittle for discrete simulation purposes. In particular, if the LCG uses a power of two as its modulus m, do not take its output modulus an even number and expect the result to behave as a dice with that number of faces: that assumption is incorrect, and many simple tests will show that. For example, the imbalance between the number of odd and even results in consecutive (simulated) dice throws is exactly zero after $2^{1+r}$ throws (here $2^{18}$). This would be detected much before that with a bidirectional Chi-squared test of nextInt(6)%2 or even just nextInt(6).

share|improve this answer
    
Thanks, I have changed the modulus to 6 since it need not be a power of two - not sure if this makes a difference. –  Andrew Mar 13 '12 at 22:01
1  
The low-order bits never have an opportunity to influence the output of the generator, which for the purpose of predicting the output behaves as a 20-bit (not 48-bit) state. The low-order bits are not used in the output, but they affect the next output - changing the low-order bits will change the high-order bits and hence the output from the next seed. This means bruteforcing high-order bits is not sufficient. –  Andrew Mar 14 '12 at 3:00
    
Can you possibly explain the second part in more depth? I'm not sure I follow what you are doing. –  Andrew Mar 14 '12 at 7:01
    
@Andrew: What the answer contains is "The top 28 bits of seed never have an opportunity to influence the output of the generator". While I have goofed on the number, that is now fixed (top has been correct all along). I have added more explanations on that, and in the second part. –  fgrieu Mar 14 '12 at 7:53
1  
You are of course right! I misunderstood which bits you were referring to. I simplified the algorithm with the assumption that n is not a power of two in the original question. Your second procedure will work for n=6 - nice work. How many values are required to know with certainty the future values? –  Andrew Mar 15 '12 at 6:03
show 7 more comments

Yes. I don't have the references at hand, but I'll bet you can use your favorite search engine to find it. As I remember it, with something like three values from a linear-congruential generator, you can predict values. It might be more if you're truncating to only eight bits, but it's such a horrible flaw that you really shouldn't even be giving this a lot of thought.

If you must use a quick-and-dirty random bit generator, take a decent hash function (even SHA-1 is good enough for this) and iterate hashing the hash value. Bonus points for duplicating the context, finalizing it, and then hashing the value into the cumulative context.

But you get even more bonus points for using something designed to be a fast PRNG. Get an implementation of the NIST AES-CTR DRBG (that's Deterministic Random Bit Generator) that uses AES in Counter Mode to generate random bits.

There are open source implementations available and they're reasonably fast even with software AES. The last one I used was even faster than rc4random that's part of many unixes. If you are on an Intel processor with AES-NI (and do the software engineering to bolt that in), it runs like stink.

Really, look away from the abyss before it looks into you. Get a good PRNG.

EDIT

In response to your comment, look at this paper called "How to crack a Linear Congruential Generator." It even has source code.

share|improve this answer
1  
You're right - I want to understand why though. So far I haven't been able to find an algorithm anywhere with the two conditions listed above that breaks it. I wouldn't use it in practice in any case :) –  Andrew Mar 14 '12 at 7:06
    
I've added in more text along with a link to an applicable paper. –  Jon Callas Mar 14 '12 at 23:21
add comment

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.