The Nonlinear Filter Boolean Function of LILI-128 Stream Cipher Generator Is Successfully Broken Based on the Complexity of Nonlinear 0 1 Symbol Sequence

Show more

The nonlinear filter Boolean function of LILI-128 stream cipher generator is studied in this paper. First we measure the complexity of the stream ciphers sequence of LILI-128 stream cipher generator and obtain the shortest bit stream sequence reconstructed Boolean function of nonlinear filter in LILI-128 stream cipher generator. Then the least nonlinear Boolean function of generating stream cipher sequence is reconstructed by clusterig, nonlinear predictive and nonlinear synchronization from shortest bit stream sequence. We have verified the correctness of our reconstruction result by simulating the block diagram of Lili-128 keystream generator using our getting Boolean function and implement designers’ reference module of Lili-128 stream cipher public online, and two methods produce the same synchronous keystream sequence under same initial state, so that our research work proves that the nonlinear Boolean function of LILI-128 stream cipher generator is successfully broken.

References

[1] B. Schneier, “Applied Cryptography,” 2nd Edition, John Wiley and Sons, Hoboken, 1996.

[2] R. E. Atani, et al., “Alamout: A New Synchronous Stream Cipher with Authentication,” IEEE Proceedings of the 1st International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace & Electronic Systems Technology, 17-20 May 2009, pp. 4244-4067.

[3] E. Dawson, A. Clark, J. Golic, W. Millan, L. Penna and L. Simpson, “The LILI-128 Keystream Generator,” NESSIE Proceedings of the Fist Open NESSIE Workshop, Leuven, November 2000. Http://www. cryponessie.org.

[4] M. J. O. Saarinen, “A Time-Memory Trade of Attack against LILI-128,” In: Fast Software Encryption (Lecture Notes in Computer Science), Springer-Verlag, Berlin, 2002, pp. 231-236. doi:10.1007/3-540-45661-9_18

[5] H. Molland and T. Helleseth, “An Improve Correlation Attack against Irregular Clocked and Filtered Keystream Generators,” In: Advance in Cryptology-Crypto 2004 (Lecture Notes in Computer Science), Springer-Verlag, Berlin, 2004, pp. 373-389.
doi:10.1007/978-3-540-28628-8_23

[6] N. T. Courtois, “Fast Algebraic Attack on Stream Ciphers with Linear Feedback,” In: Advance in Cryptology-Crypto 2003 (Lecture Notes in Computer Science), Springer-Verlag, Berlin, 2003, pp. 176-194.

[7] Y. Tsunoo, T. Saito, M. Shigeri, H. Kubo and K. Minematsu, “Shorter Bit Sequence Is Enough to Break Stream Cipher LILI-128,” IEEE Transactions on Information Theory, Vol. 51, 2005, pp. 4312-4319.
doi:10.1109/TIT.2005.859285

[8] W. Millan and E. Dawson, “LILI-II Is Not Broken,” 2005.
http//eprint.iacr.org/complete/2005/234