A Survey of Recent Attacks on the Filter Generator
The filter generator consists of a linear feedback shift register (LFSR) and a Boolean filtering function that combines bits from the shift register to create a key stream. The nonlinear combiner generator employs several (LFSRs) and a Boolean function th
- PDF / 394,624 Bytes
- 11 Pages / 430 x 660 pts Page_size
- 112 Downloads / 205 Views
The Selmer Center, Department of Informatics, University of Bergen, PB 7803 N-5020 Bergen, Norway 2 Department of Electrical and Computer Engineering University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Abstract. The filter generator consists of a linear feedback shift register (LFSR) and a Boolean filtering function that combines bits from the shift register to create a key stream. The nonlinear combiner generator employs several (LFSRs) and a Boolean function that combines bit from all the registers to generate the key stream. A new attack on the filter generator has recently been described by Rønjom and Helleseth who also extended the attack to linear feedback shift registers over an extension field GF (2m ). Some extensions and improvements of the attacks to the filter generator have been given by Rønjom, Gong and Helleseth. The purpose of this paper is to give a short overview of these attacks and to discuss how to extend these attacks to the nonlinear combiner generator. Keywords: Boolean function, filter generator, nonlinear combiner generator, m-sequences, stream ciphers.
1
Introduction
The binary filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register of length n that generates a maximal linear sequence {st } (an m-sequence) of period 2n − 1 and a Boolean function of degree d that combines bits from the shift register and produces an output bit zt at any time t. An illustration of the filter generator is shown in Figure 1. The sequence {st } obeys the recursion n
cj st+j = 0, cj ∈ {0, 1}
j=0
n j where c0 = cn = 1. The characteristic polynomial g(x) = j=0 cj x , of the n linear recursion, is a primitive polynomial of degree n and period 2 − 1. The i zeros of g(x) are α2 for i = 0, 1, . . . , n − 1, where α is a primitive element in n GF (2 ), the finite field with 2n elements. The m-sequence can be written as st = T r1n (βαt ) n−1 i where β ∈ GF (2n ) and T r1n (x) = i=0 x2 . S. Bozta¸s and H.F. Lu (Eds.): AAECC 2007, LNCS 4851, pp. 7–17, 2007. c Springer-Verlag Berlin Heidelberg 2007
(1)
8
S. Rønjom, G. Gong, and T. Helleseth
s t+n
LFSR
F
zt
Fig. 1. Filter generator
The sequence {st } is determined by the initial state (s0 , s1 , . . . , sn−1 ) and the characteristic polynomial g(x). The 2n sequences generated by g(x), corresponding to the different initial states, form a vector space over GF (2) denoted by Ω(g(x)). For further information on linear shift registers the reader is referred to the recent book by Golomb and Gong [2]. By repeated use of the recursion we can write st as a linear combination of the n bits in the initial state. Thus, we have st =
n−1
si lit
(2)
i=0
for n binary sequences {lit } for i = 0, 1, . . . , n − 1. Note that each of these n sequences are nonzero and obey the same recursion as {st } and thus are msequences. At each time t, a keystream bit zt is calculated as a function of certain bits in some positions (e0 , e1 , . . . , em−1 ) in the LFSR state (st , st+1 , . . . , st+n−1 ) at
Data Loading...
