On the Affine Sub-Families of Quadratic NFSRs
Jiamin Zhang, Tian Tian, Wen‐Feng Qi, Qun-Xiong Zheng · IEEE Transactions on Information Theory · 2017
Grain-128 is a hardware oriented stream cipher based on the cascade connection of a 128-bit linear feedback shift register into a 128-bit quadratic nonlinear feedback shift register (NFSR). Its main register is in essence a quadratic NFSR, however its affine sub-families could not be solved by the previous methods. In this paper, it is shown that the family of sequences generated by the main register of Grain-128 includes no affine sub-families except a small one of order three. To achieve this goal, a new method is proposed for solving affine sub-families of general quadratic NFSRs. Let NFSR(f) be an NFSR with a quadratic characteristic function f . It is proved that the characteristic function of a linear sub-family of the NFSR(f) divides a linear combination of variables appearing in the quadratic terms of f , where the division can be seen as the univariate polynomial division over the finite field F2. This facilitates picking up a candidate set of linear sub-families through univariate polynomial factorization over F2. The affine case is an analogy. Besides, a useful new upper bound on the orders of affine sub-families of a quadratic NFSR is given.