Internal state recovery of keystream generator LILI-128 based on a novel weakness of the employed Boolean function

Abstract

This paper proposes an algorithm for internal state recovery of the keystream generator LILI-128 and introduces a novel approach for cryptanalysis of certain stream ciphers which belong to the class of nonlinear filters. The proposed cryptanalysis is based on a cryptographic feature/weakness of the Boolean function employed as the nonlinear filter. It is shown that the developed algorithm is significantly more efficient than the previously reported ones against LILI-128 and can recover the internal state with time complexities of pre-processing and processing of the order of 2 47 and 2 35, respectively, the space complexity of 2 47, and a sample of dimension approximately equal to 2 46. The developed cryptanalysis is also a practical confirmation on the significance of the so-called "non-normality" design criterion for Boolean functions.