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

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 247 and 235, respectively, the space complexity of 247, and a sample of dimension approximately equal to 246. The developed cryptanalysis is also a practical confirmation on the significance of the so-called “non-normality” design criterion for Boolean functions.

► An algorithm for internal state recovery of the keystream generator LILI-128 and a novel approach for cryptanalysis of certain stream ciphers are pointed out.
► The proposed cryptanalysis employs a cryptographic feature/weakness of involved k-normal Boolean function.
► The cryptanalysis combines elements of time–memory–data trade-off technique and some implications of the k-normality.
► The developed cryptanalysis is an alternative attacking approach against LILI-128, and it provides additional flexibility/gain.
► The developed cryptanalysis shows how a particular attack can be mounted when the non-normality criterion of the involved Boolean function is not fulfilled.