Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table of the AND gate that you will end up with a string consisting of (approximately) 75% zeroes and 25% ones with the ones being psuedorandomly distributed , so to speak, in a string of zeroes. My question is given any number of observed output bits in the sequence , is it possible to predict WHEN the AND gate will output a one ?


Yup, it's possible. This generator is easily broken, as each output bit has degree only two. There's an efficient algorithm that, given the first $n$ bits of output from the generator, will let you predict all the future outputs from the generator with 100% accuracy.

Let $x_1,\dots,x_{128}$ denote the initial state of the first LFSR and $x_{129},\dots,x_{256}$ denote the initial state of the second LFSR. Then every bit produced by your generator can be expressed as a multivariate polynomial over $x_1,\dots,x_{256}$. The degree of this polynomial is two: each monomial is of the form $x_i x_j$ or $x_i$. Here were are working in the finite field $GF(2)$, i.e., working modulo two. In this field, the AND of $x_i$ and $x_j$ is the term $x_i x_j$ (the product). It follows that the output of the generator is a polynomial of degree two. (Why? Because at any given time, the output from the first LFSR is a linear function of the initial state, i.e., a polynomial $p_1(x_1,\dots,x_{128})$ of degree one; and similarly the output from the second LFSR is a linear function, i.e., a polynomial $p_2(x_{129},\dots,x_{256})$ of degree one. Now the output of the generator is the AND of these two, i.e., it is the product $p_1(x_1,\dots,x_{128}) p_2(x_{129},\dots,x_{256})$, which is a polynomial of degree two.)

So, if you're given $n$ bits of output from this generator, you receive $n$ quadratic equations in the 256 unknowns $x_1,\dots,x_{256}$. If $n$ is large enough, there are standard techniques for solving this system of equations, which gives you $x_1,\dots,x_{256}$. At that point you know the initial state of both LFSRs, so you can predict the future output of the generator for all time -- and the scheme is broken.

How do you solve the system of linear equations? One simple approach is linearization: if $n > 256^2/2$, then you can replace each monomial $x_i x_j$ by a new unknown $y_{i,j}$; then you get a new system of $n$ linear equations in roughly $C(256,2)$ unknowns, which can be efficiently solved using Gaussian elimination. If $n$ is smaller than that but still significantly larger than 256, you can use relinearization, which is efficient as long as $n$ is large enough. (You can also try SAT solvers, Groebner basis algorithms, or other methods, though these are not polynomial-time in general.) For more details on relinearization, see https://crypto.stackexchange.com/a/3736/351.

To avoid this problem, I suggest using a cryptographic-strength pseudorandom generator -- also known in the cryptographic literature as a "stream cipher". For instance, you could use AES in CTR mode (counter mode). This will provide very strong resistance against prediction of future outputs, as long as the AES key is chosen at random and is hard to guess.

By the way, the Cryptography Stack Exchange site has many experts who are knowledgeable about this sort of topic, so you might be interested in checking out the material that's available over there.

  • $\begingroup$ I'm not seeing how the output can be described by a system of linear equations, the AND function of two variables is bent which means maximally nonlinear or the farthest distance to an affine (linear) function. $\endgroup$ Mar 29 '15 at 21:38
  • $\begingroup$ @WilliamHird, I've edited the second paragraph to explain why the output can be described by a system of quadratic equations (not linear -- quadratic, i.e., degree two) in $x_1,\dots,x_{256}$. $\endgroup$
    – D.W.
    Mar 29 '15 at 22:40
  • $\begingroup$ Nice answer. Why do textbooks say that the AND ( OR, NAND, NOR) functions are irreversible computations, you can't recover the input from the output because information is lost. You just showed that this is not true, what am I missing? $\endgroup$ Mar 30 '15 at 2:39
  • 1
    $\begingroup$ @WilliamHird, there is no contradiction. If you're given $a \land c$, you can't necessarily uniquely recover $a$. But if you're given $a \land c$, $b \land d$, $a \land d$, $b \land c$, $(a\oplus b) \land c$, $a \land (b\oplus c)$, $(a \oplus 1) \land c$, $b \land (d \oplus 1)$, etc. (all combinations of the AND of a linear function of $a,b$ and a linear function of $c,d$), now you can uniquely recover $a,b,c,d$ -- you have a lot of information about $a,b,c,d$. Breaking your cipher is more analogous to the latter situation than the former. $\endgroup$
    – D.W.
    Mar 30 '15 at 3:28

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.