septembre  2002  –  SÉcurité  des  Communications  sur  Internet–  SECI02

The Alternating Step(r, s) Generator

A. A. Kanso^{1}

1: King Fahd University of Petroleum and Minerals

P. O. Box 2440, Hail, Saudi Arabia

                                                              akanso@hotmail.com

Abstract

A new construction of a pseudo-random generator based on a simple combination of three feedback shift registers (FSRs) is introduced. The main characteristic of its structure is that the output of one of the three FSRs controls the clocking of the other two FSRs. This construction allows users to generate a large family of sequences using the same initial states and the same feedback functions of the three combined FSRs. The construction is related to the Alternating Step Generator that is a special case of this construction. The period, and the lower and upper bound of the linear complexity of the output sequences of the construction whose control FSR generates a de Bruijn sequence and the other two FSRs generate m-sequences are established. Furthermore, it is established that the distribution of short patterns in these output sequences occur equally likely and that they are secure against correlation attacks. All these properties make it a suitable cryptogenerator for stream cipher applications.

Keywords. Feedback Shift Registers, Stream Ciphers, Clock-Controlled Registers, Alternating Step Generator.

1. Introduction

A k-stage feedback shift register (FSR) is a device that generates binary sequences.

An FSR is made up of two parts: a shift register S, and a feedback function Q. The shift register S consists of k stages S_{0}, S_{1}, ..., S_{k−1} which contains one bit 0 or 1. The contents of these stages at a given time t is known as the state of the register S and is denoted by: \underline{S}_{t} = S_{0}(t), S_{1}(t), ..., S_{k−1}(t). (Where at time t = 0 the state \underline{S}_{0} = S_{0}(0), S_{1}(0), ..., S_{k−1}(0) is called the initial state of S).

The feedback function Q is a function that maps the state of the register S to the bit 0 or 1. At time t, Q(S_{0}(t), ...., S_{k−1}(t)) = 0 or 1.

The shift register S is clocked at a time interval, when this happens the contents of S are shifted one bit to the left (i.e., the content of S_{i} is transferred into S_{i−1}(i = 1, 2, .., k − 1)) and the new content of S_{k−1} is computed by applying the feedback function Q to the old contents of S.

The above can be expressed as follows:

\{ \begin{matrix}S_{i}(t + 1) & = & S_{i+1}(t) & for i = 0, 1, ..., k − 2 \\ S_{k−1}(t + 1) & = & Q(S_{0}(t), ...., S_{k−1}(t)) \end{matrix}

The binary sequence (S_{t}) generated by this device is the sequence of contents of the 0^{th} stage S_{0} of S for all t (i.e., the binary sequence (S_{t}) = S_{0}, S_{1}, S_{2}, ...... where S_{t} = S_{0}(t) ∈ GF (2) for t = 0, 1, 2, ...).

The state sequence of this device is given by the sequence of states of the register S:

(\underline{S}_{t}) = \underline{S}_{0}, \underline{S}_{1}, .....

Kanso

29 where \underline{S}_{t} = S_{0}(t), ..., S_{k−1}(t) for t = 0, 1, 2, ...

Since the output sequence of a feedback shift register is the content of the 0^{th} stage of the register then clearly each of the output sequence (S_{t}) and the state sequence (\underline{S}_{t}) determine the other.

If the feedback function Q of a feedback shift register can be written in the form: Q(S_{0}(t), ..., S_{k−1}(t)) = (C_{0}S_{0}(t) ⊕ ... ⊕ C_{k−1}S_{k−1}(t)) for a given time t, for some binary constants C_{0}, C_{1}, ..., C_{k−1} called the feedback coefficients, then the shift register is called linear, where ⊕ denotes addition modulo 2.

The feedback coefficients C_{0}, ..., C_{k−1} determine a polynomial C_{0} ⊕ C_{1}x^{1} ⊕ ... ⊕ C_{k−1}x^{k−1} ⊕ x^{k} of degree k associated with the feedback function Q. We write μ(x) to denote this polynomial and call it the characteristic feedback polynomial of the linear feedback shift register.

Any k-stage linear feedback shift register can be uniquely described by a characteristic feedback polynomial μ(x) over the finite field of order 2 of the form: μ(x) = C_{0} ⊕ C_{1}x^{1} ⊕ ... ⊕ C_{k−1}x^{k−1} ⊕ x^{k}.

1.1. Construction

Keystream sequence generators that produce sequences with large periods, high linear complexities and good statistical properties are very useful as building blocks for stream cipher applications. The use of clockcontrolled generators in keystream generators appears to be a good way of achieving sequences with these properties [1].

In this paper, a new clock-controlled generator that is called the Alternating Step(r, s) Generator (and referred to as ASG(r, s)) is introduced. The ASG(r, s) is a sequence generator composed of three FSRs A, B and C [2] which are interconnected such that B is clocked by the constant integer r and C is not clocked if the content of the 0^{th} stage of A is 1, otherwise, B is not clocked and C is clocked by the constant integer s. FSR A is called the control register and FSRs B and C are called the generating registers. The output bits of the ASG(r, s) are produced by adding modulo 2 the output bits of FSRs B andC under the control of FSR A.

Suppose that the control register FSR A has k stages and feedback function R. Similarly, suppose that the generating registers FSRs B and C have m and n stages respectively and feedback functions S and T respectively. Let \underline{A}_{0} = A_{0}(0), A_{1}(0), ..., A_{k−1}(0), \underline{B}_{0} = B_{0}(0), B_{1}(0), ..., B_{m−1}(0) and \underline{C}_{0} = C_{0}(0), C_{1}(0), ..., C_{n−1}(0) be the initial states of A, B and C respectively.

The initial state of the ASG(r, s) at time t = 0 is given by: \underline{S}_{0} = (\underline{A}_{0}, \underline{B}_{0}, \underline{C}_{0}).

Define a function F that acts on the state of FSR A at a given time t to determine the number of times FSR B or FSR C is clocked such that: at any time t, F (\underline{A}_{t}) = rA_{0}(t) + s(A_{0}(t) ⊕ 1).

Define two cumulative functions of FSR A, G_{A} and Q_{A}: {0, 1, 2, ...} → {0, 1, 2, ...} such that:

G_{A}(t) = ∑_{i=0}^{t−1} A_{0}(i)F (\underline{A}_{i}) = r ∑_{i=0}^{t−1} A_{0}(i), for t > 0, and G_{A}(0) = 0,

and

Q_{A}(t) = ∑_{i=0}^{t−1}(A_{0}(i) ⊕ 1)F (\underline{A}_{i}) = s ∑_{i=0}^{t−1}(A_{0}(i) ⊕ 1), for t > 0, and Q_{A}(0) = 0.

Thus, with initial state \underline{S}_{0} = (\underline{A}_{0}, \underline{B}_{0}, \underline{C}_{0}), at time t the state of the ASG(r, s) is given by: \underline{S}_{t} = (\underline{A}_{t}, \underline{B}_{G_{A}(t)}, \underline{C}_{Q_{A}(t)}).

At any time t, the output of the ASG(r, s) is the content of the 0^{th} stage of B added modulo 2 to the content of the 0^{th} stage of C, i.e., B_{0}(G_{A}(t)) ⊕ C_{0}(Q_{A}(t)).

The ASG(r, s) may also be described in terms of the three output sequences (A_{t}), (B_{t}) and (C_{t}) of the feedback shift registers A, B and C respectively.

The Alternating Step(r, s) Generator

Acting on their own, suppose that FSR A, FSR B and FSR C produce output sequences (A_{t}) = A_{0}, A_{1}, ..., (B_{t}) = B_{0}, B_{1}, ..., and (C_{t}) = C_{0}, C_{1}, ... respectively. The sequence (A_{t}) is called the control sequence, and the sequences (B_{t}) and (C_{t}) are called the generating sequences of the ASG(r, s) respectively and referred to as component sequences.

The output sequence (Z_{t}) of the ASG(r, s) whose control and generating sequences are (A_{t}), (B_{t}) and (C_{t}) respectively is given by: Z_{t} = B_{G_{A}(t)} ⊕ C_{Q_{A}(t)} where:

G_{A}(t) = r ∑_{i=0}^{t−1} A_{i} and Q_{A}(t) = s ∑_{i=0}^{t−1}(A_{i} ⊕ 1), for t > 0, and G_{A}(0) = Q_{A}(0) = 0.

2. Properties of the Output Sequence (Z_{t}) of the ASG(r, s)

Suppose that A is an FSR with initial state \underline{A}_{0} and feedback function R such that the output sequence (A_{t}) of A is a de Bruijn sequence of span κ and it has period K = 2^{κ} [2]. Suppose that the feedback shift registers B and C are primitive linear feedback shift registers (LFSRs) with non-zero initial states \underline{B}_{0} and \underline{C}_{0} respectively, and primitive characteristic feedback polynomials g(x) of degree m and h(x) of degree n respectively (where g(x) and h(x) are associated with the feedback functions S and T respectively) [2]. Let (B_{t}) and (C_{t}) denote the output sequences of LFSRs B and C respectively. Then (B_{t}) and (C_{t}) are m-sequences of periods M = (2^{m} − 1) and N = (2^{n} − 1) respectively [2]. Let (Z_{t}) be the output sequence of the ASG(r, s) whose component sequences are (A_{t}), (B_{t}) and (C_{t}).

Note that a de Bruijn sequence of span κ can be easily obtained from an m-sequence generated by a κ-stage primitive LFSR by simply adding a 0 to the end of each subsequence of (κ−1) 0s occurring in the m-sequence.

In a full period K = 2^{κ} of (A_{t}) the number of ones and zeroes is K_{1} = K_{0} = 2^{κ−1} [2]. Thus, after clocking FSR A K times, LFSR B is clocked G_{A}(K) = r2^{κ−1} times and LFSR C is clocked Q_{A}(K) = s2^{κ−1} times.

In this section, some properties of the output sequences such as period and linear complexity are established. It is shown that, when m and n are positive integers greater than 1 satisfying gcd(m, n) = 1, and r and s satisfy gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, then the period of the output sequences is exponential in κ, m and n, and that the linear complexity is exponential in κ. Finally, it is established that the distribution of short patterns in the output sequences of this ASG(r, s) turns out to be ideal.

2.1. Period and Linear Complexity of (Z_{t})

The output sequence (Z_{t}) can be seen as two sequences added modulo 2, (Z_{t}) = (B_{G_{A}(t)}) ⊕ (C_{Q_{A}(t)}), where (B_{G_{A}(t)}) and (C_{Q_{A}(t)}) are generated by the sub-generators whose component sequences are (A_{t}), (B_{t}) and (A_{t}), (C_{t}) respectively.

In order to establish the period and the linear complexity of (Z_{t}) one needs to first consider the periods and the linear complexities of the two sequences (B_{G_{A}(t)}) and (C_{Q_{A}(t)}).

In the following two lemmas, the periods of the sequences (B_{G_{A}(t)}) and (C_{Q_{A}(t)}) are considered. Tretter [3] has considered this proof for the output sequences of the stop and go generator [4]. His proof is also valid for the sequences (B_{G_{A}(t)}) and (C_{Q_{A}(t)}).

Lemma 1 If gcd(r, 2^{m} − 1) = 1, then the period P_{G} of the sequence (B_{G_{A}(t)}) is 2^{κ}(2^{m} − 1).

Proof. The sequence (B_{G_{A}(t)}) will repeat whenever the states of the shift registers A and B return to their initial states \underline{A}_{0} and \underline{B}_{0} respectively. The register A returns to its initial state once every K = 2^{κ} clock pulses. Thus, for λ cycles of register A, register B is clocked λG_{A}(K) times.

Therefore, if for some integers U and λ, λG_{A}(K) = UM, then the feedback shift registers A and B will simultaneously be in their initial states. The period of the sequence (B_{G_{A}(t)}) corresponds to the smallest integer value that the integer U can take.

Now U = λG_{A}(K)/M. Therefore, if gcd(G_{A}(K), M) = 1 i.e., gcd(r2^{κ−1}, 2^{m}−1) = 1, then the smallest value that U can take is when λ = M. Clearly gcd(2^{κ−1}, 2^{m} − 1) = 1, hence, if gcd(r, 2^{m} − 1) = 1 then gcd(G_{A}(K), M) = 1.

Thus, in M cycles of register A, register B cycles G_{A}(K) times and the period of (B_{G_{A}(t)}) is KM = 2^{κ}(2^{m} − 1).

Lemma 2 If gcd(s, 2^{n} − 1) = 1, then the period P_{Q} of the sequence (C_{Q_{A}(t)}) is 2^{κ}(2^{n} − 1).

Proof. Similar to the proof of the above lemma.

Definition 3 The linear complexity of a purely periodic sequence is equal to the degree of its minimal polynomial. The minimal polynomial is the characteristic feedback polynomial of the shortest LFSR that can produce the given sequence.

In the following two lemmas, the minimal polynomials of (B_{G_{A}(t)}) and (C_{Q_{A}(t)}) are considered.

Lemma 4 If gcd(r, 2^{m} − 1) = 1, then the minimal polynomial of the sequence (B_{G_{A}(t)}) is of the form I(x)^{α} where 2^{κ−1} < α ≤ 2^{κ} and I(x) is an irreducible polynomial of degree m. In particular, the linear complexity of (B_{G_{A}(t)}) is L_{1} such that: m2^{κ−1} < L_{1} ≤ m2^{κ}.

Proof. First, recall that if gcd(r, 2^{m} − 1) = 1 then gcd(G_{A}(K), M) = gcd(r2^{κ} − 1, 2^{m} − 1) = 1.

Upper Bound on L_{1}: If one starts at location i in the sequence (B_{G_{A}(t)}) for a fixed value of i with 0 ≤ i < K and chooses every K^{th} element in the sequence (B_{G_{A}(t)}), then this is equivalent to starting at position t = G_{A}(i) in (B_{t}) and choosing every G_{A}(K)^{th} element. Such a sequence is a G_{A}(K)-decimation of (B_{t}). All the G_{A}(K)-decimation of (B_{t}) have the same minimal polynomial I(x) whose roots are the G_{A}(K)^{th} powers of the roots of g(x) [5]. The final sequence (B_{G_{A}(t)}) consists of K such sequences interleaved. (In other words, if (B_{G_{A}(t)}) is written by rows into an array K columns wide, then each column is a sequence produced by I(x)). Hence, the sequence (B_{G_{A}(t)}) may be produced by an LFSR constructed as follows [6].

Take an LFSR with feedback polynomial I(x) and replace each delay by a chain of K delays and only the left most of each such group of K delays is tapped and input to the feedback function with a non-zero feedback coefficient. Thus, (B_{G_{A}(t)}) is produced by an LFSR with the feedback polynomial I(x^{K}). Hence, the minimal polynomial of (B_{G_{A}(t)}) divides I(x^{K}) = I(x^{2^{κ}}) = I(x)^{2^{κ}}. Hence, (B_{G_{A}(t)}) has linear complexity L_{1} bounded from above by mK = m2^{κ}.

Furthermore, Chambers [6] has shown that, if g(x) is irreducible, with degree m and exponent M and gcd(G_{A}(K), M) = 1, then the polynomial I(x), like g(x) is irreducible of degree m and exponent M.

Lower Bound on L_{1}: Let Q(x) denote the minimal polynomial of (B_{G_{A}(t)}). The sequence (B_{G_{A}(t)}) satisfies I(E)^{2^{κ}}(B_{G_{A}(t)}) = (0) for all t, where (0) is the all-zero sequence and E is the shift operator. Since the polynomial I(x) is irreducible then the polynomial Q(x) must be of the form I(x)^{α} for α ≤ 2^{κ}.

Assume α ≤ 2^{κ−1}. Then Q(x) divides I(x)^{2^{κ−1}}. Since I(x) is an irreducible polynomial of degree m it divides the polynomial (1 + x^{M}). Therefore, Q(x) divides (1 + x^{M})^{2^{κ−1}} = (1 + x^{2^{κ−1}M}), but then the period of (B_{G_{A}(t)}) is at most 2^{κ−1}M [5] contradicting lemma 1. Therefore α > 2^{κ−1} and the lower bound follows.

Lemma 5 If gcd(s, 2^{n} − 1) = 1, then the minimal polynomial of the sequence (C_{Q_{A}(t)}) is of the form J(x)^{β} where 2^{κ−1} < β ≤ 2^{κ} and J(x) is an irreducible polynomial of degree n. In particular, the linear complexity of (C_{Q_{A}(t)}) is L_{2} such that: n2^{κ−1} < L_{2} ≤ n2^{κ}.

Proof. Similar to the proof of the above lemma.

Therefore, if gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1 then the periods of (B_{G_{A}(t)}) and (C_{Q_{A}(t)}) are P_{G} = 2^{κ}(2^{m} − 1) and P_{Q} = 2^{κ}(2^{n} − 1) respectively and the minimal polynomials of (B_{G_{A}(t)}) and (C_{Q_{A}(t)}) are equal to I(x)^{α} and J(x)^{β} respectively where 2^{κ−1} < α, β ≤ 2^{κ} and I(x), J(x) are irreducible polynomials of degree m and n respectively.

Theorem 6 If m, n are positive integers greater than 1 satisfying gcd(m, n) = 1 and r, s satisfy gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, then the output sequence (Z_{t}) has period P_{Z} = 2^{κ}(2^{m} − 1)(2^{n} − 1) and linear complexity L such that: (m + n)2^{κ−1} < L ≤ (m + n)2^{κ}.

Proof. From the above lemmas, the minimal polynomials of (B_{G_{A}(t)}) is I(x)^{α} and that of (C_{Q_{A}(t)}) is J(x)^{β} where 2^{κ−1} < α, β ≤ 2^{κ}. Since I(x) and J(x) are irreducible of different degrees then gcd(I(x), J(x)) = 1, hence gcd(I(x)^{α}, J(x)^{β}) = 1 [5]. Therefore, the period of (Z_{t}) is P_{Z} = lcm(P_{G}, P_{Q}) [5, theorem 3.9] and the minimal polynomial of (Z_{t}) is I(x)^{α}J(x)^{β} of degree L = (mα + nβ) [5, theorem 6.57].

Hence, the period of (Z_{t}) is P_{Z} = lcm(2^{κ}(2^{m} −1), 2^{κ}(2^{n} −1)) = {[2^{κ}(2^{m} −1)(2^{n} −1)]/(2^{gcd(m,n)} −1)} [7, lemma 5.9]. Thus, the period of (Z_{t}) is P_{Z} = 2^{κ}(2^{m} − 1)(2^{n} − 1), and the linear complexity of (Z_{t}) is L such that: (m + n)2^{κ−1} < L ≤ (m + n)2^{κ}.

2.2. The Statistical Properties of (Z_{t})

In this section, the number of ones and zeroes in a full period P_{Z} = 2^{κ}(2^{m} − 1)(2^{n} − 1) of the sequence (Z_{t}) are counted. It also shown that when m and n are positive integers greater than 1 satisfying gcd(m, n) = 1 and the positive integers r and s satisfy gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, then any pattern of length q ≤ min(ψ, δ) where ψ, δ are positive integers such that ψ = ⌊(m − 1)/r + 1⌋ and δ = ⌊(n − 1)/s + 1⌋ occurs with probability 2^{−q} + O(1/2^{m−q}) + O(1/2^{n−q}), where ⌊W ⌋ is the integer part of W for any real number W.

Since (B_{t}) and (C_{t}) are m-sequences then in a full period M = (2^{m} − 1) of (B_{t}) the number of ones and zeroes is M_{1} = 2^{m−1} and M_{0} = (2^{m−1} − 1) respectively, and in a full period N = (2^{n} − 1) of (C_{t}) the number of ones and zeroes is N_{1} = 2^{n−1} and N_{0} = (2^{n−1} − 1) respectively [2].

If the period of (Z_{t}) attains its maximum value P_{Z} = 2^{κ}(2^{m}−1)(2^{n}−1), then it is obvious that the number of ones and zeroes in a full period of (Z_{t}) is 2^{κ}[(2^{m} − 1)2^{n−1} − 2^{m−1}] and 2^{κ}[(2^{m} − 1)2^{n−1} − (2^{m−1} − 1)] respectively.

In the following theorem, similar techniques to the ones used by Gunther [8] are applied to determine the distribution of short patterns in the output sequences of the ASG(r, s).

Theorem 7 Let m, n be positive integers greater than 1 satisfying gcd(m, n) = 1 and let r, s satisfy gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1. Let ψ and δ be positive integers such that ψ = ⌊(m − 1)/r + 1 ⌋ and δ = ⌊(n − 1)/s + 1⌋.

The probability of occurrence of any pattern σ = (σ_{0}, σ_{1}, ...., σ_{q−1}) ∈ {0, 1}^{q} of length q ≤ min(ψ, δ) in the sequence (Z_{t}) is 2^{−q} up to an error of order O(1/2^{m−q}) + O(1/2^{n−q}).

Proof. The proof is given in the appendix.

Clearly, the smaller the values for r and s compared to m and n are, the better the above result is. This does not mean that it is suggested to take r and s to be very small, for example r = s = 1. For more security it is better to irregularly clock the generating registers by large values, so that the gap between the bits selected from the generating sequences is large.

Experiments have shown that if gcd(m, n) = 1, then for any values of r and s satisfying gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, the output sequences of the ASG(r, s) have good statistical properties.

Therefore, when m and n are positive integers greater than 1 satisfying gcd(m, n) = 1 and r, s satisfy gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, then an ASG(r, s) with a de Bruijn sequence as the control sequence and m-sequences as the generating sequences generates sequences with period P_{Z} = 2^{κ}(2^{m} − 1)(2^{n} − 1), linear complexity L such that (m + n)2^{κ−1} < L ≤ (m + n)2^{κ}, and these sequences have good statistical properties.

In practice, one can choose r and s to be powers of 2 in which case gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1. In the following section, some correlation attacks on the ASG(r, s) are considered.

3. Attacks

A suitable stream cipher should be resistant against a “known-plaintext” attack. In a known-plaintext attack the cryptanalyst is given a plaintext and the corresponding cipher-text (in another word, the cryptanalyst is given a keystream), and the task is to reproduce the keystream somehow.

The most important general attacks on LFSR-based stream ciphers are correlation attacks. Basically, if a cryptanalyst can in some way detect a correlation between the known output sequence and the output of one individual LFSR, this can be used in a divide and conquer attack on the individual LFSR [9, 10, 11, 12].

The output sequence of the ASG(r, s) is an addition modulo 2 of its two irregularly decimated generating sequences (B_{G_{A}(t)}) and (C_{Q_{A}(t)}). Thus, one would not expect a strong correlation to be obtained efficiently, especially, if primitive feedback polynomials of high Hamming weight are associated with the feedback functions of the registers B and C [11], and the values of r and s which are used to clock the generating registers are considered as part of the key (i.e., r and s are kept secret).

If the characteristic feedback functions of A, B and C are known then a cryptanalyst can exhaustively search for initial state of A, each such state can be expanded to a prefix of the control sequence (A_{t}) using the characteristic feedback function of A. Suppose that one expands the sequence (A_{t}) until its p^{th} 1 and 0 are produced where p = max(m, n). From this prefix, and from the knowledge of a corresponding p-long prefix of the output sequence of (Z_{t}), one can derive the value of p non-consecutive bits of the generating sequences (B_{t}) and (C_{t}) using the following relation:

Z_{t} ⊕ Z_{t+1} = \{ \begin{matrix}B_{G_{A}(t)} ⊕ B_{G_{A}(t+1)} & if A_{t} = 1, \\ C_{Q_{A}(t)} ⊕ C_{Q_{A}(t+1)} & if A_{t} = 0. \end{matrix}

Since the characteristic feedback functions of B and C are known, then the initial states of B and C can be revealed given these non-consecutive p-bits of (B_{t}) and (C_{t}) respectively by solving a system of linear equations, but first one has to reveal the values of r and s in order to determine the locations of these non consecutive p-bits in (B_{t}) and (C_{t}). Therefore, the attack takes approximately O(Φ2^{κ}m^{3}n^{3}) steps where Φ = Φ_{1}Φ_{2}, Φ_{1} is the number of possible values for r such that gcd(r, 2^{m} − 1) = 1 and Φ_{2} is the number of possible values for s such that gcd(s, 2^{n} − 1) = 1.

The probability of two random numbers being relatively primes is 60.8% [13]. Thus, Φ_{1} ≈ 2^{m−1} and Φ_{2} ≈ 2^{n−1}, and the above attack takes approximately O(2^{κ+m+n−2}m^{3}n^{3}) steps.

For κ ≈ 64, m ≈ 64 and n ≈ 64, the attack takes approximately O(2^{226}) steps. Thus, this ASG(r, s) appears to be secure against this attack. Moreover, it appears to be secure against all correlation attacks introduced in [9, 10,11,12,14, 15, 16, 17,18,19].

There is also another attack that can be applied to the ASG(r, s) through the linear complexity, but this attack requires (m + n)2^{κ} consecutive bits of the output sequence.

For maximum security, the ASG(r, s) should be used with secret initial states, secret characteristic feedback functions, secret r, s satisfying gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, and m, n greater than 1 satisfying gcd(m, n) = 1. Subject to these constraints, an ASG(r, s) with κ ≈ 64, m ≈ 64 and n ≈ 64 appears to be secure against all presently known attacks.

4. Related Work

An interesting example of existing FSR-based construction for comparison with the ASG(r, s) is the Alternating Step Generator (ASG) of Gunther [8].

The ASG is a special case of the ASG(r, s); it is actually an ASG(1, 1). Although the ASG(r, s) is slower than the ASG, its advantage is that it provides more security. For an ASG with κ ≈ l, m ≈ l and n ≈ l, if the characteristic feedback functions of A, B and C are known, then in order to reveal the initial states of the three registers the attack mentioned in section 3 takes approximately O(2^{l}l^{6}) steps, whereas for the ASG(r, s), the attack takes approximately O(Φ2^{l}l^{6}) steps. Moreover, for the ASG in order to produce a new sequence, one has to choose a new initial state and/or a new characteristic feedback function for at least one of the FSRs, whereas for the ASG(r, s) in order to produce a new sequence, it suffices to assign new value(s) for r and/or s.

5. Conclusion

From the theoretical results established, it is concluded that an ASG(r, s) whose control FSR generates a de Bruijn sequence and generating FSRs generate m-sequences produces sequences with large periods, high linear complexities, good statistical properties, and they are secure against correlation attacks. Furthermore, using the same initial states and the same characteristic feedback functions, the ASG(r, s) produces a new sequence each time one assigns new value(s) for r and/or s. These characteristics and properties enhance its use as a suitable crypto-generator for stream cipher applications.

Acknowledgement

I would like to thank Prof. Peter Wild for his helpful comments.

References

[1] D. Gollmann and W. Chambers. Clock-controlled shift register: A review. IEEE Journal on Selected Areas in Communications, vol. 7, no. 4, May 1989, pp. 525–533.

[2] S. W. Golomb. Shift Register Sequences. Aegean Park Press, 1982.

[3] Steven A. Tretter. Properties of PN2 sequences. IEEE Transactions on Information Theory, vol. IT-20, March 1974, pp. 295–297.

[4] T. Beth and F. Piper. The stop and go generator. In Advances in Cryptology: Proceedings of EuroCrypt 84, Lecture Notes in Computer Science, Berlin: Springer-Verlag 1985, vol. 209, pp. 88–92.

[5] R. Lidl, H. Niederreiter. Introduction to Finite Fields and Their Applications. Cambridge University Press, 1986.

[6] W. Chambers. Clock-controlled shift registers in binary sequence generators. IEE Proceedings E, vol. 135, Jan 1988, pp. 17–24.

[7] R. Ruppell. Analysis and Design of Stream Ciphers. Berlin, Heidelberg, New York: Springer-Verlag, 1986.

[8] C. G. Gunther. Alternating step generators controlled by de Bruijn sequences. In Advances in Cryptology: Proceedings of EuroCrypt 87, Lecture Notes in Computer Science, Berlin: Springer-Verlag, vol. 309, 1988, pp. 5–14.

[9] J. Golic, M. Mihaljevic. A generalized correlation attack on a class of stream ciphers based on the Levenstein distance. Journal of Cryptology, vol. 3, 1991, pp. 201–212.

[10] J.Golic. Towards fast correlation attacks on irregularly clocked shift registers. In Advances in Cryptology: Proceedings of EuroCrypt 95, Lecture Notes in Computer Science, Berlin: Springer-Verlag, vol. 921, 1995, pp. 248–262.

[11] W. Meir, O. Staffelbach. Fast correlation attacks on certain stream ciphers. Journal of Cryptology, vol. 1, 1989, pp. 159–176.

[12] T. Siegenthaler. Correlation-immunity of non-linear combining functions for cryptographic applications. IEEE Transactions On Information Theory, vol. IT-30, no. 5, 1984, pp.776–779.

[13] www.utm.edu/research/primes/notes/relprimr.html.

[14] J. Golic. On the security of shift register based keystream generators. In R. Anderson, Editor, Fast Software Encryption, Cambridge Security Workshop, Lecture Notes in Computer Science, Berlin: Springer-Verlag, vol. 809, 1994, pp. 90–100.

[15] T. Johansson. Reduced complexity correlation attacks on two clock-controlled generators. In Advances of Cryptology: Proceedings of AsiaCrypt 98, Berlin: Lecture Notes in Computer Science, vol. 1514, 1998, pp. 342–356.

[16] M. Mihaljevic. An approach to the initial state reconstruction of a clock-controlled shift register based on a novel distance measure. In Advances in Cryptology: AusCrypt 92, Berlin: Lecture Notes in Computer Science, vol. 178, 1993, pp. 349–356.

[17] J. Golic, L. O’Connor. Embedding probabilistic correlation attacks on clock-controlled shift registers. In Advances in Cryptology: EuroCrypt 94, Berlin: Lecture Notes in Computer Science, vol. 950, 1995, pp. 230–243.

[18] T. Johansson, F.Jonsson. Improved fast correlation attacks on certain stream ciphers via convolutional codes. In Advances in Cryptology: EuroCrypt 99, Berlin: Lecture Notes in Computer Science, vol. 1592, Springer-Verlag, 1999, pp. 347–362.

[19] T. Johansson, F.Jonsson. Fast correlation attacks through reconstruction of linear polynomials. In Advances in Cryptology: Crypto 2000, Berlin: Lecture Notes in Computer Science, vol. 1880, Springer-Verlag, 2000, pp. 300–315.

A. Proof of Theorem 7

Proof. Since gcd(m, n) = 1 and gcd(r, 2^{m} − 1) = gcd(s, 2^{n} − 1) = 1, then the period of (Z_{t}) P_{Z} = 2^{κ}(2^{m} − 1)(2^{n} − 1).

Let t ∈ {0, 1, .., P_{Z−1}} be represented in the form t = u + (v + yM)2^{κ}, u ∈ {0, 1, .., K − 1}, v ∈ {0, 1, .., M−1}, y ∈ {0, 1, .., N−1} and let us first consider the frequency of patterns among subsequences Z_{t}, Z_{t+1}, ...., Z_{t+q−1} for a fixed u ∈ {0, 1, ...., K − 1}.

Let ρ = ρ(u) and θ = θ(u) be defined by:

ρ_{0} = 0  (1)
θ_{0} = σ_{0}
ρ_{i+1} = ρ_{i} ⊕ A_{u+i}(σ_{i+1} ⊕ σ_{i})
θ_{i+1} = θ_{i} ⊕ (1 ⊕ A_{u+i})(σ_{i+1} ⊕ σ_{i})

for i ∈ {0, 1, ..., q − 2}.

Then σ can be written as

σ_{i} = ρ_{i} ⊕ θ_{i}  (2)

for i ∈ {0, 1, ..., q − 1}.

The matching condition at time t is:

Z_{t+i} = σ_{i}  (3)

for i ∈ {0, 1, ..., q − 1}.

This is equivalent to:

B_{G_{A}(t+i)} ⊕ C_{Q_{A(t+i)}} = ρ_{i} ⊕ θ_{i}  (4)

for i ∈ {0, 1, ..., q − 1}.

Using the following relations:

G_{A}(u + i + 1) = G_{A}(u + i) + rA_{i}  (5)
Q_{A}(u + i + 1) = Q_{A}(u + i) + s(A_{i} ⊕ 1)

the sum of Equation (4) and of the corresponding equation for (i + 1) becomes:

B_{G_{A}(t+i+1)} ⊕ B_{G_{A}(t+i)} = ρ_{i+1} ⊕ ρ_{i}  (6)
C_{Q_{A}(t+i+1)} ⊕ C_{Q_{A}(t+i)} = θ_{i+1} ⊕ θ_{i}

since, when A_{i} = 1, θ_{i+1} ⊕ θ_{i} = C_{Q_{A}(t+i+1)} ⊕ C_{Q_{A}(t+i)} = 0, and when A_{i} = 0, ρ_{i+1} ⊕ ρ_{i} = B_{G_{A}(t+i+1)} ⊕ B_{G_{A}(t+i)} = 0.

This has two solutions:

B_{G_{A}(t+i)} = ρ_{i}  (7)
C_{Q_{A}(t+i)} = θ_{i}

and

B_{G_{A}(t+i)} = 1 ⊕ ρ_{i}  (8)
C_{Q_{A}(t+i)} = 1 ⊕ θ_{i}

for i ∈ {0, 1, ..., q − 1}.

The number of solutions to this equation is equal to the number of occurrences of the pattern σ in the sequence (Z_{t}) (where t = u + (v + yM)2^{κ}, v ∈ {0, 1, .., M − 1}, y ∈ {0, 1, .., N − 1}), i.e., to the quantity we want to determine.

Without restricting ourselves we consider the solution of Equation (7). Making use of the fact that K = 2^{κ} and that G_{A}(K) = r2^{κ−1} and Q_{A}(K) = s2^{κ−1}, this equation becomes:

B_{G_{A}(u+i)+vr2^{κ−1}} = ρ_{i}  (9)

where i ∈ {0, 1, .., q − 1}. (The term yM is omitted since (B_{t}) has period M.)

C_{Q_{A}(u+i)+(v+yM)s2^{κ−1}} = θ_{i}  (10)

Let φ(u) = [G_{A}(u + q − 1) − G_{A}(u)]/r which is less than m since q ≤ min(ψ, δ) where ψ = ⌊(m − 1)/r + 1⌋ and δ = ⌊(n − 1)/s + 1⌋ , then the assumptions that (B_{t}) is an m-sequence imply that Equation (9) has 2^{m−φ(u)−1} solutions if ρ ≠ 0.

Let κ(u) = [Q_{A}(u + q − 1) − Q_{A}(u)]/s, then similarly, (C_{t}) is an m-sequence and gcd(m, n) = 1 imply that Equation (10) has 2^{n−κ(u)−1} solutions if θ ≠ 0.

This remains true for ρ = 0 and/or θ = 0 if we accept an error at most O(1/2^{m−q}) + O(1/2^{n−q}). Note that φ(u) + κ(u) = (q − 1).

Clearly, the same result also holds for Equation (8). Hence, the total number of solutions to Equation (3) is:

2(2^{m−φ(u)−1})(2^{n−κ(u)−1}) = 2^{m+n−q}

which is independent of u.

This finally implies that the frequency of the pattern σ is given by:

\frac{2^{m+n−q}}{MN} + O(1/2^{m−q}) + O(1/2^{n−q})

Therefore, in a full period of (Z_{t}) any pattern of length q ≤ min(ψ, δ) occurs with a probability (1/2^{q}) + O(1/2^{m−q}) + O(1/2^{n−q}).