# LFSR dynamic mutation

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?

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.

• What about recovering the k[] tab knowing values of state, C and i?
– qwer
Jun 2 '12 at 13:39
• 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].
– fgrieu
Jun 2 '12 at 15:28
• 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?
– qwer
Jun 2 '12 at 16:38
• How to recover k[], if C<=L?
– qwer
Jun 4 '12 at 23:13