LFSR dynamic mutation

Question

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?

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.