Breaking variations of Linear Congruential Generators

Question

So I have been trying to learn a bit of cryptanalysis and breaking pseudorandom generators as of recently, but I have run into a roadblock in my learning as I cannot crack this one problem. Basically it is a variation on an LCG, but I cannot figure out how to solve it, even though I am pretty certain it is weak, I just lack the understanding of what technique to try.

The generator is from the random number generator used by TI calculators as found here.

Basically it goes as follows:

$$\begin{align} s_1&\gets s_1\cdot a_1\bmod m_1\\ s_2&\gets s_2\cdot a_2\bmod m_2\\ r&\gets (s_1-s_2)/m_1\\ \text{if }&r<0\text{ then }r\gets r+1 \end{align} $$ [Notes of the editor: That generator is equivalent to the one of figure 3 in Pierre l’Écuyer's Combined Multiple Recursive Random Number Generators, CACM Volume 31 Issue 6, June 1988, p. 742-751. The moduli $m_i$ are primes slightly below $2^{31}$ with $\gcd(m_1-1,m_2-1)=2$ and $m_1$ slightly larger than $m_2$. The $a_i$ are even constants somewhat below $\sqrt{m_i}$, giving maximal period and said to give good results for the spectral test of the multiplicative LCGs. Variable $r$ is floating-point. In l’Écuyer's paper, we have $r=((s_1-s_2)\bmod m_1)\cdot(\widetilde{1/m_1})$ where $\widetilde{1/m_1}$ is a close floating-point approximation by default of $1/m_1$, and $v=u\bmod m$ means that $0\le v<m$ and $m$ divides $u-v$. ]

This small variation has stifled my attempts (which have been off and on for a few months). If anyone has an explanation of how to get the next number from only the results I would love to know, or even if you could point me in the right direction it would be greatly appreciated.
Thanks!!!

P.S.: I hope this is in the right category, I am new to this website and have also searched through the similar questions and couldn't find any that would help me out here.

Answer 1

This generator has a state defined by $s_1$ and $s_2$, and can take just below $2^{62}$ states. This can't be cryptographically secure by today's standards, which call for more than 80-bit security, but is still quite too much for fast cryptanalysis by pure brute force using a single CPU. We need at least one serious speedup.

The most obvious is: enumerate the (less than $2^{31}$) states $s_1$, and for each deduce $s_2$ from one output (giving us $(s_1-s_2)\bmod m_1$ ) and $s_1$ (or, in rare case, that $s_1$ can't have that value); then check these $s_1$ and $s_2$ with a few more outputs.

The devil is in the details, and in particular the error we have on $(s_1-s_2)\bmod m_1$ as reverse-computed from actual output. If $r$ is given with 6 decimal figures on the right of the decimal point, we only get about 20 out of 31 bits (but if $r$ is given with 6 significant digits, we'll get more for small $r$). This is however enough to reconstruct $s_2$ from two consecutive outputs and values of $s_1$ without enumerating all the possible values of $(s_1-s_2)\bmod m_1$ (that would only be a last resort).

The above is crude, but will get the job done in seconds with a careful implementation on a modern CPU. And (quoting Bruce Schneier, attributing the saying to the NSA):

Attacks always get better; they never get worse.

Note: since Pierre l’Écuyer's generator has been around for nearly 3 decades, is quite usable for non-cryptographic purposes like simulations, portable, relatively efficient given that constraint, and apparently often used, I would not be surprised if it had been studied in depth, and a much better attack found.

---

Assuming we have an $r$ (like 4.833936e-5) that let us walk back to $(s_1-s_2)\bmod m_1\ =d$ exactly, the unoptimized algorithm goes:

• for $s_1$ from $1$ to $m_1-1$
  • $s_2\gets(s_1-d)\bmod m_1$
  • if $0<s_2<m_2$
    • $s_{1.1}\gets s_1\cdot a_1\bmod m_1$
    • $s_{2.1}\gets s_2\cdot a_2\bmod m_2$
    • if $(s_{1.1}-s_{2.1})\bmod m_1$ matches output well enough
      • $s_{1.2}\gets s_{1.1}\cdot a_1\bmod m_1$
      • $s_{2.2}\gets s_{2.1}\cdot a_2\bmod m_2$
      • if $(s_{1.2}-s_{2.2})\bmod m_1$ matches output well enough
        • success, output $(s_1,s_2)$ and stop.
• Failure, refine.

A possible improvement is that most of the time $s_{1.1}−s_{2.1}$ varies by $a_1-a_2$ from one step to the other of the outer loop, and that's small, which allows to fast-forward $s_1$ considerably. I believe that alone will reduces the attack to a mere fraction of a second (c.f. saying).