2
$\begingroup$


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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Highly appreciated, I think I understand what you are saying. So basically you are saying to solve for s2, using every possible value for s1, and then check if the values given by that match up to the next consecutive outputs? Presumably doing this with multiple threads in order to make it finish in a reasonable time? $\endgroup$ – Jayden Mar 26 '18 at 6:34
  • $\begingroup$ @Jayden: Yes. If we have one exact value of $(s_1-s_2)\bmod m_1$, the job to be done for each $s_1$ reduces to a handful of integer arithmetic operations. Since that must be repeated at most $2^{31}$ time, and modern CPUs run at like $2^{33}$ instructions per second per thread, I guess we won't need multi-thread to be well under a minute, with a good implementation. Of course, this is ideal grounds for parallelization. $\endgroup$ – fgrieu Mar 26 '18 at 6:53
  • $\begingroup$ Alright, I have the basics of that in a program already as that was my first thought, but I am thinking I must have messed something up along the way since it did not go very fast at all. Thanks for the insight! $\endgroup$ – Jayden Mar 26 '18 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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