Design of Feedback Shift Register of Against Power Analysis Attack

Yongbin Zhao , XuYang and RanranLi

Abstract: Stream ciphers based on linear feedback shift register (LFSR) are suitable for constrained environments, such as satellite communications, radio frequency identification devices tag, sensor networks and Internet of Things, due to its simple hardware structures,high speed encryption and lower power consumption. LFSR, as a cryptographic primitive,has been used to generate a maximum period sequence. Because the switching of the status bits is regular, the power consumption of the LFSR is correlated in a linear way. As a result,the power consumption characteristics of stream cipher based on LFSR are vulnerable to leaking initialization vectors under the power attacks. In this paper, a new design of LFSR against power attacks is proposed. The power consumption characteristics of LFSR can be masked by using an additional LFSR and confused by adding a new filter Boolean function and a flip-flop. The design method has been implemented easily by circuits in this new design in comparison with the others.

Keywords: Stream cipher, feedback shift register, power analysis, Boolean function.

1 Introduction

On account of its simple hardware structures, high speed encryption and lower power consumption, stream ciphers based on LFSR are well suitable for constrained environments, such as satellite communications, radio frequency identification devices tag, sensor networks and Internet of Things. For example, ZUC [ETSI/SAGE Specification (2010)] formed the core of the 3GPP mobile standards 128-EEA3 and 128-EIA3. However, the security of stream ciphers is serious threaten by correlation attacks[Meier (2011)], algebraic attacks [Courtois (2002); Rønjom (2017)], differential cryptanalysis [Siegenthaler (1984); Banik (2016)], cube attack [Aumasson, Dinur and Meier (2009), Rahimi, Barmshory and Mansouri (2016)] and side channel attack etc. Side channel attacks, which include power attacks [Kocher, Jaffe and Jun (1999)], timing attacks [Kocher (1996)], electromagnetic attacks [Quisquater and Samyde (2001)] and differential fault analysis [Shamir and Biham (1998)], are effective methods to gain information from the physical implementation of a cryptosystem. Power attack has been considered as the most dangerous attack to the security of cryptographic embedded systems.

CMOS logic and application specific details cause the power characteristics of logic operations dependency on the input data. Power attack tries to find the relationship between initialization vectors (IV) and power consumption by using the measurement of the power consumption variation in every cycle. Differential power analysis was proposed by Kocher, Jaffe and Jun in 1999. Lano et al. [Lano, Mentens and Preneel(2004)] adapted differential power analysis methods to theoretically attack stream cipher algorithms A5/1 and E0. After Fischer et al. [Fischer, Gammel and Kniffler (2006)] have mounted a successful differential power attack against Trivium and Grain ciphers, which are candidate stream ciphers in ECRYPT (European Network of Excellence in Cryptology). The power analysis method has been widely applied in stream cryptanalysis[Tena-Sánchez and Acosta (2015); Gupta, Mishra and Suri (2016)]. A few designs [Kocher,Jaffe and Jun (1999), Burman, Mukhopadhyay and Veezhinathan (2007), Sharif Mansouri(2014)], which protect stream ciphers from leaking information, have been proposed. In this paper, a new design of LFSR against power attacks for stream cipher based on LFSR is proposed. The implementation is simpler and easier by using this design in comparison to the others. In addition, the better synchronization performance is achieved.

2 Preliminaries

2.1 Boolean function

Let be the finite field with two elementsdenote the n-dimensional vector space. A Boolean function f in n variables is a mapping frominto, and the set of all Boolean functions in n variables is denoted by.Alternatively, the Boolean functioncan also be represented as the Algebraic Normal Form (ANF), i.e.,

Many properties of Boolean functions can be described by the Walsh spectrum, such as nonlinearity, denoted by, balancedness, denoted bymth order correlation immunity(m-CI ),denoted by, where. The balanced m-CI function is said to be m-resilient.

In stream cipher, Boolean functions are provided high nonlinearity and satisfy certain criteria. Cryptographic properties of Boolean function, such as balancedness, nonlinearity and correlation immunity, etc. are also important indicator for the security of steam ciphers. Boolean functions with good cryptographic properties must be balanced, high level nonlinearity, CI is no less than 1 for filter functions and less than the number of LFSRs for combination functions.

2.2 LFSR

As a cryptographic primitive, LFSR composed of XOR gates and flip-flops has been used to generate a maximal period sequence. It has two implementation, Galois implementation and Fibonacci implementation. The Fibonacci implementation (see Fig. 1)is simply copy each bit to its neighbor on the right. In this paper, the Fibonacci representation LFSRs was adapted (see more details in [Goresky M and Klapper A M(2002)]). The initial state of the LFSR is called the IV. For example,in Fig. 1. Afterclock cycle, the state of LFSR is, and the leftmost bit isat the next clock cycle.

She saw that in her father’s palace the torches in the ballroom92 were extinguished, and all within asleep; but she did not venture to go in to them, for now she was dumb and going to leave them forever, she felt as if her heart would break

Figure 1: Fibonacci representation of LFSR with length n

The combination of taps and their location is often referred to as a connection polynomial, and expressed. Whenis a primitive polynomial, the output sequence of LFSR is a periodic sequence of span(called maximum length sequence or m-sequence).

3 Design of LFSR

Based on the power model of LFSR, the new design of LFSR can effectively mask the power consumption characteristics of the LFSR. By adding a filter function and a flipflop, the power consumption characteristics of the LFSR can be confused.

3.1 Power model of LFSR

In stream cryptosystems based on LFSR, the power consumption is mainly divided into three parts: the power consumption of the LFSR, the power consumption of the filter function, and other power consumption (caused by measurement errors, noise,electromagnetic radiation, etc.). These three parts are separately denoted byandrespectively. The power consumption of the LFSR is composed of XOR gates() and filp-flops (), that is. At ithclock cycle, the power consumed is expressed as:

Among other power consumptions, most of the consumptions are random measurement errors. It is generally considered that the errors can be reduced by multiple measurements in the same clock cycle. The mathematical expectation measurements ofis a constant (). Considered that the feedback function and filter function are realized by XOR gate, the power consumption is a const, that is. So it can be gotten that

Table 1: Power consumption of 0.18 CMOS standard cells

Table 1: Power consumption of 0.18 CMOS standard cells

Heading level Normalized Power 2-input NAND 1 2-input AND 2.14 2-input XOR 3.36 D Flip Flop 22.55

Remark: Some results on 90 nm ASIC technology had been given by Sharif Mansouri[Sharif Mansouri (2014)].

In order to suit for CMOS-implemented power consumption, Fischer et al. [Fischer,Gammel and Kniffler (2006)] used Hamming distance based on power model to describe the power consumptions and give an approximate estimation

3.2 Analysis of flip-flop state changes in LFSR

Because LFSR has been used to generate a maximal period sequence, the connection polynomial of LFSR is selected by a primitive polynomial.

For simplicity, the length of the LFSR in cipher stream is 8(8-stages) was assumed.Example 1. The feedback polynomial (primitive polynomial) [Lidl and Niederreiter(1994)] was chosen.

Obviously, the linear recurrence relation of Eq. (4) is

The period of output sequence is 255. Let IV =(01010100), the following output sequence was gotten

The statistical results are shown in Tab. 2, Fig. 2 and Fig. 3.

Table 2: Statistical results of the LFSR

Figure 2: Statistical figure of the LFSR with state changes

Figure 3: Statistical figure of the LFSR with CoutZtO and the difference of CoutZtO

Form Fig. 3 and Fig. 4, the power consumption of the LFSR is highly correlated in a linear way and the power consumption characteristics of stream cipher based on LFSR are vulnerable to leaking IV under the power attacks(see more details in Burman et al.[Burman, Mukhopadhyay and Veezhinathan (2007); Sharif Mansouri (2014)])

3.3 A new design of LFSR

Definition 1: Let S is a output sequence of LFSR, thenis a power reversible sequence whenandorand, whereis the output of LFSR at ithclock cycle.

From example 1, the following power reversible sequence was gotten

From sequence (2), the connection polynomial by BM algorithm [Massey (1969)] was gained:

And the linear recurrence relation of equation is

Therefore, the new design of LFSR against the power attack was proposed. In the design,adding two additional flip-flop and a new LFSR with length n+2 was required (see Fig. 4).

Figure 4: The new design of LFSR against the power attack

The statistical results using the new design to implement LFSR with length 8 are shown in Tab. 3, Fig. 5 and Fig. 6.

Figure 5: Statistical figure of the new design LFSR with state changes

Figure 6: Statistical figure of the new design with CoutZtO and the difference of CoutZtO

Table 3: Statistical results of the new design

3.4 Improvement of the design

In the design, the power consumption was masked. For confusing the power consumption,the improvement design with an additional filter function, whose inputs are taps of LFSRs, to control the power consumption of the leftmost flip-flop was proposed (see Fig. 7).

Figure 7: The improvement design of LFSR (only the upper half) with additional filter function

For example, the Boolean function g(x) was selected,

Figure 8: Statistical figure of the improvement design with CoutZtO and the difference of CoutZtO

4 Conclusions

Stream ciphers based on LFSR have received frequent usage in the wide range of constrained environments. The power attack is one of the serious threaten for the security of stream ciphers. The new design of LFSR basing on power model of LFSR was proposed by using the mask method. The capability of LFSR against the power attack has been improved due to the power trace has been masked and confused. The new design can be carriedd out easily by circuits. Since only XOR gates and flip-flops are adapted,the better synchronization performance has been achieved, which made the new LFSR suitable for wider usage in different situations.

Acknowledgement:This work is supported by Colleges and universities in Hebei province science and technology research project (Grant No. ZD2016020).