Source of this document
LILI-II DESIGN

1. Design of LILI-II keystream generator
The LILI-II 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-II 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 mixed with the 128-bit IV (by two passes through the lili-II cipher) to form the initial values of the two shift registers, from left to right, the 128 bits in LFSRc then the 127 bits in LFSRd. In the rare event that either register is initialised as all zeros, then that key is declared invalid. For LILI-II, LFSRd is clocked at least once and at most four times between the production of consecutive keystream bits.


Figure 1: Overview of LILI-II keystream generator.

2. Clock Control Subsystem
The clock-control subsystem of LILI-II uses a pseudorandom binary sequence produced by a regularly clocked LFSR, LFSRc of length 128 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:

x128 + x126 + x125 + x124 + x123 + x122 + x119 + x117 + x115 + x111 + x108 + x106 + x105 + x104 + x103 + x102 + x96 + x94 + x90 + x87 + x82 + x81 + x80 + x79 + x77 + x74 + x73 + x72 + x71 + x70 + x67 + x66 + x65 + x64 + x60 + x58 + x57 + x56 + x55 + x53 + x52 + x51 + x50 + x49 + x47 + x44 + x43 + x40 + x39 + x36 + x35 + x30 + x29 + x25 + x23 + x18 + x17 + x16 + x15 + x14 + x11 + x9 + x8 + x7 + x6 + x1 + 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 Pc = 2128 - 1.

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

s[128+t] =
s[127+t] ^ s[122+t] ^ s[121+t] ^ s[120+t] ^ s[119+t] ^ s[117+t] ^ s[114+t] ^ s[113+t] ^ s[112+t] ^ s[111+t] ^ s[110+t] ^ s[105+t] ^ s[103+t] ^ s[99+t] ^ s[98+t] ^ s[93+t] ^ s[92+t] ^ s[89+t] ^ s[88+t] ^ s[85+t] ^ s[84+t] ^ s[81+t] ^ s[79+t] ^ s[78+t] ^ s[77+t] ^ s[76+t] ^ s[75+t] ^ s[73+t] ^ s[72+t] ^ s[71+t] ^ s[70+t] ^ s[68+t] ^ s[67+t] ^ s[63+t] ^ s[62+t] ^ s[61+t] ^ s[58+t] ^ s[57+t] ^ s[56+t] ^ s[55+t] ^ s[54+t] ^ s[51+t] ^ s[49+t] ^ s[48+t] ^ s[47+t] ^ s[46+t] ^ s[41+t] ^ s[38+t] ^ s[34+t] ^ s[32+t] ^ s[26+t] ^ s[25+t] ^ s[24+t] ^ s[23+t] ^ s[22+t] ^ s[20+t] ^ s[17+t] ^ s[13+t] ^ s[11+t] ^ s[9+t] ^ s[6+t] ^ s[5+t] ^ s[4+t] ^ s[3+t] ^ s[2+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 0 and 126 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(x0, x126) = 2(x0) + x126 + 1

3. Data Generation Subsystem
The data-generation subsystem of LILI-II uses the integer sequence c produced by the clock-control subsystem to control the clocking of a binary LFSR, LFSRd of length 127. The contents of a fixed set of n=12 stages of LFSRd are input to a specially chosen Boolean function, fd. The truth table for this function is given below. 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:

x127 + x121 + x120 + x114 + x107 + x106 + x103 + x101 + x97 + x96 + x94 + x92 + x89 + x87 + x84 + x83 + x81 + x76 + x75 + x74 + x72 + x69 + x68 + x65 + x64 + x62 + x59 + x57 + x56 + x54 + x52 + x50 + x48 + x46 + x45 + x43 + x40 + x39 + x37 + x36 + x35 + x30 + x29 + x28 + x27 + x25 + x23 + x22 + x21 + x20 + x19 + x18 + x14 + x10 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1

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

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

u[127+t] =
u[126+t] ^ u[125+t] ^ u[124+t] ^ u[123+t] ^ u[121+t] ^ u[120+t] ^ u[119+t] ^ u[117+t] ^ u[113+t] ^ u[109+t] ^ u[108+t] ^ u[107+t] ^ u[106+t] ^ u[105+t] ^ u[104+t] ^ u[102+t] ^ u[100+t] ^ u[99+t] ^ u[98+t] ^ u[97+t] ^ u[92+t] ^ u[91+t] ^ u[90+t] ^ u[88+t] ^ u[87+t] ^ u[84+t] ^ u[82+t] ^ u[81+t] ^ u[79+t] ^ u[77+t] ^ u[75+t] ^ u[73+t] ^ u[71+t] ^ u[70+t] ^ u[68+t] ^ u[65+t] ^ u[63+t] ^ u[62+t] ^ u[59+t] ^ u[58+t] ^ u[55+t] ^ u[53+t] ^ u[52+t] ^ u[51+t] ^ u[46+t] ^ u[44+t] ^ u[43+t] ^ u[40+t] ^ u[38+t] ^ u[35+t] ^ u[33+t] ^ u[31+t] ^ u[30+t] ^ u[26+t] ^ u[24+t] ^ u[21+t] ^ u[20+t] ^ u[13+t] ^ u[7+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 12 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,96,122). The function fd has been chosen to be balanced, highly nonlinear and has first order of correlation immunity relative to the positions of 12 stages used as inputs to fd. This function also has nonlinearity 1992 and algebraic order 10.

NOTE this function REPLACES the previously published Boolean function, which was discovered to be very wrong.

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

9,6,5,A,6,9,A,5,6,9,A,5,9,6,5,A,6,9,A,5,9,6,5,A,6,9,A,5,9,6,5,A,
6,6,A,A,9,9,5,5,9,9,5,5,6,6,A,A,9,9,5,5,6,6,A,A,9,9,5,5,6,6,A,A,
3,C,F,0,C,3,0,F,C,3,0,F,3,C,F,0,C,2,0,D,3,E,F,1,C,2,0,D,3,E,F,1,
C,C,0,0,3,3,F,F,3,3,F,F,C,C,0,0,3,1,F,E,C,D,0,2,3,1,F,E,C,D,0,2,
6,9,A,5,9,6,5,A,9,6,5,A,6,9,A,5,6,9,A,5,9,6,5,A,6,9,A,5,9,6,5,A,
9,9,5,5,6,6,A,A,6,6,A,A,9,9,5,5,9,9,5,5,6,6,A,A,9,9,5,5,6,6,A,A,
C,3,0,F,3,C,F,0,3,C,F,0,C,3,0,F,C,1,0,E,3,D,F,2,C,1,0,E,3,D,F,2,
3,3,F,F,C,C,0,0,C,C,0,0,3,3,F,F,3,2,F,D,C,E,0,1,3,2,F,D,C,E,0,1,
6,9,A,5,6,9,A,5,9,6,5,A,9,6,5,A,4,E,7,2,4,F,7,1,4,C,7,1,4,F,7,3,
9,9,5,5,9,9,5,5,6,6,A,A,6,6,A,A,B,E,8,3,B,C,8,1,B,C,8,0,B,D,4,2,
C,3,0,F,C,3,0,F,3,C,F,0,3,C,F,0,D,A,E,1,D,D,E,E,D,A,E,7,D,7,E,2,
3,3,F,F,3,3,F,F,C,C,0,0,C,C,0,0,1,6,2,2,1,B,2,7,1,E,2,C,1,A,2,0,
9,6,5,A,9,6,5,A,6,9,A,5,6,9,A,5,B,0,8,F,B,2,8,C,B,3,8,C,B,3,8,D,
6,6,A,A,6,6,A,A,9,9,5,5,9,9,5,5,4,0,7,F,4,2,7,D,4,3,7,C,4,2,7,D,
3,C,F,0,3,C,F,0,C,3,0,F,C,3,0,F,1,A,2,0,1,3,2,8,1,F,2,F,1,0,2,E,
C,C,0,0,C,C,0,0,3,3,F,F,3,3,F,F,D,9,E,D,D,0,E,5,D,8,E,5,D,B,E,8,
9,6,5,A,6,9,A,5,6,9,A,5,9,6,5,A,B,4,8,7,4,B,7,8,B,4,8,7,4,B,7,8,
6,6,A,A,9,9,5,5,9,9,5,5,6,6,A,A,4,4,7,7,B,B,8,8,4,4,7,7,B,B,8,8,
3,C,F,0,C,3,0,F,C,3,0,F,3,C,F,0,2,E,1,D,D,2,E,1,2,E,1,D,D,2,E,1,
C,C,0,0,3,3,F,F,3,3,F,F,C,C,0,0,E,D,D,E,1,1,2,2,E,D,D,E,1,1,2,2,
9,6,5,A,6,9,A,5,6,9,A,5,9,6,5,A,4,B,7,8,B,4,8,7,4,B,7,8,B,4,8,7,
6,6,A,A,9,9,5,5,9,9,5,5,6,6,A,A,B,B,8,8,4,4,7,7,B,B,8,8,4,4,7,7,
3,C,F,0,C,3,0,F,C,3,0,F,3,C,F,0,D,2,E,1,2,E,1,D,D,2,E,1,2,E,1,D,
C,C,0,0,3,3,F,F,3,3,F,F,C,C,0,0,1,1,2,2,E,D,D,E,1,1,2,2,E,D,D,E,
6,9,A,5,6,9,A,5,9,6,5,A,9,6,5,A,4,9,7,1,4,4,7,8,4,9,7,D,4,F,7,B,
9,9,5,5,9,9,5,5,6,6,A,A,6,6,A,A,B,2,8,E,B,7,8,2,B,A,8,6,B,9,8,4,
C,1,0,E,C,2,0,D,3,D,F,2,3,E,F,1,6,6,A,D,6,8,A,C,6,8,A,7,6,C,A,3,
3,2,F,D,3,1,F,E,C,E,0,1,C,D,0,2,6,7,A,0,6,5,A,D,6,0,A,0,6,7,A,7,
6,9,A,5,6,9,A,5,9,6,5,A,9,6,5,A,4,F,7,9,4,6,7,4,4,A,7,9,4,0,7,0,
9,9,5,5,9,9,5,5,6,6,A,A,6,6,A,A,B,4,8,B,B,A,8,F,B,5,8,3,B,5,8,E,
C,2,0,D,C,1,0,E,3,E,F,1,3,D,F,2,9,E,5,2,9,5,5,3,9,9,5,2,9,8,5,9,
3,1,F,E,3,2,F,D,C,D,0,2,C,E,0,1,9,7,5,6,9,5,5,E,9,9,5,F,9,1,5,D

The Boolean Function has 12 inputs and these properties: Balanced, CI(1), Algebraic Degree=10, Nonlinearity=1992, No Linear Structures.