Circuits and Systems
Vol.4 No.2(2013), Article ID:29860,4 pages DOI:10.4236/cs.2013.42022

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

Xiangao Huang1, Chao Wang2, Wei Huang3, Junxian Li1

1Beijing Institute of Technology, Zhuhai Campus, Zhuhai, China

2Computer Center, Chang’an University, Xi’an, China

3Research Institute of Electronics, Xi’an, China

Email: xiangaohuang@yahoo.com.cn

Copyright © 2013 Xiangao Huang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Received January 24, 2013; revised February 24, 2013; accepted March 4, 2013

Keywords: LILI-128 Stream Cipher; Clock Control; Boolean Function; Complexity; Attack

ABSTRACT

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.

1. Introduction

Our society greatly depends on security of communications, financial transactions, telematic services, internet and mobile networks [1] which in turn present new challenges for protecting the information from unauthorized eavesdropping. Cryptography mainly uses two types of symmetric algorithms, block ciphers and stream ciphers. The block ciphers have become widely used technology. As an example AES is a secure block cipher that offers excellent performance on a variety of hardware and software environments. On the other hand, the stream ciphers are widely used in secure communication because of high throughput, less complex hardware circuitry and very little error propagation which has attracted much attention. An important class of stream ciphers is based on a mixture of linear feedback shift register (LFSR), nonlinear filter generators and also clock-controlled generators [2,3]. LILI-128 stream cipher is an example which is designed by Dawson, Clark, Golic, Millan, Penna and Simpson, which submitted to NESSIE (New European Schemes for Signatures, Integrity and Encryption) as a candidate cipher [3]. According to the final report, LILI- 128 stream cipher was rejected in the first round of NESSIE. In this work we will discuss basic structure and the attack of LILI-128 stream cipher. We particularly study the filter Boolean function of LILI-128 stream cipher generator.

2. The Structure of LILI-128

The structure of the LILI-128 keystream generators is illustrated in Figure 1. It uses two binary LFSRc and LFSRd and two functions fc and fd to generate a pseudorandom binary keystream sequence. At initialization, 128 bit key provides the initial states of the LFSRc and LFSRd.

The generator can be divided into two subsystems based on the functions they perform: the clock control subsystem and data generation subsystem. The clock control subsystem produces an integer sequence that is used to control data generation subsystem. The feedback polynomial of the LFSRc is chosen to be the primitive polynomial

(1)

Since is primitive, the LFSRc produce a maximum-length sequence of period. The function fc takes two bits as input and produced an integer ck such that. The value of ck is calculated as

(2)

The LFSRd is clocked by ck at least once and at most four times, which is given as fllows:

(3)

since is a primitive polynomial, a period of at maximum is guaranteed for LFSRd output sequence. The contents of 10 different stages of LFSRd are input to a nonlinear filter function fd. The output zk of nonlinear filter function fd is the keystream sequence.

3. Security Analysis

LILI-128 stream cipher are a long period around 2128, high linear complexity which is conjectured to be at least 268, and good statistics regarding the distribution of zeroes and ones, so designers claim that the LILI-128 keystream generator can resist currently known styles of attack. Some methods [4-7] of breaking it have been proposed, since LILI-128 stream cipher was publicized in 2000. The methods have already been shown that some attack break the LILI-128 stream cipher more efficiently than an exhaustive search for its secret key. However, most of the attack methods consider only the complexity of time or memory for search for its secret key. For example, Time-Memory Tradeoff Attack [4] needs approximately 246 bits, and Correlation Attack [5] needs approximately about 223 bits. While algebraic Attack [6] needs approximately 218 bits. Even a new attack method [7] requires a mere 27 bits of keystream, but needs 299 − 1 computations. The above styles of attack are only quailtative analysis, without an actual example of the successful attack. In 2005, designers summarize recently published styles of attack on the LILI-128 stream cipher, and assert that LILI-128 remains unbroken [8]. They encourage further analysis of the LILI-128 stream cipher.

4. The Expression of the Nonlinear Filter Function fd

In Figure 1, designers do not publicize the expression of the nonlinear filter function fd. Up to now, all attacks explain only that LILI-128 has lower complexity as designers claim, and do not get the expression of the nonlinear filter function fd. The aim which we attack LILI- 128 is the expression of the nonlinear filter function fd. The reference module of LILI-128 is got from the Information Security Institute’s webpage: http://www.isi.qut.

Figure 1. Overview of LILI-128 keystream generators.

edu.au/resources/lili/. We implement the reference module on ASCII initial value “yyyy yyyyyyyyyyy y” and get the keystream sequence of LILI-128, and study the expression of the nonlinear filter function fd. First, we determine the least keystream bit amount of expressing the nonlinear filter function fd from the LILI-128 kystream sequence by means of measuring the complexity of the LILI-128 kystream sequence. The least keystream bit amount of expressing the nonlinear filter function fd is not equal for differ initial state. The least keystream bit amount is approximately 212 - 213 bits. We reconstruct the expression fd from Shortest bit stream sequence by clusterig, nonlinear predictive and nonlinear synchronization, which has 46 items from liner items to nonlinear polynomials with 6 orders as follows:

(4)

5. Verifying the Correctness for the Filter Boolean Function fd

If we describe LILI-128 keystream generator by MATLAB, the stages of LFSRc be labeled s[1], s[2],∙∙∙, s[39] from left to right. At every time, we have the following formula to calculate the feedback bit:

(5)

where indicates the addition modulo 2. Let the LFSRc shift left, and s[38] = w. Sequentially circulating, the LFSRc will produce a linear pseudorandom sequence. The function fc is given by

(6)

The stages of LFSRd be labeled u[1], u[2], ∙∙∙, u[89] from left to right. At time k, the feedback bit is calculated by the following formula

(7)

where indicates the addition modulo 2. Let the LFSRd shift left, and u[89] = w. According to above circulation, the LFSRd will produce a linear pseudorandom sequence. We map the set: (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) into the set: (1, 2, 4, 8, 13, 21, 31, 45, 66, 81), the fd is given by:

(8)

We simulate the keystream sequence of LILI-128 in Figure 1 using (6) by 128 bits initial values which are ASCII “yyyyyyyyyyyyyyyy”. Compare simulating result with the result of implementing the reference module, and two methods produce the same synchronous keystream sequence under same initial state “yyyyyyyyyyyyyyyy”. We verify the nonlinear filter function fd again by initial state “ggggggggggggggg” and “123456789abcdefg”, and obtain all the same synchronous keystream sequence, so that the validation work indicates we have successfully broken the nonlinear filter Boolean function of LILI-128 stream cipher generator.

6. Conclusion

In the design of LILI-128, Designers made an attempt to confuse the linear pseudorandom binary sequence with the long period Pc = 289 – 1 by the clock-control with the long period Pc = 239 – 1 and get high linear complexity of keystream sequence. The nonlinear sequence is generated through the nonlinear filter function fd with 46 items and the most algebraic 6 orders to withstand all kinds of currently known attack. The LILI-128 keystream generator certainly resists currently known styles of attack, but it does not withstand our attack. The currently known styles of attack based on time complexity and memory complexity of arithmetic. The attacks do not consider the complexity of keystream sequence oneself. We get the least bit amount of the attack by measuring the complexity of the keystream sequence of LILI-128 and the nonlinear filter function fd from the least keystream bit amount by the phase space reconstruction, Clustering, nonlinear prediction and nonlinear synchronization. In this paper, our research work has made a great breakthrough in stream cipher analysis, breaks the dream that stream cipher of LILI-128 is not attacked, and will bring the importance influence on stream cipher design. We only publish our research result and do not expatiate the specific theory and algorithm of attacking LILI-128 stream cipher because our attack method has important application in attacking military stream cipher. Reader verifies above fd first of all. And then fd is redesigned. The stream cipher sequence of LILI-128 output is obtained by simulating Figure 1 given an ASCII initial state. Reader sends the ASCII initial state and the stream cipher sequence whose length is 213 bits to us. We will return fd to him. The Boolean function fd of nonlinear filter is got from known stream ciphers sequence, which belongs to research areas of blind signal processing.

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