LILI-128 DESIGN

1. Design of LILI-128 keystream generator
The LILI-128 keystream generator is a simple and fast keystream generator that uses two binary LFSRs and two functions to generate a pseudorandom binary keystream sequence. The structure of the LILI keystream generators can be grouped into two subsystems based on the functions they perform: clock control and data generation. The LFSR for the clock-control subsystem is regularly clocked. The output of this subsystem is an integer sequence which controls the clocking of the LFSR within the data-generation subsystem.

The state of the LILI-128 is defined to be the contents of the two LFSRs. The functions fc and fd are evaluated on the current state data, and the feedback bits are calculated. Then the LFSRs are clocked and the keystream bit is output. At initialisation, the 128 bit key is used directly to form the initial values of the two shift registers, from left to right, the first 39 bits in LFSRc then the remaining 89 bits in LFSRd. In the rare event that either register is initialised as all zeros, then that key is declared invalid. For LILI-128, LFSRd is clocked at least once and at most four times between the production of consecutive keystream bits.

Figure 1: Overview of LILI-128 keystream generators.

2. Clock Control Subsystem
The clock-control subsystem of LILI-128 uses a pseudorandom binary sequence produced by a regularly clocked LFSR, LFSRc of length 39 and a function fc, operating on the contents of k = 2 stages of the LFSRc to produce a pseudorandom integer sequence. The feedback polynomial of LFSRc is chosen to be the primitive polynomial:

x³⁹ + x³⁵ + x³³ + x³¹ + x¹⁷ + x¹⁵ + x¹⁴ + x² + 1

and the initial state of LFSRc is never allowed to be the all zero state. It follows that LFSRc produces a maximum-length sequence of period P_c = 2³⁹ - 1.

To remove any possible ambiguity, the recursion that corresponds to the feedback polynomial for LFSRc is:

s[39+t] = s[37+t] ^ s[25+t] ^ s[24+t] ^ s[22+t] ^ s[8+t] ^ s[6+t] ^ s[4+t] ^ s[t]

where ^ indicates the exclusive-or operation on bits (equivalent to addition modulo 2), and LFSRc shifts left at a time t.

At time instant t, the contents of stages 12 and 20 of LFSRc are input to the function fc and the output of fc is an integer c(t), such that c(t) is an element of {1,2,3,4}. The function fc is given by:

fc(x₁₂, x₂₀) = 2(x₁₂) + x₂₀ + 1

3. Data Generation Subsystem
The data-generation subsystem of LILI-128 uses the integer sequence c produced by the clock-control subsystem to control the clocking of a binary LFSR, LFSRd of length 89. The contents of a fixed set of n=10 stages of LFSRd are input to a specially chosen Boolean function, fd. The truth table for this function is given in the Appendix. The binary output of fd is the keystream bit z(t). After z(t) is produced, the two LFSRs are clocked and the process repeated to form the keystream.
The feedback polynomial of LFSRd is chosen to be the primitive polynomial:

x⁸⁹ + x⁸³ + x⁸⁰ +x⁵⁵ + x⁵³ +x⁴² + x³⁹ + x + 1

and the initial state of the LFSRd is never all the zero state. Then LFSRd produces a maximum-length sequence of period P_d = 2⁸⁹ - 1 which is Mersenne Prime.

To remove any possible ambiguity, the recursion that corresponds to the feedback polynomial for LFSRd is:

u[89+t] = u[88+t] ^ u[50+t] ^ u[47+t] ^ u[36+t] ^ u[34+t] ^ u[9+t] ^ u[6+t] ^ u[t]

where ^ indicates the exclusive-or operation on bits (equivalent to addition modulo 2), and LFSRd shifts left at a time t.

The 10 inputs to the fd are taken from LFSRd positions according to this full positive difference set: (0,1,3,7,12,20,30,44,65,80). The function fd has been chosen to be balanced, highly nonlinear and the satisfy the third order of correlation immunity relative to the positions of 10 stages used as inputs to fd.

The truth table for the output function fd is as follows:

0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,
0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,
0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,
1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,
0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,
0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,
0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,
1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,
0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,
0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,
0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,
0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,
1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,
1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,
0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,
1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,
0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,
1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,
0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,
1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,
0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,
0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,
0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,
0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,
1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,
0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,
1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0

The Boolean Function has 10 inputs and these properties: Balanced, CI(3), Order=6, Nonlinearity=480, No Linear Structures.