11
$\begingroup$

Linear Feedback Shift Registers (LFSRs) can be excellent (efficient, fast, and with good statistial properties) pseudo-random generators. Many stream ciphers are based on LFSRs and one of the possible designs of such stream ciphers is combining outputs of $m$ LFSRs as input of a boolean function $f:GF(2)^m\rightarrow GF(2)$. This last function has to be carefully selected.

My question is a rather elementary one. I understand that using one LFSR to produce the keystream is not appropriate as one can create the whole keystream by knowing a tiny fraction of it: if the tap positions of a length $n$ LFSR are known, one needs $n$ bits to determine the entire keystrem sequence, and if they are not known, one needs $2n$ bits (by using the Berlekamp-Massey algorithm to find out the tap positions). However, why do we need a non-linear combination of LFSRs (among all sorts of other requirements)? What would be the problem of getting a number of LFSRs with appropriate lengths and tap positions and XOR together their output to produce the keystream?

Improve this question
$\endgroup$
4
  • $\begingroup$ Maybe these lecture notes will help... $\endgroup$
    – rphv
    May 10, 2013 at 21:39
  • 3
    $\begingroup$ The edit by rphv has many ambiguities in it. A linear feedback shift register (LFSR) of length $n$ does not necessarily generate a sequence of period $2^n-1$. The period could be much smaller and could depend on the initial loading and the feedback polynomial, that is, for some feedback polynomials, one can get sequences of different periods by changing the initial loading. It is true that the maximum period is $2^n-1$ and occurs when the feedback polynomial is a primitive polynomial in the sense that coding theorists use the term (and the initial loading is all-zeroes). $\endgroup$
    – Dilip Sarwate
    May 11, 2013 at 18:49
  • $\begingroup$ @rphv I think there is another issue about the edit: one needs $2n$ bits if the tap positions are not known. If they are known, one needs $n$ bits. $\endgroup$
    – geo909
    May 11, 2013 at 19:20
  • $\begingroup$ In my previous comment, the last clause, which appears in parentheses, should read "and the initial loading is not all-zeroes" The word not was inadvertently left out, and it is now too late to edit the comment. $\endgroup$
    – Dilip Sarwate
    May 11, 2013 at 19:38

2 Answers 2

Reset to default
11
$\begingroup$

If there was no non-linearity, then every bit of keystream output would be a (known) linear function of the unknown key bits. Consequently, in a known-plaintext attack scenario, each bit of known keystream output would allow us to write a linear equation on the unknown key bits. If we have a 128-bit key, there are 128 boolean unknowns (variables), so once we have 128 bits of known keystream, we have 128 linear equations in 128 unknowns. At that point it becomes easy to solve for the original key bits using standard methods for solving a system of linear equations (e.g., Gaussian elimination). Thus, an attacker could recover the key from 128 bits of known output from the stream cipher, which is a total break of the stream cipher.

The only way to prevent this kind of attack is to make sure that the cipher contains non-linear elements. To prevent other related but fancier attacks (e.g., linear cryptanalysis), one also needs sufficient non-linearity in the stream cipher.

Clarification: To keep it simple, my answer above assumes that the feedback polynomial for the LFSRs is known. The attack does generalize to the case where the feedback polynomials are not known (you need twice as much known keystream output); in that case, the attack gets a bit more complicated, but the basic idea still applies. I tried to keep it simple to help you understand the intuition without getting bogged down in mathematics, but if you want to see more details about the case where the feedback polynomials are not known, Dilip Sarwate has an excellent answer that explains that case more thoroughly.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You're right! By the reccurent nature of the LFSRs, every output bit of every LFSR can be expressed as a linear combination of the initial state! Then we end up with a system of linear equations and we can perform Gaussian elimination. $\endgroup$
    – geo909
    May 11, 2013 at 19:33
  • 3
    $\begingroup$ This answer is incorrect in the details. If one knows that the sequence is generated by an LFSR of length $128$ bits, then there are $128$ coefficients of the feedback polynomial (a.k.a. tap locations) that need to be determined, and $128$ bits of the sequence (exactly the initial loading of the LFSR) are not enough to determine these feedback coefficients; you need $256$ bits. Take a simpler case: for $n=3$, we have (continued in next comment) $\endgroup$
    – Dilip Sarwate
    May 12, 2013 at 1:59
  • 1
    $\begingroup$ (continued from previous comment) an initial load $(a_2,a_1,a_0)$ and feedback taps $f_1,f_2,f_3$ where $$\begin{align}a_3&=a_2f_1+a_1f_2+a_0f_3\\a_4&=a_3f_1+a_2f_2+a_1f_3\\a_5&=a_4f_1+a_3f_2+a_2f_3\end{align}$$ so that we need $6$ bits of the sequence, not $3$, to get $3$ linear equations to solve for $f_1,f_2,f_3$. This is the same as the amount of information needed by the Berlekamp-Massey algorithm, but the Berlekamp-Massey algorithm will also find the shortest LFSR that generates any arbitrarily $6$-bit sequence, not just for the sequences known to be generated by a $n$-bit LFSR $\endgroup$
    – Dilip Sarwate
    May 12, 2013 at 2:10
  • $\begingroup$ @DilipSarwate, absolutely, great point! My answer keeps it simple and assumes the feedback polynomial / tap locations are known. Yes, if the feedback polynomial is not known, then twice as many bits of known keystream are needed, and more sophisticated methods are needed. Thank you for pointing this out! $\endgroup$
    – D.W.
    May 12, 2013 at 4:26
12
$\begingroup$

The Berlekamp-Massey algorithm is an iterative method for finding the shortest LFSR that can generate a given sequence of bits. The given sequence might or might not be generated by an LFSR: the Berlekamp-Massey algorithm does not care. It just finds the shortest LFSR that can generate the given sequence, and if the sequence has been generated by an LFSR of length $n$, then the Berlekamp-Massey algorithm is guaranteed to find this LFSR after examining no more than $2n$ bits of the sequence. A simplistic description of what happens is as follows. After the algorithm has found the shortest LFSR that generates the first $k$ bits of the sequence, it examines the $(k+1)$-th bit of the sequence. If this $(k+1)$-th bit of the sequence matches the $(k+1)$-th bit of the output of the current LFSR, the LFSR is accepted as the one that generates the first $k+1$ bits. If not, the LFSR is updated so that the new, typically longer, LFSR generates the first $k+1$ bits. As stated earlier, if the sequence in question was in fact generated by an LFSR of length $n$, then the Berlekamp-Massey algorithm is guaranteed to find this LFSR by the time it has examined $2n$ bits of the sequence. How does the algorithm know that it is done? Well, it doesn't, but after the correct LFSR has been found, the $(2n+1)$-th, the $(2n+2)$-th, the $(2n+3)$-th, $\ldots$ bits of the given sequence match the corresponding outputs of the LFSR and so the Berlekamp-Massey algorithm does not update the $n$-bit LFSR it has found.

What does all this have to do with the question asked? Well, the (bit-by-bit XOR) sum of the outputs of the various LFSRs is a sequence that is generated by a longer LFSR (typically, the length of the longer LFSR is the sum of the lengths of the LFSRs whose outputs were summed). So, the cryptographic security is not significantly larger. What is needed is some way of combining the constituent LFSR outputs so that the resulting sequence has linear complexity much larger that the sum of the LFSR lengths. The linear complexity of a sequence is defined as the length of the shortest LFSR that can generate the sequence. What we want is a sequence that has high linear complexity but which can be generated easily as a nonlinear function of the outputs of short LFSRs. The legitimate users of the system can encipher and decipher easily, but a cryptanalyst attempting to break the system via a known plaintext attack has to either figure out the nonlinear function (and the constituent LFSRs) which is not easy to do or attempt a Berlekamp-Massey algorithm attack which may fail because not enough bits of the sequence can be determined via a known plaintext attack to find the shortest LFSR that generates the sequence.

Improve this answer
$\endgroup$
7
  • $\begingroup$ So, that's another good reason not to use combinations of LFSRs.. After reading your answer I looked a bit more carfully and confirmed that if the combiner function is $f$ and the lengths of the $m$ LFSRs are $L_1,\cdots,L_m$, then the linear complexity of the output sequence is $f(L_1,\cdots,L_m)$; in our case that's the sum of the $L_i's$ as you said. So, for lengths that add up to 128 (so we have a 128-bit key), one needs only $2\times 128=256$ bits of the keystream sequence and the Berlekamp-Massey algorithm to break the system. $\endgroup$
    – geo909
    May 11, 2013 at 19:35
  • $\begingroup$ It seems that ideally one would like linear complexity almost equal to the period of the keystream (and of course, a large period) $\endgroup$
    – geo909
    May 11, 2013 at 19:41
  • 1
    $\begingroup$ @geo909 Something is awry in your comment. The combiner function $f$ is a Boolean function that maps $m$ bits (the LFSR outputs) to $1$ bit, the desired sequence with high linear complexity. So what does $f(L_1,L_2,\ldots, L_m)$ mean since the arguments and output have changed from bits to integers? $\endgroup$
    – Dilip Sarwate
    May 11, 2013 at 19:45
  • $\begingroup$ Good point! "[...] the linear complexity is [...] $L=f(L_1,\cdots,L_m)$ [...] with the latter Boolean function transformed by evaluating the addition and multiplication operations in the function over the integers rather than over $GF(2)$" (Dawson, Simpson, Analysis and Design issues for Synchronous Stream Ciphers). Also this applies when the $L_i's$ are pairwise coprime. $\endgroup$
    – geo909
    May 11, 2013 at 19:51
  • $\begingroup$ @geo909 OK, I am still a little confused. If $f(a,b)=a\vee b = a \oplus b \oplus ab$, does $f(L_1,L_2)$ equal $L_1+L_2+L_1L_2$ for relatively prime $L_1, L_2$? Or does it equal something else? $\endgroup$
    – Dilip Sarwate
    May 11, 2013 at 22:40

Your Answer

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

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