A Fibonacci View on the Galois NFSR Used in Trivium

Trivium is an international standard of lightweight stream ciphers (ISO/IEC 29192-3: 2012). In this paper, the Trivium-like NFSRs, a class of Galois NFSRs generalized from the Galois NFSR of Trivium, are studied from the perspective of Fibonacci NFSRs. It is shown that an n-stage Trivium-like NFSR cannot be equivalent to an n-stage Fibonacci NFSR, which is proved by showing the existence of “collision initial states”. As an intermediate conclusion, a necessary and sufficient condition for a kind of linear degeneracy of a Trivium-like NFSR is obtained from the persepective of interleaved sequences. Moreover, the smallest stage number of a Fibonacci NFSR that can generate all the output sequences of an n-stage Trivium-like NFSR is shown to be greater than n − 7 and this value is no less than 371 = 287 + min{93, 84, 111} specifically for the 288-stage Galois NFSR used in Trivium. These results contradict the existence of a equivalent Fibonacci model of Trivium NFSR of small stage, which implies that Trivium algorithm possesses a fair degree of immunity against “structure attack”.