Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. One security criterion for the design of stream ciphers is to assure the output sequences of their used NFSRs have long periods. The periodicity of those sequences are guaranteed by the NFSRs’ nonsingularity. The nonsingularity is well solved for Fibonacci NFSRs, whereas it is not for Galois ones. This paper considers the nonsingularity of Galois NFSRs. Some necessary conditions are presented, first for general Galois NFSRs, and then for submaximum and maximum length Galois NFSRs. Moreover, both particular Galois NFSRs are enumerated. All these extend the known results for Fibonacci NFSRs into Galois ones.

Nonlinear feedback shift registers (NFSRs) are generally classified as Fibonacci NFSRs and Galois NFSRs according to their implementation configurations. Some Galois NFSRs can be equivalent to Fibonacci ones in the sense that their sets of output sequences are equal. Finding the characterization of those equivalent NFSRs is helpful to the design of NFSR-based stream ciphers. Moreover, one of their design's security criteria is to assure their used NFSRs are nonsingular. This paper considers the Galois NFSRs with terminal bits, which have the first several bits involved only shifts and have been used in many stream ciphers such as Grain and Trivium. The paper first gives a special class of such Galois NFSRs and reveals its relation with Fibonacci ones with respect to their sets of output sequences. It then presents a necessary and sufficient condition for an n- stage Galois NFSR with terminal bit equivalent to an n-stage Fibonacci NFSR. Based on this condition, the paper enumerates those n-stage Galois NFSRs with the same terminal bit that are equivalent to a given n-stage Fibonacci NFSR. Finally, the paper gives a necessary/sufficient condition for the nonsingularity of Galois NFSRs with terminal bits.

Abstract Grain is a hardware-oriented finalist in the eSTREAM Stream Cipher Project. As a particular Galois nonlinear feedback shift register (NFSR), cascade connection of two NFSRs has been used as the main building block in the Grain family of stream ciphers. Two NFSRs are said to be equivalent if their sets of output sequences are equal. Finding properties of equivalent cascade connections of two NFSRs is useful to the design of the Grain family of stream ciphers. This paper first gives some properties of feedback functions between equivalent cascade connections of two NFSRs. It then shows that a cascade connection of two NFSRs and its equivalent Galois NFSR have isomorphic state diagrams if they have the same stage number. Finally, the paper reveals that for any given cascade connection of an $m$-stage NFSR1 into an $n$-stage NFSR2, there is only another one equivalent cascade connection of an $m$-stage NFSR3 into an $n$-stage NFSR4; moreover, the feedback functions of NFSR1 and NFSR3 are dual complementary, and the feedback functions of NFSR2 and NFSR4 are complementary. As an application of this property, the paper shows that the existing Grain family of stream ciphers have used the ones with lower cost of hardware implementations between their own two equivalent cascade connections, confirming their good design criteria.

Grain is one of three hardware-oriented finalists of the eSTREAM Project. A nonlinear feedback shift register (NFSR) in Grain-like structure is a cascade connection of a linear feedback shift register (LFSR) into an NFSR, in which the characteristic polynomial of the LFSR is primitive and the feedback function of the NFSR is nonsingular. In 2011 Hu and Gong pointed out that the period of the sequence generated by an NFSR in Grain-like structure is a multiple of the period of the sequence generated by its LFSR if the initial state of the LFSR is nonzero. Meanwhile, they proposed an open problem: for fixed feedback functions of an NFSR and an LFSR, determine whether the sequences generated by the NFSR in Grain-like structure can achieve the minimum period, i.e., the period of the LFSR, when the initial state of the LFSR is nonzero, and if they can achieve, provide at least one pair of the initial states of the NFSR and LFSR. Clearly, from a security point of view, it is not preferable if the sequences generated by an NFSR in Grain-like structure achieve the minimum period. This paper converts the open problem into a problem of solving an integer equation with respect to two unknown integers that uniquely correspond to the initial states of the NFSR and LFSR, by viewing the NFSR as a Boolean control network. Based on the integer equation, this paper shows that for any given initial state of an n-stage NFSR and any given nonzero initial state of an m-stage LFSR, the probability that the sequence generated by the NFSR in Grain-like structure achieves the minimum period 2m-1 is at most 2-n. This implies that the probability of the cascade connection used in Grain achieving the minimum period is very small.

Driven stable nonlinear feedback shift registers (NFSRs) with inputs are not only able to limit error propagations in convolutional decoders, but also helpful to analyze the period properties of sequences generated by a cascade connection of NFSRs in stream ciphers. An NFSR is driven stable if and only if the reachable set is a subset of the basin. Due to lack of efficient algebraic tools, the driven stability of NFSRs with inputs has been much less studied. This paper continues to address this research using a Boolean control network approach. Viewing an NFSR with input as a Boolean control network, we first give its Boolean control network representation, which is characterized with a state transition matrix. Some properties of the state transition matrix are then provided. Based on these, explicit forms are given for the reachable set and the set of basin. Two algorithms for obtaining both the sets are provided as well. Compared with the exhaustive search and the existing state operator method, the Boolean control network approach requires lower computational complexity for those NFSRs with their stages greater than 1.