LCG Cracking: Predict Future Numbers

TL;DR

Linear Congruential Generators (LCGs) are simple random number generators often used for testing or in situations where strong security isn’t needed. They’re easy to break if you know a few generated numbers. This guide shows how to predict future values from an LCG sequence.

Understanding the LCG

An LCG produces a sequence of numbers using this formula:

Xn+1 = (a * Xn + c) mod m

• X_n+1: The next number in the sequence.
• X_n: The current number in the sequence.
• a: The multiplier.
• c: The increment.
• m: The modulus (often a power of 2).

If you know a, c, and m, predicting the sequence is easy. But often, you only have a few generated numbers to start with.

Steps to Crack an LCG

1. Gather Enough Numbers: You need at least as many consecutive numbers as there are variables (a, c, and m) to solve for them. More is better!
2. Determine the Modulus (m): This is often the easiest part.
   • Look for a pattern in the generated numbers. If they seem to wrap around at a certain value, that’s likely your modulus.
   • If you know the LCG is used in a programming language like C++, m might be related to the size of an integer type (e.g., 2³² for unsigned int).
3. Solve for ‘a’ and ‘c’: Once you know m, you can use two consecutive numbers from the sequence to create a system of equations.

   Let’s say you have X₁ and X₂. You can write:

   X2 = (a * X1 + c) mod m

   X3 = (a * X2 + c) mod m

   You now have two equations with two unknowns (a and c). Solve this system. A simple approach is to subtract the first equation from the second:

   X3 - X2 = a * (X2 - X1) mod m

   Then, solve for a. Be careful with modular arithmetic – you might need to find the modular inverse of (X₂ – X₁).

4. Calculate ‘c’: Substitute the value of a back into one of your original equations and solve for c.
5. Predict Future Numbers: Now that you know a, c, and m, you can generate any future number in the sequence using the LCG formula.

   Xn+1 = (a * Xn + c) mod m

Example

Let’s say you have these three consecutive numbers: 5, 8, 13 and you suspect the modulus is 16.

1. m = 16 (assumed)
2. Solve for ‘a’:

   8 = (a * 5 + c) mod 16

   13 = (a * 8 + c) mod 16

   Subtracting the first from the second:

   5 = a * 3 mod 16

   The modular inverse of 3 modulo 16 is 5 (because 3 * 5 = 15 which is congruent to -1 mod 16).
   Therefore, a = 5 * 5 mod 16 = 9

3. Solve for ‘c’:

   8 = (9 * 5 + c) mod 16

   8 = 45 + c mod 16

   8 = 13 + c mod 16

   Therefore, c = -5 mod 16 = 11

4. Predict the next number:

   X4 = (9 * 13 + 11) mod 16

   X4 = (117 + 11) mod 16

   X4 = 128 mod 16 = 0

Important Considerations

• Modular Inverse: Finding the modular inverse is crucial. If it doesn’t exist, your modulus might be incorrect or you need a different approach.
• Large Modulus: For very large moduli (e.g., 2⁶⁴), solving the equations can become computationally expensive. Specialized tools and libraries may be needed.
• Security Implications: LCGs are not suitable for cyber security applications where unpredictability is essential. They’re easily broken, as demonstrated here.