Plumstead, Joan B. “Inferring a sequence generated by a linear congruence.” Foundations of Computer Science, 1982. SFCS’08. 23rd Annual Symposium on. IEEE, 1982.

Synopsis

Pseudo-random number generators of the form \(X_{t + 1} = a X_t + b \mod m\) can be “easily” broken – i.e. \(a\) and \(b\) can be inferred by looking at at most \(O(log_2(m))\) elements in the PRNG sequence. Inferring \(m\) is a bit harder1, but all of \(a\), \(b\) and \(m\) can be inferred with at most \(O(log_2(m))\) errors where an error is a mismatch between a predicted and an actual element in the random sequence. It is assumed that the algorithm is “told” what the correct value is when it makes a mistake.

What I Learned

Key insight for me was that an \(ax+b\) PRNG is not as secure as its seed. Just by knowing (or guessing!) that the PRNG is of the form \(ax+b\), an adversary can recover the seed.

  1. Imagine \(a = 1\) and \(b = 1\) (i.e. the “random” sequence is just a monotonically increasing sequence). Then it may take a very long time for the sequence to “wrap” around \(m\), and until it wraps there is no restriction on what \(m\) can be. ↩