Cryptography
stream-cipher lfsr
Updated Fri, 20 May 2022 04:26:15 GMT

Determine LFSR phase quickly?


I know it's possible with work backwards from the output bits of an LFSR to determine its feedback polynomial in a O(n) fashion. I'm also curious if, given an LFSR state and polynomial, is it possible to quickly work out how far the LFSR state is from a given epoch state (eg: the all-ones state). The only sure-fire method I know of is to run the LFSR forwards/backwards until the state is the epoch state and keep track with a counter.

Edit: thinking about this more, this would be equivalent to solving $S = M^NE$ quickly $N$, where $S$ is your current state, $E$ is the epoch state and $M$ is the companion matrix of the LFSR. Anyone have a fast solution to the discrete logarithm problem in the ring of $KxK$ $GF(2)$ matrices?




Solution

Well, one way to look at this is to notice that, if the feedback polynomial is prime, then the result of starting with state $E$, and then stepping the LFSR forward $N$ steps is the value $2^N \cdot E$, where we do the computation in $GF(2^K)$, using the polynomial representation (with the feedback polynomial being the polynomial). In addition, I believe that if the feedback polynomial is not prime, then it is possible to factor that polynomial into its primes, solve the equivalent solution modulo each prime factor, and then recombine them.

So, the solving the problem of finding $N$ is equivalent to solving $S = 2^N \cdot E$ in $GF(2^K)$, or in other words, $S/E = 2^N$; that is, this problem can be reduced to solving a discrete log problem in $GF(2^K)$.

What does that rewording of the problem buy us? Well, it turns out that there are recent results in this area; this paper shows us how this problem can be solved in "quasi-polynomial" time (by which they mean $K^{O(\log K)}$; technically supra-polynomial, but just barely); that paper tells us how to do discrete logs quickly over fields of small characteristic, and a characteristic of 2 is as small as it gets.





Comments (5)

  • +0 – Very interesting, thanks. I hadn't though about taking the entire LFSR state as an element in a larger field, but that makes perfect sense. — Jul 02, 2014 at 21:26  
  • +0 – I still wonder what the best (known) algorithm is (it seems possible that an algorithm for characteristic 2 beats a general algorithm for small characteristics); its runtime and memory requirements; and how much its runtime depends on $P$ (is it harder for a random primitive $P$ than e.g. the primitive $P$ with lowest possible $P(2)$? — Jul 03, 2014 at 11:55  
  • +0 – @fgrieu: the $GF(2^k)$ argument can be used to address the later question; for two different polynomial representations of $GF(2^k)$, there is a linear mapping that preserves the field structure. Hence, we can use that mapping to map from the "hard" representation to the "easy" one, and solve it there. Now, the constant "2" in the hard representation will (probably) map to some other constant; if the easy solution depends on the base 2, we just solve two discrete logs in the easy representation. — Jul 03, 2014 at 14:33  
  • +0 – If the primitive $P$ of degree $k$ of the generator is not sparse or otherwise unfit, I trust you that we can massage $S/E\equiv x^N\pmod P$ into $A\equiv B^N\pmod Q$, where $Q$ is any primitive polynomial we see fit, and polynomials $A$ and $B$ somehow follow (I fail to tell exactly how, though). We can then solve $A\equiv x^{N_A}\pmod Q$ and $B\equiv x^{N_B}\pmod Q$, and then have $N\equiv N_A-N_B\pmod{2^k-1}$. So at worse, the cost for arbitrary $P$ is twice the cost for any $Q$ we see fit, plus whatever the cost of changing from $S/E\equiv x^N\pmod P$ to $A\equiv B^N\pmod Q$ is. — Jul 03, 2014 at 16:12  
  • +0 – @fgrieu: you've got it mostly; however there's one point you missed. When we're switching between $GF(2^k)$ representations, we're not actually changing anything essential in the equation. Instead, a "representation" is just a way of mapping between the elements of the abstract field to bit patterns; and yes, it is fun and easy to convert the bit pattern of one representation into the exact same field element in a different representation. Also, it doesn't matter of the generator is sparse or not; as long as it is primitive, the argument works. — Jul 03, 2014 at 18:59  


External Links

External links referenced by this document: