How broken is a xor of two LCGs?

Question

Suppose we define a PRG as the xor of two LCGs modulo a 64-bit prime: something like the following Python code.

p = 14692456042302986707
alpha, beta = 1416483285059710267, 1922202445720274864
gamma, delta = 8868330555542893802, 9736145736144160231

def prg(x, y):
    while True:
        x = (alpha * x + beta) % p
        y = (gamma * y + delta) % p
        yield (x ^ y)

To express it more mathematically, starting from a seed $(x_0,y_0)$ the outputs are $z_1, z_2, \ldots$, where

$x_{i+1}=\alpha x_i+\beta\ (\mathrm{mod}\ p)$,
$y_{i+1}=\gamma y_i+\delta\ (\mathrm{mod}\ p)$,
$z_i=x_i\oplus y_i$,

with constants $p=14692456042302986707$, $\alpha=1416483285059710267$, $\beta=1922202445720274864$, $\gamma=8868330555542893802$, and $\delta=9736145736144160231$.

How broken is this construction, in the sense of being predictable given some output? Of course it can be broken in at most p iterations given two consecutive outputs (guess x, derive y from the first output, and check against the second). But is it more broken than that? Can it be predicted in significantly fewer than p iterations given some amount of output? Is there anything in the literature about attacking this construction? It is surely simple enough that it has been considered.

Please forgive this beginner’s question. I have not been able to find an answer online or in the literature, searching under all the search terms I can think of. Nevertheless I suspect the answer is well-known, hence I am asking here.

I should emphasise that I am not proposing to use this construction for anything security-sensitive (nor indeed for anything at all). I am only curious about crypto fundamentals, and this is the simplest LCG-based construction that I cannot easily break, though I do of course suspect it to be breakable.

---

Update: In response to Thomas’s request for a smaller variant to analyse, here are some 24-bit constants:

$p = 14435129$, $\alpha = 881969$, $\beta=8713582$, $\gamma=12608927$, $\delta=9284034$.

Here $p$ was selected as a random 24-bit prime, then the others as random numbers less than $p$.

Of course this reduced version can be brute-forced very easily, but the question remains of whether there is an even faster attack.

Answer 1

Distinguishing attack. How broken is it? It is broken. As fgrieu notes, the high bit is highly biased. In other words, the high bit is fairly predictable. This is enough to distinguish the output of this generator from a truly random bitstream. That means the stream cipher is broken: that's the definition of what it means for a stream cipher to be broken. The distinguishing attack requires observing a few outputs and requires very little computation, so it is much faster than brute force.

Of course, this is a distinguishing attack, not a state recovery attack. Nonetheless, that's still a valid break.

---

State recovery attack. There is also a state-recovery attack. For instance, if you can observe $2^{30}$ outputs from the generator, then with about $2^{44}$ steps of computation you can recover the initial state of the stream cipher (and thus predict all of its outputs). The running time of this attack is faster than brute force.

The attack chains together several observations:

• Correlation to the MSB of a single LCG. Notice that the most significant bit (MSB) of $z_i$ (the $i$th output from the stream cipher) is strongly correlated to the MSB of $x_i$ (the $i$th output from the first LCG). In other words, $\Pr[z_i=x_i]$ is quite a bit larger than $1/2$: for instance, with your parameters for the 64-bit generator, $\Pr[z_i=x_i]\approx 0.8$. This happens because the MSB of $y_i$ is more likely to be 0 than to be 1.

  The consequence is that, if we can observe $2^{30}$ outputs from the stream cipher, then we observe a sequence that is highly correlated to the MSBs of $2^{30}$ outputs from the first LCG.

• Outputs from the LCG are a linear function of the initial state. Notice that $x_i$, the $i$th output from the first LCG, is related to the initial state $x_0$ of that LCG by a simple linear relationship:

  $$x_i = c_i x_0 + d_i \bmod p,$$

  where $c_i,d_i$ are some known constants that depends only upon the (public) parameters of the LCG but not on the key or state. (In particular, $c_i=\alpha^i \bmod p$ and $d_i = \beta (\alpha^i-1)/(\alpha-1) \bmod p$.)

  This means that the state of the first LCG at any point in time can be related to its initial state through a simple linear relationship. This will be useful in the remainder of the attack.

• Sometimes, the MSB of the output of the 1st LCG can be predicted given only partial knowledge of the initial state. Suppose we know the top 44 bits of the initial state $x_0$ (i.e., we know all but the bottom 20 bits of $x_0$). Then there are some time steps where we can predict the MSB of the output completely, given this information, even though we don't know the bottom 20 bits of the initial state.

  In particular, consider any time step $i$ where $c_i$ satisfies $c_i < p/2^{22}$. Then we can predict the MSB of $c_i x_0 + d_i \bmod p$ given knowledge the top 44 bits of $x_0$, and our prediction will be right most of the time (about $7/8$ of the time). This means we can predict the MSB of $x_i$ (the MSB of the $i$th output) and we'll be right about $7/8$ of the time.

  It is easy to predict which time steps satisfy this condition: since all of the $c_i$'s are publicly known, we can easily enumerate which values of $i$ satisfy the condition $c_i < p/2^{22}$. Among the first $2^{30}$ time steps, we expect to find about $2^8$ good time steps that satisfy the condition, i.e., about $2^8$ time steps where we can predict the MSB of the output of the first LCG, given a guess at the top 44 bits of $x_0$.

• We can verify a partial guess at the initial state of the 1st LCG. Suppose we have a guess at the top 44 bits of $x_0$ (at the top 44 bits of the initial state of the 1st LCG). Then the above observations give us a way to verify whether this guess is correct. We focus on the $2^8$ good time steps where $c_i$ is small; we'll analyze the outputs from the stream cipher at those $2^8$ offsets (the rest of the outputs from the stream cipher are simply ignored in this analysis). Notice that the MSB of each of those outputs from the stream cipher are highly correlated with the MSB of the corresponding output from the first LCG (the MSB of $x_i$). Now given our guess at the top 44 bits of $x_0$, we can produce excellent predictions for the MSB of $x_i$ at each of those $2^8$ time steps. So, we can check whether the MSB of the outputs from the stream cipher appears to be well-correlated to the predictions for the MSB of the corresponding $x_i$'s. If there is a good correlation, then we infer that this partial guess at $x_0$ is (probably) correct. If there is no apparent correlation, then we can conclude that this guess is probably wrong.

This yields an attack on the stream cipher that is faster than brute force. We identify the $2^8$ "good" time steps (where $c_i$ is small) in advance, and focus on analyzing those outputs from the stream cipher. We enumerate all $2^{44}$ guesses for the top 44 bits of $x_0$, and use the observation above to verify which of those guesses appear to be correct. For each guess that passes the above filter, we then exhaustively enumerate all possibilities for the remaining 20 bits of $x_0$ and then infer $y_0$. The test described above should eliminate almost all of the incorrect guesses at the top 44 bits of $x_0$, so I expect the total running time to be approximately $2^{44}$ steps of computation.

I have not tried to finely optimize the running time of this attack, and my running time estimates are pretty crude, so a more careful analysis would probably give a better estimate (I would not be surprised if my estimates are off by an order of magnitude). Nonetheless, it seems quite clear that this will be significantly faster than the brute-force attack you described; that attack requires $2^{64}$ steps of computation, and this is significantly faster.

Related literature. You might enjoy reading about the "Hidden Number Problem", which is the following: given $\text{MSB}(x_i k \bmod p)$ for many random, known values of $x_i$, find $k$. That's closely related to a key step of my attack above, though my attack above has to work even in the presence of noise (on the other hand, my attack above is not polynomial-time; it is merely better than brute-force). Past work on the Hidden Number Problem has been used, for instance, to attack certain implementations of DSA.

---

Performance. It occurs to me that, implicit in your question, is the follow-up question: "If this can't be broken, why isn't it used?" The answer to that is: this cipher is going to offer poor performance.

Let's break it down. If we want 128-bit security (which is the standard of comparison right now), we're going to need to use two 128-bit primes. If we want to eliminate the distinguishing attack, we're going to need to discard some of the most significant bits; so we might get 80-100 bits of pseudorandom output per iteration of the stream cipher.

Now let's look at how long each iteration of the stream cipher will take, with these parameters. Well, we have to do two 128x128->256 multiply operations, and two 256->128 modular reductions. No computer chip offers a "multiply two 128-bit numbers" instruction; if you build it out of 32x32->64 multiplies, you're going to need to do 16 of those per 128x128->256 multiply, or 32 of the 32x32->64 multiply instructions per iteration. The modular reduction is even worse; I'm guessing that might take something like 100 instructions per reduction. So we're looking at maybe 250 instructions per iteration of the generator, or maybe 25-30 instructions per byte of output. This is a very rough estimate, and I haven't benchmarked it, but I think this is enough to make clear that this generator is not going to be competitive with state-of-the-art stream ciphers, even if there are no clever shortcut attacks.

Answer 2

Here is a pretty dumb cipher-text only attack.

Suppose that either x or y is zero. Then the output is the XOR of beta or delta with the result of the other equation.

Because you have two generators working together, you've actually doubled the chance of this happening. When this happens you can just XOR off the constant and then directly solve for half of the internal state. You can run this attack on any ciphertext you have and hope you get lucky. You do this by just computing what the result would be had this event had occurred for every byte of the cipher-text.

Next, you could then look for a case where the output from the generator is zero. When this happens the two halves must be equal to each other.

You then compare your calculations done above with this event and try to get them to line up. If you have enough cipher-text you'll get it a hit and you've solved the internal state.

This is a pretty horrible attack but I'd expect to work much faster than brute forcing both values ($2^{128}$ work) and it'd work with high probability with about than $2^{63}$ iterations worth of ciphertext.

I'm very much an amateur, so if I can find an attack like this a real cryptographer could probably completely shred this construction.

Answer 3

Here a few thoughts:

If the yielded number is "small", then x and y are close, too (since they are equal in the most significant bits).

Let's assume the RNG produces a stream of ciphers, and we look for two consecutive "small" values, where the difference is under some threshold $T$. Then we know for these x and y values: $$|x-y| < T \text{ (mod p )}$$ $$|(\alpha x + \beta) - (\gamma y + \delta)| < T \text{ ( mod p)}$$

It should be fairly easy to solve this in reasonable time, once you got rid of the constants in this system.