Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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