In normal LFSR, the state is a function of the initial seed, taps positions and time, nothing else. I've seen a modification of LFSR that works like this:

TAPS = const
MASK = (1<<L)-1 #L=bitlength of state

def parity(x):
    return (number of ones in x)&1

def tick(state):
    b = parity(state & TAPS)    
    return (state<<1 | b) & MASK

while True:
    i = 0
    k = [...] #elements smaller than bitlength of state
    while True:
        state = state ^ (1<<k[i%C]) #C<=length(k)
        state = tick(state)
        i += 1

I can't find any mention of that variant in the literature. Does it have a name, or is it completely custom?


1 Answer 1


I have never met this, but it can still be analyzed in the framework of Linear Feedback Shift Registers, and is unsafe as a key stream generator.

I'll assume that $2^{\mathtt L-1}\le \mathtt{TAPS}<2^\mathtt L$. The operation state = tick(state) then is the normal operation for a Fibonacci LFSR with the binary polynomial $Q(x)$ of degree $\mathtt L$ defined by the bits set in the integer $2\cdot\mathtt{TAPS}+1$.

The addition of state = state ^ (1<<k[i%C]) turns that into a different beast, in particular the state now includes $\mathtt i\pmod{\mathtt C}$, sort of extending the state from $\mathtt L$ bits to $\mathtt L+\log_2\mathtt C$ bits.

However, the transformation corresponding to $\mathtt C$ steps leaves $\mathtt i\bmod \mathtt C$ unchanged, and is a linear transformation of $\mathtt{state}$. For moderate $\mathtt C\cdot\mathtt L$, blindly applying a good tool based on the Berlekamp–Massey algorithm on known output will allow prediction of the rest, without any description of the system.

Update: At step $\mathtt i$, $\mathtt{state_i}$ has bits sets as per the coefficients of the remainder of the division by polynomial some appropriate reduction using $Q(x)$ (defined above) of the sum of two polynomials:

  • $x^\mathtt i\cdot S(x)$ where $S(x)$ corresponds to bits set in $\mathtt{state_0}$, as would be the case for a normal LFSR;
  • $\sum_{\mathtt j=0}^{\mathtt i-1}x^{\mathtt{k[}\mathtt j\bmod\mathtt{C]}+\mathtt i-1-\mathtt j}$, corresponding to the effect of state = state ^ (1<<k[i%C]).

To answer an additional question: in general, $\mathtt{k[]}$ can not be reconstructed from $(\mathtt{TAPS}, \mathtt L, \mathtt C, \mathtt{state_0})$ and a single $(\mathtt i, \mathtt{state_i})$. When $\mathtt C>\mathtt L$ an amount-of-information argument shows that we do not have enough input. And even for $\mathtt C\le \mathtt L$ there can often be several solutions.

  • $\begingroup$ What about recovering the k[] tab knowing values of state, C and i? $\endgroup$
    – qwer
    Commented Jun 2, 2012 at 13:39
  • $\begingroup$ Knowledge of TAPS and complete values of state at the end of two consecutive steps gives 1<<k[i%C] used in the second step (hint: tick is an easily reversed mapping), which allows to confirm that TAPS is really known, and recover k[i%C]. $\endgroup$
    – fgrieu
    Commented Jun 2, 2012 at 15:28
  • $\begingroup$ I meant values as in three variables: state, C, i, not all history of states. What if only the first and last states are available? $\endgroup$
    – qwer
    Commented Jun 2, 2012 at 16:38
  • $\begingroup$ How to recover k[], if C<=L? $\endgroup$
    – qwer
    Commented Jun 4, 2012 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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