Paper 2021/928 Original: eprint.iacr.org/2021/928 ↗

Necessary and Sufficient Conditions for Galois NFSRs Conditionally Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium

Abstract

Grain and Trivium are two typical stream ciphers based on nonlinear feedback shift registers (NFSRs). The 160-stage Galois NFSR used in Grain was found conditionally equivalent to a 160-stage Fibonacci NFSR before Grain was introduced. But it remains unknown whether the 288-stage Galois NFSR used in Trivium is conditionally equivalent to a Fibonacci NFSR, though Trivium exists for over ten years and several types of Galois NFSRs have been found conditionally equivalent to Fibonacci ones with same stage number over the last decades. This paper applies the NFSR's dynamic system description, and obtains some necessary and sufficient conditions for Galois NFSRs to be conditionally equivalent to Fibonacci ones with same stage number, covering and improving the previous work on this research. As an application, the paper reveals that the 288-stage Galois NFSR used in Trivium is not conditionally equivalent to any Fibonacci NFSR, indicating the infeasibility of applying a conditionally equivalent Fibonacci NFSR to simplify its cryptanalysis, and indicating the good confusion and diffusion of the initial state to the output sequence generated from the Galois NFSR's 288-th bit that is used as one of inputs of Trivium's filtering function. This provides a formal extra justification of Trivium's good design, and allows future designs to be built by the same principle.