Research On Affine Sub-families Of A Family Of NFSR Sequences

With the development of cryptanalysis, the stream ciphers based on nonlinear feedback shifted registers(NFSR) attract more and more attention. However, compared with LFSR sequences whose algebraic properties are adequately understood, algebraic properties of NFSR sequences are extremely resistant to analysis. For example, whether a family of NFSR sequences contains some set of sequences with low linear complexity is essentially unknown. If the set of output sequences of an NFSR includes a large number of sequences with low linear complexity, then stream ciphers based on this NFSR may be vulnerable to correlation attacks, algebraic attacks of distinguishing attacks based on linear approximations. A simple case is that a family of NFSR sequences contains a sub- family of LFSR sequences. In particular, if an NFSR can be decomposed into the cascade connection of an NFSR into an LFSR, the family of the NFSR may include an affine sub-family. In general, an NFSR can be implemented either in the Fibonacci configuration(called Fibonacci NFSR) or in the Galois configuration(called Galois NFSR). In this paper, we study the affine sub- families of a family of Fibonacci NFSRs. The main results are,1. For a given NFSR, we present a method to obtain all the decompositions of the NFSR into the cascade connection of an NFSR into an LFSR. Our result shows that all such decompositions can be obtained by factoring a polynomial over the finite field o f two elements. Furthermore, a potential weakness of an NFSR of such decomposition for cryptographic applications is discussed.2. If the family of output sequences of an NFSR includes an affine sub- family, we call the minimal length of the LFSR which can generate the sub- family the order of the affine sub-family. In this paper, we give a method to derive an upper bound on the maximal order of affine sub- families of a family of NFSR sequences, which can be directly obtained from the algebraic normal form(ANF) of the characteristic function of the NFSR.3. In Grain v1, the 160-bit NFSR is a cascade connection of an 80-bit LFSR into an 80-bit NFSR. In this paper, we study how to compute affine sub- families included in the family of output sequences of the 160-bit NFSR in Grain. Firstly, we prove that if the family of output sequences of the 160-bit NFSR includes an affine sub- family, then it must be included in that of the 80-bit NFSR in Grain. Next, the result in 2 shows that the order of the affine sub- families in the family of output sequences of the 80-bit NFSR in Grain is no more tha n 31. Furthermore, we propose two algorithms to solve affine sub- families included in the family of output sequences of the 80-bit NFSR. Finally, we obtain that the family of o utput sequences of the 160-bit NFSR in Grain includes no affine sub-families except for an affine sub-family of order 2.