8
$\begingroup$

To show some colleague programmers exactly how broken C's rand() is (at least on Windows) I decided to break it. So everyone knows the exact parameters, MSVC's implementation is as follows:

uint32_t state;

int rand() {
    state = state * 214013 + 2531011;
    return (state >> 16) & 0x7fff;
}

Because the top bit never affects anything but the next top bit in the next state and is never returned you could see this as the LCG $X_{n+1} \equiv (214013X_n + 2531011) \mod 2^{31}$ where at each iteration we only get to see the top 15 bits.

The problem is, I have not found any references that attack fixed LCG's with partial output.

Of course it requires only 2-3 calls of the rand() function to enable a bruteforce attack with at most $2^{16}$ operations on the secret part of the state, but that's hardly a break. Something similar would not be feasible with larger constants and a larger modulus.

So far I've been unable to find a break that shows this generator to be severely broken. I'm interested in results on similar LCG's that can be transformed to an attack on this one.

P.S.: If an attack exists that could be done on a graphical calculator without any programming, it increases how convincingly I can show the generator to be broken. But this is just bonus points.

$\endgroup$
13
$\begingroup$

Notations:

  • $v=u\bmod m$ means $m$ divides $u-v$ and $0\le v<m$, including if $u<0$.
  • All variables are non-negative integers (except for the above).
  • $a=214013$, $b=2531011$ are the LCG parameters.
  • $X_n$ is the 31-bit state with $X_{n+1}=(a\cdot X_n+b)\bmod 2^{31}$.
  • $R_n=\lfloor X_n/2^{16}\rfloor$ is the 15-bit output.
  • $S_n=X_n-2^{16}\cdot R_n$ is the hidden 16-bit portion of the state.

Assume we have the first few outputs $R_0$, $R_1$.. and want to find $X_0$.

We derive:
$$\big((2^{16}\cdot R_1+S_1)\bmod 2^{31}\big)=\big((a\cdot (2^{16}\cdot R_0+S_0)+b)\bmod 2^{31}\big)$$ $$2^{16}\cdot R_1-a\cdot2^{16}R_0-b+S_1\equiv a\cdot S_0\pmod{2^{31}}$$ Using that $S_1<2^{16}$ and defining $r=2^{16}-1-S_1<2^{16}$, that becomes:
$$2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1\equiv a\cdot S_0+r\pmod{2^{31}}$$ Defining $K$ as the quotient of the Euclidean division of $a\cdot S_0+r$ by $2^{31}$, it comes:
$$\big((2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod2^{31}\big)+2^{31}\cdot K=a\cdot S_0+r$$ Using that $r<2^{16}\le a$, we find that $S_0$ must be the quotient of the Euclidean division of the new left side of the equation by $a$, and $r$ the reminder; we derive:
$$S_0=\Big\lfloor{{\big((2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod 2^{31}\big)+2^{31}\cdot K}\over a}\Big\rfloor$$


Therefore the following outputs the possible values for $X_0$ given the first two outputs $R_0$ and $R_1$, by trying all possible values of $K$:

  • Compute $T=(2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod 2^{31}$
    Notice that $T+2^{31}\cdot K=a\cdot S_0+r$ with $S_0<2^{16}$ and $r<2^{16}$
  • For $K$ from $0$ to $\big\lfloor\big((2^{16}-1)\cdot(a+1)-T\big)/2^{31}\big\rfloor$
    • If $\big((T+2^{31}\cdot K)\bmod a\big)<2^{16}$
      • Output $\big\lfloor(T+2^{31}\cdot K)/a\big\rfloor+2^{16}\cdot R_0$

The quantity $(T+2^{31}\cdot K)\bmod a$ tested in the loop is $r$, hence the test's bound. $\big\lfloor(T+2^{31}\cdot K)/a\big\rfloor$ is $S_0$. What's output is a candidate $X_0$, since $S_n=X_n-2^{16}\cdot R_n$. It is easy to filter these candidates using $R_2$.

This works for any $a\ge2^{16}$. With the parameters at hand, the loop is performed at most $7$ times, with typically $2\pm1$ outputs. I can run the algorithm with pen and paper, and some would be able to perform it mentally.

The method works regardless of the bit size $x$ of $X$, an output $R$ with $x/2$ high bits (give or take a constant), and $a$ big enough that the attack works: the cost is $O(x^2\cdot a/2^{x/2})$ using standard arithmetic algorithms. I think we could avoid most values of $K$ that do not pass the test, bringing the cost to $O(x^2)$ even for huge $a$ (and quoting Bruce Schneier attributing that saying to the NSA: "Attacks always get better; they never get worse").

When $a$ is too small to carry that attack, a trivial attack applies, recovering the state $X_0$ from most to least significant bits, at a rate of about $\log_2a$ additional bits for each additional $R_n$.

Improvement: if $a$ is small or otherwise unfavorable, we can use $R_j$ rather than $R_1$, replacing $a$ with $a_j=a^j\bmod2^{31}$ for some $j>1$ giving a favorable $a_j$ (a small maximum $K$), and replacing $b$ with $b_j=b\cdot(1+a+\dots+a^{j-1})\bmod2^{31}$. That allows to efficiently tackle much larger modulus!


Generally speaking, Linear Congruential Generators are very poor from a cryptographic standpoint, even when some post-processing is applied; see this answer for an example.

More often than not, Linear Congruential Generators are not even suitable for simulation purposes. To demonstrate this to the incredulous, generate a million values using the LCG in the question; count how many times each of the 32768 values is reached; and either compute the standard deviation of that, or graph the counts sorted by increasing values; repeat with a sound RNG, and compare.

$\endgroup$
  • 2
    $\begingroup$ Could you explain the math behind your equations, I'm a little confused how the $S_1$ turned into $2^{16} - 1$ $\endgroup$ – Vishwa Iyer Jul 9 '17 at 20:47
  • 1
    $\begingroup$ @fgrieu I think the part that is unclear (for me at least) is how you got to the formula after "Using that S1<a, we derive" . There, it looks like you just replaced S1 with S^16 - 1? $\endgroup$ – bennofs Jul 9 '17 at 23:23
  • 1
    $\begingroup$ @bennofs: : you (and Vishwa Iyer) are absolutely right. Further, I was using a potentially different $K$ before and after that second "We derive". This is hopefully rigorous now. Thanks for pinpointing the issue! $\endgroup$ – fgrieu Jul 10 '17 at 4:54
  • $\begingroup$ @fgrieu I understand the math a little better, so from my understand, you defined $r$ just to simply the equation better? And could you explain how you got the ranges for $K$ with your loop? And when you were deriving $S_0$ where did the $r$ go? Did it disappear because floor($r$/$a$) = $0$? $\endgroup$ – Vishwa Iyer Jul 10 '17 at 12:24
  • $\begingroup$ @fgrieu sorry i wasn't clear on my question. I'm talking about the equation where you solved for $S_0$, where did $r$ go? Also, shouldn't $K = \text{floor}(a \cdot S_0 + r - T)/2^{31}$, or am I missing something? I don't know where the $2^{16} \cdot a - 1$ came from. $\endgroup$ – Vishwa Iyer Jul 10 '17 at 13:46
4
$\begingroup$

You already answered your own question: given the output from 2 calls to the rand() function and $2^{16}$ steps of computation, you can recover the internal state completely, simply by brute-forcing the parts of the state that you are not aware of. That is a break.

You say it's "hardly a break", but that is too-narrow thinking. A break is a break; anything that suffices to predict future outputs of the generator is a break. It does break Window's rand() implementation.

Maybe you are wondering whether some other generator that looks sorta like Window's rand(), but is not Window's rand(), would be breakable. Well, that's a different question. The answer to that will depend upon what specifically you have in mind -- but regardless, at that point we're not talking about Window's rand() any longer. The break you've got is already good enough to show that Window's rand() should not be used for cryptographic purposes. It's plenty adequate to show how broken Window's rand() is.

If this doesn't count as "good enough" of an attack, then probably your question isn't really a question about cryptography, but something else -- because for cryptographic purposes, this is a valid break.


That said, there is a slight improvement on the attack. I believe you can build a meet-in-the-middle attack that needs about $2 \times 2^8$ steps of computation and 2 outputs from rand(), and that infers its internal state.

Here's the idea. Suppose you observe the top 16 bits of $X_0$. Now write $X_0 = c + 2^8 d + e$, where $0 \le d,e < 2^8$ and $c$ is a known constant. Notice that this means

$$X_1 = (214013 c + 2531011) + 2^8 \cdot 214013 d + 214013 e.$$

The first part ($214013 c + 2531011$) is a known constant, so we have

$$X_1 = \text{known} + \text{known} \times d + \text{known} \times e.$$

or in other words,

$$X_1 - \text{known} - \text{known} \times d = \text{known} \times e.$$

Now we're set up to do a meet-in-the-middle attack. We know the top 16 bits of $X_1$. We can enumerate all $2^8$ possibilities for $e$, calculate the resulting top 16 bits of the right-hand side, and store them in a table. We can then enumerate all $2^8$ possibilities for $d$, calculate the resulting top 16 bits of the left-hand side, and look it up in the table to check for a match. When we guess them right, we should find a match.

$\endgroup$
  • $\begingroup$ I'm looking to show that rand() is unsuitable for nearly any purpose, rather than just cryptographic purposes. And I'm looking for 2 things here: either a better attack requiring less computation (preferably to be done with just a graphical calculator), or some reference recommendations for breaking LCG's with partial output. And my "break" doesn't work anymore if we'd change state to uint64_t (and change the shift to 48). $\endgroup$ – orlp Sep 28 '13 at 6:32
  • $\begingroup$ @nightcracker, in that case, it sounds like your question is not about cryptography per se, so I don't think it is on-topic here. The cryptographic aspect of the question has been answered.... $\endgroup$ – D.W. Sep 28 '13 at 6:52
  • 1
    $\begingroup$ How so? The existence of a $2^{16}$ attack does not mean all further research on attacks should be stopped - especially considering that the internal state is only twice as large as that. $\endgroup$ – orlp Sep 28 '13 at 8:24
  • 1
    $\begingroup$ @nightcracker, I think it does mean that. A $2^{16}$ attack means the generator is broken. It means absolutely no one should use the generator. At that point, who cares whether there is a $2^8$ attack? How will that affect your decision-making? If news of a $2^8$ attack will cause you to avoid the generator, when news of a $2^{16}$ attack wouldn't, then there is something wrong with your decision-making. P.S. If your question is about other generators like the Windows rand(), but different (say with larger parameters), then that's a different question: post a new question. $\endgroup$ – D.W. Sep 28 '13 at 17:05
3
$\begingroup$

Related to "show some colleague programmers"

You could code and use a smaller 8-bit rng to show them a "mini version" of C's rand. The period will be shorter and therefore more obvious… you can print the complete period (256 bytes) on screen. Seeding the rng in +1 steps and printing the next 256 bytes will show them they're actually only rotating a sequence of 256 predicable bytes. After that, it shouldn't be a huge step to convince them that bigger numbers don't fix the predictability problem. Also, the 8-bit version provides a playground to build upon towards attacking MSVC's implementation.

Related to "references that attack fixed LCG"

There is a paper that might be interesting for you to take a look at:

It includes a C code example which allows the calculation of the seed used in an LCG.

Related to "graphical calculator"

Well, it is probably not what you were thinking of as it doesn't attack any LCG, but there is a piece of software that allows to experiment with the parameters of an LCG and which visualizes the subtle correlations between the pseudo-random numbers successively created by an LCG.

screenshot of the software

You can grab either the English or the German version at
http://www.vias.org/simulations/simusoft_lincong.html

$\endgroup$

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.