LFSR-based Stream Ciphers
In order to minimize the size of the internal state, stream ciphers dedicated to low-cost hard- ware implementations may use a linear transition function. Among all such possibilities, linear feedback shift registers (LFSRs) offer several advantages including their performance, their implementation cost and many theoretical results on the statistical properties of the produced sequences. LFSR-based generators are then probably the most commonly studied class of keystream generators. This class includes both hardware-oriented stream ciphers and software-oriented ciphers, but this second type of applications usually relies on non-binary LF- SRs, operating on a larger alphabet (e.g. on 32-bit words). The most widely used LFSR-based stream ciphers include E0 (used in the Bluetooth standard), A5/1 used for encrypting the over- the-air communications in the GSM cellular telephone standard, SNOW 2.0 (ISO/IEC 18033-4 standard) and its variant SNOW 3G used in UMTS 3G networks.
In most practical LFSR-based generators used nowadays, the internal state is divided into two parts: one is updated linearly by an LFSR, and the other one is updated with a nonlinear function in order to prevent the main attacks exploiting the linearity of the transition function. This nonlinear part may be small (and seen as a nonlinear memory) as in E0 or SNOW 2.0, or both parts of the internal state may be of equal size, like in MUGI or Grain.
3.1 Main properties of LFSRs
Copyright By PowCoder代写 加微信 powcoder
3.1.1 Definitions
An LFSR of length L over Fq is a finite state automaton which produces a semi-infinite sequence of elements of Fq, s = (st)t≥0, satisfying a linear recurrence relation of degree L over Fq
st+L = cist+L−i, ∀t ≥ 0 .
The L coefficients c1,…,cL are elements of Fq. They are called the feedback coefficients of the LFSR.
The Fibonacci representation of an LFSR of length L over Fq has the form depicted on Figure 3.1. The register consists of L delay cells, called stages, each containing an element of Fq. The contents of the L stages, st,…,st+L−1, form the state of the LFSR. The L stages are initially loaded with L elements, s0, . . . , sL−1, which can be arbitrary chosen in Fq; they form the initial state of the register.
Chapter 3.
– – … –
c1 c2 cL−1 cL
LFSR-based Stream Ciphers
– – output
? ?
+++
Figure 3.1: Fibonacci representation of an LFSR of length L.
The shift register is controlled by an external clock. At each time unit, each digit is shifted one stage to the right. The content of the rightmost stage st is output. The new content of the leftmost stage is the feedback bit, st+L. It is obtained by a linear combination of the contents of the register stages, where the coefficients of the linear combination are given by the feedback coefficients of the LFSR:
st+L =cist+L−i .
Therefore, the LFSR implements the linear recurrence relation of degree L:
st+L = cist+L−i, ∀t ≥ 0 .
Example 3.1. A binary LFSR of length 4. Table 3.1 gives the successive states of the binary LFSR of length 4 with feedback coefficients c1 = c2 = 0, c3 = c4 = 1 and with initial state (s0, s1, s2, s3) = (1, 0, 1, 1). This LFSR is depicted in Figure 3.2. It corresponds to the linear recurrence relation
st+4 = st+1 + st mod 2 .
The output sequence s0s1 . . . generated by this LFSR is 1011100 . . ..
Figure 3.2: Binary LFSR with feedback coefficients (c1, c2, c3, c4) = (0, 0, 1, 1) —–
Feedback polynomial and characteristic polynomial. The output sequence of an LFSR is uniquely determined by its feedback coefficients and its initial state. The feedback coef- ficients c1, . . . , cL of an LFSR of length L are usually represented by the LFSR feedback polynomial (or connection polynomial) defined by
L P(X)=1−ciXi .
Error-Correcting Codes and Symmetric Cryptography – A. Canteaut 45 Table 3.1: Successive states of the LFSR with feedback coefficients (c1, c2, c3, c4) = (0, 0, 1, 1)
and with initial state (s0, s1, s2, s3) = (1, 0, 1, 1)
t 0123456789101112131415
st 1011110001001101
st+1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0
st+2 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1
st+3 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1
Alternatively, one can use the characteristic polynomial, which is the reciprocal polynomial of the feedback polynomial:
L P⋆(X)=XLP(1/X)=XL−ciXL−i .
For instance, the feedback polynomial of the binary LFSR shown in Figure 3.2 is P(X) =
1 + X3 + X4 and its characteristic polynomial is P ⋆(X) = 1 + X + X4.
Non-singular LFSRs. An LFSR is said to be non-singular if the degree of its feedback polynomial is equal to the LFSR length (i.e., if the feedback coefficient cL differs from 0). In this case, the transition function of the LFSR is bijective. Any sequence generated by a non-singular LFSR of length L is periodic, and its period does not exceed qL − 1. Indeed, the LFSR has at most qL different states and the all-zero state is always followed by the all-zero state. Moreover, if the LFSR is singular, all generated sequences are ultimately periodic, i.e., the sequences obtained by ignoring a certain number of elements at the beginning are periodic.
3.1.2 Characterization of LFSR output sequences
A given LFSR of length L over Fq can generate qL different sequences corresponding to the qL different initial states and these sequences form a vector space over Fq. The set of all sequences generated by an LFSR with feedback polynomial P is characterized by the following property [Zie59].
Theorem 3.1. A sequence (st)t≥0 is generated by an LFSR of length L over Fq with feedback polynomial P if and only if there exists a polynomial Q ∈ Fq[X] with deg(Q) < L such that the generating function of (st)t≥0 satisfies
stXt = Q(X) . t≥0 P(X)
Moreover, the polynomial Q is completely determined by the coefficients of P and by the initial state of the LFSR:
L−1k Q(X) = − Xj skcj−k ,
where P(X) = −Li=0 ciXi.
46 Chapter 3. LFSR-based Stream Ciphers
L∞∞j
for all j ≥ L.
skcj−k=0
−ciXi stXt = Xj − skcj−k
Therefore, we deduce that
j=0 k=max(0,j−L)
L−1j ∞j
− Xj skcj−k + Xj j=0 k=0 j=L
skcj−k .
L∞ Q(X) = − ciXi stXt
is a polynomial of degree strictly less than L if and only if the second right-hand term vanishes,
This result, which is called the fundamental identity of formal power series of linear re- curring sequences, means that there is a one-to-one correspondence between the sequences generated by an LFSR of length L with feedback polynomial P and the fractions Q(X)/P(X) with deg(Q) < L. It has two major consequences. On the first hand, any sequence generated by an LFSR with feedback polynomial P is also generated by any LFSR whose feedback poly- nomial is a multiple of P. This property is widely used for attacking LFSR-based generators (e.g., in distinguishing attacks, and in fast correlation attacks). It may also be helpful since some multiple of the feedback polynomial may provide more appropriate representations in some contexts.
Example 3.2. Let s be a binary sequence satisfying
st+6 =st+4 +st+3 +st+1 +st, ∀t≥6.
The corresponding feedback polynomial is then P (X) = 1 + X2 + X3 + X5 + X6. It then follows that s also satisfies
st+8 = st+7 + st
since 1+X +X8 = (1+X2 +X3 +X5 +X6)(1+X +X2). This alternative recursion may
then have a lower implementation cost because of its sparsity.
On the other hand, Theorem 3.1 implies that a sequence generated by an LFSR with feedback polynomial P is also generated by a shorter LFSR with feedback polynomial P′ if the corresponding fraction Q(X)/P(X) is such that gcd(P,Q) ̸= 1. Thus, amongst all sequences generated by the LFSR with feedback polynomial P, there is one which can be generated by a shorter LFSR if and only if P is not irreducible over Fq. This leads to the following natural notion of minimal polynomial.
Error-Correcting Codes and Symmetric Cryptography - A. Canteaut 47 Definition 3.2. For any linear recurring sequence (st)t≥0, there exists a unique polynomial
P0 with constant term equal to 1, such that the generating function of (st)t≥0 is given by stXt = Q0(X)/P0(X)
where P0 and Q0 are relatively prime.
Then, the shortest LFSR which generates (st)t≥0 has length L = max(deg(P0), deg(Q0) +
1), and its feedback polynomial is equal to P0. The reciprocal polynomial of P0, XLP0(1/X), is the characteristic polynomial of the shortest LFSR which generates (st)t≥0; it is called the minimal polynomial of the sequence.
The minimal polynomial of a linear recurring sequence then determines the linear recur- rence relation of least degree satisfied by the sequence.
Example 3.3. The binary LFSR of length 10 depicted in Figure 3.3 has feedback polynomial P(X)=1+X+X3+X4+X7+X10 ,
and its initial state s0 . . . s9 is 1001001001.
Figure 3.3: Example of a LFSR of length 10.
-1-0-0-1-0-0-1-0-0-1 -
hhh h ++++
The generating function of the sequence produced by this LFSR is given by
stXt = Q(X) t≥0 P(X)
where Q is deduced from the coefficients of P and from the initial state: Q(X)=1+X+X7 .
Therefore, we have
t 1+X+X7 1
stX = 1+X+X3 +X4 +X7 +X10 = 1+X3 ,
since 1+X +X3 +X4 +X7 +X10 = (1+X +X7)(1+X3) in F2[X]. This implies that (st)t≥0 is also generated by the LFSR with feedback polynomial P0(X) = 1 + X3 depicted in Figure 3.4. The minimal polynomial of the sequence is then 1 + X3.
Obviously, in all cryptographic applications, the feedback polynomials of LFSRs are always chosen irreducible.
48 Chapter 3. LFSR-based Stream Ciphers Figure 3.4: LFSR of length 3 which generates the same sequence as the LFSR in Figure 3.3
3.1.3 Period of a linear recurring sequence
Another important role played by the minimal polynomial is that it determines the period of a linear recurring sequence.
Proposition 3.3. The least period of a linear recurring sequence is equal to the order of its minimal polynomial P0, i.e., to the least positive integer e for which P0(X) divides Xe + 1.
For instance, the sequence studied in Example 3.3 has minimal polynomial X3 +1. Then, it has period 3. On the other hand, any non-zero sequence generated by the LFSR of length 4 depicted in Figure 3.2 has period 24 − 1 = 15. Indeed, the minimal polynomial of any such sequence corresponds to its characteristic polynomial P0(X) = 1 + X + X4, because P0 is irreducible.
We directly deduce from Proposition 3.3 that a sequence has maximal period 2deg P0 − 1 if and only if P0 is a primitive polynomial. The sequences produced by an LFSR with primitive feedback polynomial are called maximal-length sequences (m-sequences).
3.1.4 Statistical properties of m-sequences
Maximum-length sequences, i.e., the linear recurring sequences produced by an LFSR with primitive feedback polynomial, possess several good statistical properties which make them appropriate building-blocks in keystream generators.
For instance, any binary sequence produced by an LFSR of length L with primitive feed- back polynomial satisfy the following properties. The first three properties are called Golomb’s randomness postulates [Gol82].
• Balance property: The difference between the number of ones and the number of zeroes in any window of 2L − 1 consecutive bits is equal to 1:
#{i, st0+i =1, 0≤i<2L −1}−#{i, st0+i =0, 0≤i<2L −1}=1.
• Runs: a run is a set of consecutive zeroes flanked by ones, or of consecutive ones flanked by zeroes. For instance, the sequence 0100011 has a run of zeroes of length 3. The proportion of runs of length i within any frame of (2L − 1) consecutive bits of an m- sequence is 2−i, 0 ≤ i < L. Moreover, among all runs of length i, i ≤ L − 2, the number of runs of zeroes and the number of runs of ones are equal. There is exactly one run of length (L − 1) and one run of length L (see Example 3.4).
• Two-level auto-correlation: The autocorrelation of a binary sequence of period N is defined by
C(τ) = (−1)st+st+τ mod (2L−1) .
Error-Correcting Codes and Symmetric Cryptography - A. Canteaut 49 C(τ) then measures the distance between the sequence s0s1 ...s2L−2 and the sequence
obtained by shifting it by τ positions, i.e., sτsτ+1 ...sτ−1. Indeed, we have C(τ)=2L −1−2#{t, st ̸=st+τ mod(2L−1),0≤t<2L −1}.
In particular, C(τ) = 2L − 1 if and only if τ is a multiple of the period of the sequence since the two sequences are identical. For any m-sequence generated by an LFSR with primitive feedback polynomial of degree L, we have that, if τ is not a multiple of (2L −1), then C(τ) = −1. This means that the sequence is as far as possible from its shifted versions. This property is widely used in telecommunications for synchronization.
• Multigram property: the L-tuple stst+1 . . . st+L−1 takes all the 2L − 1 nonzero values when t varies between 0 and (2L − 2).
Some additional properties of m-sequences are detailed in [Hel11].
Example 3.4. Let us consider the first 31 bits of the binary sequence produced by the LFSR
of length 5 with primitive feedback polynomial X5 + X3 + 1 from initial state 10000: 1000010101110110001111100110100
It can be checked that this sequence consists of 16 ones and 15 zeroes. It then satisfies the balance property.
The sequence has 16 runs: 8 runs of length 1 (4 runs of zeroes and 4 runs of ones), 4 runs of length 2 (2 runs of zeroes and 2 runs of ones), 2 runs of length 3 (1 run of zeroes and 1 run of ones), one run of zeroes of length 4 and one run of ones of length 5.
3.1.5 LFSR and multiplication in a finite field
The operation performed by a q-ary LFSR of length L with irreducible feedback polynomial corresponds to a multiplication in the finite field FqL .
Proposition 3.4. Let P⋆ be an irreducible polynomial in Fq[X] with degree L. Let α ∈ FqL be a root of P⋆ and {β0,...,βL−1} denote the dual basis of {1,α,...,αL−1}, i.e.,
i 0 ifi̸=i Tr(αβj)= 1 ifi=j ,
where Tr denotes the trace function from FqL into Fq.
Then, the content of the LFSR with characteristic polynomial P ⋆ at time (t + 1) is equal
to its content at time t multiplied by α, where these vectors are identified with elements in the field FqL decomposed on the basis {β0, . . . , βL−1}.
Proof. For any t, we identify an L-tuple (x0, . . . , xL−1) with an element in the finite field FqL by
x = xL−1βn−1 + . . . + x0β0 .
Then, by definition of the dual basis, we have that, for any 0 ≤ i < L,
Tr(αix) = Tr(xjαiβj)
= xjTr(αiβj)=xi. j=0
50 Chapter 3. LFSR-based Stream Ciphers This means that the i-th coordinate of x in the basis {β0, . . . , βL−1} is equal to Tr(αix). Let
us now compute the coordinates of y = αx in this basis. The i-th coordinate of y is given by
Tr(αiy) = Tr(αi+1x) .
It follows that the i-th coordinate of y is equal to the (i + 1)-th coordinate of x if i < L − 1. For i = L − 1, the last coordinate of y is given by
Tr(αL−1y) = Tr(αLx) L
= Tr ciαL−ix i=1
= ciTr(αL−ix) = cixL−i ,
where the characteristic polynomial is given by P⋆(X) = XL − Li=1 ciXL−i, implying that αL = Li=1 ciαL−i. It follows that the coordinates of y = αx correspond to the content after one clock of the LFSR initialized by x. ⋄
Galois representation. Since an LFSR with irreducible feedback polynomial is a device which implements the multiplication by an element α in a finite field, some alternate auto- morphism between the FqL and FLq may be used without modifying the transition function over FqL. Another natural representation is obtained when the basis {1,α,α2,...,αL−1} is usedforrepresentingtheelementsinFqL insteadofthedualbasis{β0,...,βL−1}.Thisrepre- sentation is called the Galois representation, and corresponds to the “natural” multiplication circuit, i.e., the multiplication in the so-called polynomial basis. The Galois representation corresponding to the Fibonacci LFSR depicted on Figure 3.1 is given in Figure 3.5.
Figure 3.5: Galois representation of the LFSR depicted on Figure 3.1.
- -+l- -+l- - -+l- -
cL−1 cL−2 c1
It is worth noticing that Fibonacci and Galois representations have different features. For instance, the Galois representation is obviously more efficient in software than the Fibonacci representation. Also, the diffusion within the register in the Galois representation is faster.
3.2 Linear complexity and LFSR synthesis
A fundamental quantity for a sequence is its linear complexity since it determines the smallest linear recursion satisfied by the sequence, or equivalently the length of the smallest LFSR generating the sequence.
Error-Correcting Codes and Symmetric Cryptography - A. Canteaut 51
Definition 3.5. The linear complexity of a semi-infinite sequence s = (st)t≥0 of elements of Fq, Λ(s), is the smallest integer Λ such that s can be generated by an LFSR of length Λ over Fq, and is ∞ if no such LFSR exists. By way of convention, the linear complexity of the all- zero sequence is equal to 0. The linear complexity of a linear recurring sequence corresponds to the degree of its minimal polynomial.
The linear complexity Λ(sn) of a finite sequence sn = s0s1 . . . sn−1 of n elements of Fq is the length of the shortest LFSR which produces sn as its first n output terms for some initial state.
The linear complexity of an infinite linear recurring sequence s and the linear complexity of the finite sequence sn composed of the first n digits of s are related by the following property: if s is an infinite linear recurring sequence with linear complexity Λ, then the finite sequence sn has linear complexity Λ for any n ≥ 2Λ [Mas69]. Moreover, the unique LFSR of length Λ that generates s is the unique LFSR of length Λ that generates sn for every n ≥ 2Λ.
3.2.1 Linear complexity as a statistical test
For a sequence s = s0s1 . . ., the sequence of the linear complexities (Λ(sn))n≥1 of all sub- sequences sn = s0 . . . sn−1 composed of the first n terms of s is called the linear complexity profile of s.
Proposition 3.6. [Rue86, Page 40] The expected linear complexity of a binary sequence sn = s0 . . . sn−1 of n independent and uniformly distributed binary random variables is
n n 4 + ε(n) −n n 2 E[Λ(s )] = 2 + 18 + 2 3 + 9 ,
where ε(n) = n mod 2.
Therefore, it may be possible to distinguish a sequence from a truly random sequence by computing its linear complexity profile and comparing the result to what is expected from Proposition 3.6. Further results on the linear complexity and on the linear complexity profile of random sequences can be found in [Rue86].
3.2.2 Berlekamp-Massey algorithm
The Berlekamp-Massey algorithm is an algorithm for determining the linear complexity of a finite sequence and the feedback polynomial of an LFSR of minimal length which generates this sequence. This algorithm is due to Massey [Mas69], who showed that the iterative algorithm proposed in 1967 by Berlekamp [Ber68] for decoding BCH codes can be used for finding the shortest LFSR that generates a given sequence. Given sequence sn of length n, the Berlekamp- Massey performs n iterations. The t-th iteration determines an LFSR of minimal length which generates the first t digits of sn. The algorithm is described in Algorithm 7. In the particular case of a binary sequence, the quantity d′ does not need to be stored since it is always equal to 1. Moreover, the feedback polynomial is simply updated by
P(X)←P(X)+P′(X)Xt−m .
The number of operations performed for computing the linear complexity of a sequence of length n is O(n2). It can be proved that the Berlekamp-Massey algorithm and the Euclidean algorithm are essentially the same [Dor87].
52 Chapter 3. LFSR-based Stream Ciphers
Algorithm 7 The Berlekamp-Massey algorithm.
Input: sn = s0s1 . . . sn−1, a sequence of n elements of Fq.
Output: Λ, the linear complexity of sn and P, the feedback polynomial of an LFSR of length Λ which generates sn.
/* Initialization */
P(X)←1,P′(X)←1,Λ←0,m←−1,d′ ←1.
/* Algorithm */
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com