Keywords

Introduction

Cryptography is the study of mathematical techniques used for achieving secured communication over the unsecured channel. Cryptographic primitives are designed to deal with the basic security issues like confidentiality, integrity, authentication, and non-repudiation. It can be classified into two categories, namely symmetric key and asymmetric key primitives. Symmetric key cryptographic primitives have the advantage of higher throughput over asymmetric ones, and therefore symmetric key cryptographic primitives are widely used for bulk data encryption and decryption. Symmetric key ciphers are again subdivided into two categories, namely block cipher and stream cipher. The stream ciphers have the advantages of higher throughput, low latency, and lesser error propagation effect than that of block cipher. The basic working principle of the stream cipher is to generate an arbitrarily long pseudorandom bit stream from a given random string and that pseudorandom bitstream is used to encrypt the message stream. Further, stream cipher based on LFSR (Linear Feedback Shift Register) is characterized by its lightweight property and ease of implementation in hardware. A few examples of popular stream ciphers are A5/1 used in GSM security, E0 used in Bluetooth, RC4 used in SSL, etc. A few prominent lightweight stream ciphers are Grain, WG, Trivium, SNOW, Salsa 20, Sprout, SOBER, etc. [1,2,3].

The outline of the paper is as follows: section “Literature Survey” provides the literature survey. Section “Background and Preliminaries” provides the background and preliminaries related to stream cipher. Section “Analysis of Feedback Shift Registers for Stream Cipher” provides the FSR analysis part. Section “Proposed Design” describes the architecture of implemented nonlinear generator model and its result analysis. Finally, section “Conclusion and Future Work” concludes the paper.

Literature Survey

Here, we have discussed the different types of LFSR-based stream ciphers. A renewed interest has grown among the research communities for analysis and design of stream ciphers due to the launch of eSTREAM project [1]. This research project was maintained by European Network of Excellence for Cryptology from 2004 to 2008. Only seven candidates are chosen from long-term research project in Europe known as ECRYPT [4]. In Table 61.1, we have listed a few LFSR-based stream ciphers and their building process [2, 3].

Table 61.1 LFSR-based stream cipher list
Full size table

Background and Preliminaries

In this section, we have included mathematical preliminaries related to LFSR-based stream cipher design.

Boolean Function

A Boolean function is a mapping from \({{F}_2^n \rightarrow {F}_2}\), over the finite field with two elements{0, 1}. If the number of combination mapping consists of an equal number of \(1^{'}s\) and \(0^{'}s\), then the Boolean function is called as balanced.

For example, let us consider \(n=3\) variable Boolean function \({f(x_1,x_2,x_3)}\) = \({x_1x_2+x_2x_3+x_3}\). The input sequences of \((x_1,x_2,x_3)\) are (000, 100, 010, 110, 001, 101, 011, 111) and the final output of the Boolean function is depicted as (0, 0, 0, 1, 1, 1, 0, 1).

A cryptographically secured Boolean function should satisfy the following properties [5, 6]:

  • Boolean function should be balanced.

  • The nonlinearity and correlation immunity of the function should be high so that it can resist correlation attack.

  • The algebraic degree and algebraic immunity of the function should be high so that it can resist algebraic attack.

Algebraic Normal Form

Usually, every Boolean function has a distinct representation as a multivariate over \(F_{2}\) which is known as algebraic normal form (ANF). This function can be represented as

$$\begin{aligned} f(x_{1}, x_{2},\ldots ,x_{n}) = c_{0} \oplus \sum _{1 \le i \le n} c_{i}x_{i} \oplus \sum _{1 \le i \le j \le n }c_{i,j}x_{i}x_{j} \oplus \ldots \oplus c_{(1,2,\ldots ,n)}x_{1} \ldots x_{n} \end{aligned}$$

where the coefficients \({c_{0}, c_{i}, c_{i,j},\ldots ,c_{(1,2,\ldots ,n)}}\) \({\in {F}_2}\). In this function, the number of variables in the highest order product term (with coefficient non zero) is known as the algebraic degree. In general, when the degree of the function \(\textit{f}\) is at most one, it can be described as an affine function. The affine functions with (\(c_0\) = 0) are known as linear functions [6, 7].

Walsh Transform

This transformation function is an n variable Boolean function. In that case, \({c = \{c_1 \ldots c_n\} \in {F}_2^n}\) and a n variable linear function can be represented as \({l_c(x) = c_1 x_1 \oplus \ldots \oplus c_n x_n}\). So, this transformation function can be described as

$$\begin{aligned} W_{f}(c) = \sum _{x \in F_{2}^{n}} (-1)^{f(x) \oplus l_c(x)} \end{aligned}$$

From the above definition of \(W_{f}(c)\), it can be observed that, when \({f(x) \oplus l_c(x)}\) value is 0, then sum is increased by 1, and when this value is 1, sum is decreased by 1 [6, 7].

Nonlinearity

Nonlinearity of a Boolean function f of n variables can be described as the distance between the function and the set of all possible affine functions. Nonlinearity can be defined in terms of Walsh transform as given below [7, 8]:

$$\begin{aligned} {\textsf {nl(f)} = 2^{n-1} - \frac{1}{2}\ max\ |W_{f}(c)|} \end{aligned}$$

Correlation Immunity

A Boolean function f on \({{F}_2^n}\) is said to be correlation of order m, where \(1\le m \le n\), if the output of f and any m input variables are statistically independent. A Boolean function f on \({{F}_2^n}\) is correlation immune of order m iff \(W_{f}(c)=0\) for all vectors \({c \in {F}_2^n}\) such that \({0 \le | c | \le m}\) [6, 8].

Analysis of Feedback Shift Registers for Stream Cipher

The normal way of designing Feedback Shift Register (FSR) through binary sequences, \(\{c_0, c_1, \ldots c_n\} \in {GF}(2)\), fulfills the recurrence relation of order n. FSR is created by D Flip-flops which are connected serially and each D Flip-flop constructed in such a way that each gate is simulating the Boolean logic for feedback function. Moreover, if FSR runs with linear recurrence, feedback function is known as LFSR and if it runs with nonlinear recurrence, then feedback function is known as NLFSR [9]. eStream selected Grain, Trivium, and MICKEY stream cipher are designed by NLFSR [1].

LFSR

Linear Feedback Shift Register (LFSR) is a shift register with a feedback path. Here, the output sequence of each D Flip-flop is joined to the input of the adjacent D Flip-flops. Feedback path is defined as the tap position of D Flip-flop which takes part in the XOR (modulo 2) operation and provides input to the last D Flip-flop. Initial value of LFSR is known as seed value of LFSR. The feedback path is also known as feedback function or connection polynomial [9, 10].

For example, let us consider a LFSR degree is \(m=3\). The LFSR structure and feedback path are shown in Fig. 61.1. Here, this feedback path can be represented in polynomial form as \({(x^{3}+x^{2}+1)}\). The internal state bits are expressed as \(a_{i}\) and it has been shifted by one to the right at each clock. In that case, rightmost state bit is considered as present output bit and the leftmost state bit is calculated by feedback path. Let us consider the output bit is \(a_{i}\) and assuming the initial state bits are (\(a_0, a_1, a_2\)).

Fig. 61.1
figure 1

Schematic diagram of LFSR

Full size image

Now, the output sequence of the LFSR can be calculated as \(a_{i+3}=a_{i+1}+a_{i}\) mod 2, where \(i=0,1,2,3,\ldots ,\).

Properties of LFSR

  • In l-stage LFSR, if l number of registers are available in the LFSR, then the number of states is equal to \(2^{l-1}\).

  • However, every feedback path or connection polynomial will not give maximum length. The LFSR will yield maximum length if and only if the corresponding feedback path is primitive polynomial.

Klapper and Goresky developed similar type of LFSR design, known as Feedback with Carry Shift Register (FCSR). There are two different types of LFSR, namely Fibonacci and Galois [11]. In FCSR and LFSR, linear sequences are possible to employ through Berlekamp–Massey algorithm [10, 11].

LFSR-Based Stream Ciphers

The main use of LFSR in stream cipher is to produce pseudorandom sequence. We know, LFSR can generate an infinite bitstream. In the most common form, multiple LFSRs are used to build a stream cipher. But LFSR exhibits linear property. Thus the nonlinearity concept has been introduced to overcome the drawback of linear property [12] by irregularly changing the clock of the LFSR. LFSR-based stream cipher uses mainly three classes of pRNGs (pseudorandom number generators), namely nonlinear combination, nonlinear filter, and clock-controlled generators [13]. Almost every LFSR-based stream ciphers follow any of these nonlinear techniques or use a combination of these techniques with some extra efforts like adding counter or a combination of different LFSRs with NLFSR [1]. Usually, nonlinear combiner design employs n number of LFSRs of different lengths. In that case, all are initially assigned with nonzero seed values. During each clock pulse, n number of results from the LFSRs are taken and filled as n data inputs to an n variable Boolean function. In case of nonlinear filter generator, n numbers of outputs from different positions of the LFSR are filled as n inputs to an n variable Boolean function. Moreover, the Boolean function and memory collectively construct an FSM [7].

Proposed Design

Our proposed model follows a simple implementation of nonlinear combination generators shown in Fig. 61.2. The model comprises cryptographically secure Boolean function and number of LFSR can be added in a customized fashion. Here, for simplicity purpose, we use less number of the LFSR.

Fig. 61.2
figure 2

Proposed design structure

Full size image

Design Specifications

This design consists of three main blocks. In the first block, three LFSRs are initially loaded and passed through \({NLFSR_1 (f_1)}\) function. The second block is also loaded with three LFSR and passed through \({NLFSR_2 (f_2)}\) function and in the third block, five LFSRs are loaded and passed through \({NLFSR_3 (f_3)}\) function. In LFSR, the feedback polynomial values are listed in the next subsection. Finally, three blocks are passed through one nonlinear function (F).

Initialization

Before the output sequence generation, the structure must be initialized with nonzero seed values. Usually, LFSR connection polynomial over GF(2) is the primitive polynomial or it can be called as the update function. Now, LFSR filled with a sequence of bits or it can be loaded like a fixed sized bit of hex values, or a string. Table 61.2 shows the LFSR tap polynomials. Specifically, results of the structure, i.e., binary sequences of the functions, are listed in the matrix order.Footnote 1

Table 61.2 Parameters of the proposed model
Full size table
Table 61.3 Cryptographic properties obtained after using the Boolean functions
Full size table

Results and Performance Analysis

We have done all our experiments in SageMath tool. Here, the final bits obtained from the nonlinear filter, i.e., F, will be considered as the final output bit which is used as a nonlinear sequence. We have taken only 15 bits of output; however, the number of bits can be increased or decreased as per requirement and also can be further converted to fixed bit hex values or string. In this paper, we have analyzed the nonlinearity property of the proposed schemes which are numerically depicted. Table 61.3 shows the typical values of parameters such as balancedness, nonlinearity, maximum nonlinearity, algebraic immunity correlation immunity, and Walsh transform. More specifically, proposed model resultant bits are shown in Table 61.3. It shows the maximum possible nonlinearity and proposed design nonlinearity.

Conclusion and Future Work

In this paper, we have surveyed LFSR-/NLFSR-based stream ciphers. We have also implemented one nonlinear-based generator model to generate cryptographically secured bitstream. The various properties of randomness like algebraic immunity, correlation immunity, Walsh transformation, nonlinearity, etc. are listed in the tabulated form. The nonlinearity of the bitstream is compared with maximum nonlinearity achievable for a particular Boolean function. Research problems on NLFSR are still not well understood like patterns and its behaviors. Development of an intelligent algorithm for designing customized LFSR-based stream cipher using the generalized model shall be our future research work.