Stream Cipher Design based on Jumping

Stream Cipher Design based on Jumping Finite State Machines Cees J.A. Jansen∗ Banksys NV, Brussels, Belgium cja@iae.nl August 11, 2005 Abstract This paper presents a new way of constructing binary cascade clock-controlled LFSR sequence generators as building blocks for stream ciphers. In these con- structions the bottleneck of multiple clocking shift registers is removed, result- ing in so called jump-controlled sequence generators, that operate in a single clock pulse and are most efficient to implement. The constructions make use of special properties of irreducible polynomials over finite fields. This paper also aims at giving insight into the mathematical theory behind the constructions. To this end, theory is developed and many of the rich set of properties of irre- ducible polynomials over GF (2), such as periods, jump indices and the number and cardinalities of various classes of polynomials are presented. Keywords: LFSR, finite state machine, sequence generation, clock-control, irreducible polynomial, transition matrix, jump index, dual polynomial. 1 Introduction Today stream ciphers are widely used in areas where the combination of security, performance and implementation complexity is of importance. One such area is wire- less communications (GSM, 3GPP, Bluetooth, IEEE802.11), where a low gate count in hardware or DSP platform implementation requirements prevail. Another area is highspeed link encryption where encryption rates of tens of gigabits per second are quite common. Although many streamcipher algorithms have been broken, a number of secure stream ciphers still exist and new initiatives like the European ECRYPT STVL stream cipher project, [5] are proposed. In stream cipher cryptography a well known construction for generating complex sequences is based on cascading clock controlled feedback shift registers. With this method (see e.g. [13]) subsequent linear FSRs are clocked, i.e. stepped through their ∗J.v. Riebeeckstraat 10, 5684 EJ Best, The Netherlands 1 state space, by a previous LFSR output one or more times before using the corre- sponding output bit. Due to the multiple clocking feature, this construction generally results in a decreased rate of sequence generation, rendering it less attractive for high speed implementations. The more general problem of finding an efficient way to let an autonomous linear finite state machine make one big step, i.e. moving to a state more than one step further, without having to traverse consecutive intermediate states, motivated the research of which the results are presented here in detail. Several parts of these results were presented earlier at RECSI VII, [9], and at SASC 2004, [10], but this paper is an extended version containing proofs of theorems. A paper from the author describing some extensions to general finite fields appeared in [11]. Stream cipher proposals based on the theory of this paper, were submitted in April 2005 to the ECRYPT stream cipher call [18, 15]. In Section 2 some basic notation and theory is introduced. Section 3 discusses a new way of effectively multiple clocking binary Linear Finite State Machines, which makes use of a property of the associated irreducible characteristic polynomial denoted by the name Jump Index. Also, an additional involution operation on polynomials is introduced, which characterizes the natural multiple clocking (or jumping) behaviour of LFSMs. Additional conditions for LFSMs with clock-controlled jumps are given in Section 4. In Section 5 sets of binary irreducible polynomials are defined, containing sets of 1, 2, 3 and 6 polynomials which are related by alternate application of the two different operators. The existence conditions of these sets and the cardinalities of the classes of sets for given degrees are presented. Section 6 discusses the generalisation of the theory developed in the previous sections to composite polynomials. Finally, we conclude in Section 7. 2 Linear Feedback Shift Register Basics si si+1 si+n−1s ff Mn−1 Mn−2 M0 mm mcn c1 - ? ?m m+ +- ff Figure 1: The Linear Feedback Shift Register Linear feedback shift registers are widely used in sequence generators for crypto- graphic purposes. They implement in a very natural way a linear recurrence relation between the individual sequence symbols generated. A figure of an LFSR over GF (q) is shown in Figure 1. The sequence s = (. . . , si, si+1, . . .) satisfies the linear recurrence 2 relation (1) of order n. sj+n = n∑ i=1 cisj+n−i ⇐⇒ n∑ i=0 cisj+n−i = 0, with c0 = −1 (1) The feedback coefficients ci are usually written as a so called Feedback Polynomial (sometimes called Connection Polynomial), F (x), of degree equal to the length of the recursion n, as given by (2). Feedback Polynomial F (x) := n∑ i=0 cix i (2) The nth order linear recursion is commonly represented by its Characteristic Polyno- mial, C(x), also of degree n, as given by (3). Characteristic Polynomial C(x) := n∑ i=0 cix n−i (3) Polynomials F and C are each others reciprocals, i.e. the roots of F (x) are the recip- rocals of the roots of C(x). This relation is commonly expressed as C(x) = xnF (x−1) or vice versa. Some authors take −ci as feedback coefficients, whence c0 = 1 resulting in a monic characteristic polynomial, see e.g. [4, pg. 26]. It is customary to consider only the monic version of the Feedback Polynomial, i.e. c−1n F (x). In general the order n of the recursion need not be minimal, meaning that there may be another recursion of order less than n, which the generated sequence satisfies. The minimal order recursion of a sequence gives rise to the so called Minimal Poly- nomial M(x) of s. This minimal polynomial is unique and divides the characteristic polynomial C(x) (see e.g. [12, pp. 418–423,102]). The roots of C(x) form solutions of the recursion equation. Another way to look at the LFSR is to consider it as a Linear Finite State Machine. In this case the state of the LFSM is represented by a vector σt = (σtn−1, σ t n−2, . . . , σ t 0), where σti denotes the content of memory cell Mi after t transitions. As the finite state machine is linear, transitions from one state to the next can be described by a multiplication of the state vector with a transition matrix T , i.e. σt+1 = σtT , for t ≥ 0. The transition matrix is given by (4) for the LFSR of Figure 1. T =  0 0 · · · 0 cn 1 0 · · · 0 cn−1 0 1 · · · 0 cn−2 ... ... . . . ... ... 0 0 · · · 1 c1  (4) It can be seen that the matrix is equal to the so called companion matrix (see e.g. [12, pp. 67–68,102]) of the polynomial xn − c1xn−1 − · · · − cn−1x − cn = C(x). The characteristic polynomial of T in the linear algebra sense, i.e. det(xI − T ), precisely equals this polynomial and, hence, C(T ) = 0. So the companion matrix plays the 3 role of a root of C and, consequently, can be used to form solutions of the recursion equation. Several authors use slightly different definitions of a companion matrix, depending on the use of column or row vector representation and the shift direction of the LFSR as can be seen in [7, pg. 35] and [17, pg. 132]. In Section 3 we will have a closer look at companion matrices of polynomials. From the foregoing it can be concluded that multiple clocking of an LFSR in fact comes down to multiplying the state vector with some power of the transition matrix. A new transition matrix can be constructed by raising the original matrix to some power and rewiring the LFSR accordingly. Strictly speaking this results in a LFSM which need not be a shift register. Also, switching between the two transition matrices, as is needed for cascade clock control is easily achieved by means of a switch for every memory cell. This method is used in many stream cipher implementations, for instance in the Jansen-Roelse Synchronous Stream Cipher [6], which is used for streaming data protection. However, there exists a more efficient way to implement the conditional multiple clocking of LFSRs as will be shown in the next section. 3 Jumping: a natural way of multiple clocking In the remainder of this paper we will focus on the binary case, although many results obtained in this paper have been generalized in a rather straightforward manner to GF (q), see [11] LetA denote the transition matrix of an autonomous Linear Finite State Machine, not necessarily a shift register, and let f(x) denote its characteristic polynomial, i.e. f(x) = det(xI+A). The principal question we ask ourselves here is if it is possible in general to find a power of the transition matrix, which is equal to a linear combination of the matrix raised to two smaller powers: At = At1 + At2 , with t1, t2 < t. The simplest useful case is the one where there exists a J , such thatAJ = A+I. If indeed such a power of the transition matrix exists, we clearly achieve the same effect if we multiply the state vector either by AJ or by A+I. Moreover, changing A into A+I is generally much simpler than rewiring A into AJ for an arbitrary transition matrix A. Also, this modification of the transition matrix is an involution, which makes it easier to assess the relevant properties for a practical implementation, in which the transformation and its inverse are needed. As is well known, if f(x) is irreducible then A can be written as the companion matrix of f(x) by applying a suitable matrix multiplication,A′ =MAM−1, which is always possible; see e.g. [17, 1]. The matrices A and A′ are called similar matrices. Note that powers of the companion matrix can be seen to represent all elements of the finite field. Hence, an equivalent statement of the problem is to find an element αJ in the finite field GF (2n), with f as defining polynomial and n = deg(f), such that αJ = α + 1, where α is an element of GF (2n). The latter is a special case of Jacobi’s logarithm, [12, pp. 79,542], which is defined for non-zero field elements as αm + αn = αm+L(n−m). In the case at hand, we have n = 1 and m = 0, so that J = L(1). The reader more acquainted with Zech’s logarithms [8], defined as αZ(x) = αx + 1, note that J = Z(1). 4 One can conclude from the foregoing that by changing the transition matrix of the Autonomous LFSM from A into A+ I, effectively J steps through the state space of the original LFSM are made, regardless of the starting state. This jump of J states gives rise to the following definition. Definition 1 Let f(x) be an irreducible polynomial over GF (2). If xJ ≡ x + 1 mod f(x), for some integer J , then J is called the Jump Index of f . The Jump Index does not exist for every irreducible polynomial, as this depends on the condition xJ ≡ x + 1 mod f(x) or equivalently f(x)|(xJ + x + 1) for some J . In other words: αJ = α + 1, where α is a root of f(x) and, hence, an element of the splitting field GF (2n) of f(x). Obviously, it follows that J ≥ deg(f). For irreducible trinomials of the form xn + x + 1 the jump index equals the degree of the trinomial. Also, for primitive polynomials, i.e. irreducible polynomials of maximal order (period) 2n − 1, where n is the degree of f , the jump index always exists. The latter can be seen from the fact that x is a primitive element in this case, so successive powers of x generate all non-zero elements of GF (2n), including the element x+ 1. The Jump Index is an important parameter of irreducible polynomials just as the period is, because both values determine whether the irreducible polynomial can be used as characteristic polynomial of a shift-multiple-shift LFSR (in general a step-or- jump LFSM), as will be seen later. Let f⊥(x) denote the characteristic polynomial of the modified transition matrix, it follows that f⊥(x) = det(xI +A+ I) = det((x+ 1)I +A) = f(x+ 1) (5) We have the following definition. Definition 2 Let f(x) be an irreducible polynomial over GF (2). The dual of f(x), denoted by f⊥(x) is defined as f(x+ 1). We call f⊥(x) the dual of f(x) because (f⊥)⊥ = f((x + 1) + 1) = f(x), which is an involution transformation on polynomials. Moreover, if f(x) has jump index J then the sums of α and αJ for all roots lie in the base field and are equal to 1. The duality operator clearly preserves the degree of the polynomial. The period (or order) of f is not necessarily preserved, as a simple counter example shows: f(x) = x4+x3+1 has period 15, but f⊥(x) = f(x + 1) = x4 + x3 + x2 + x + 1 has period 5. Irreducibility is also preserved as stated in the following theorem: Theorem 1 Let f(x) be an irreducible polynomial over GF (2), then the dual of f(x), f⊥(x) = f(x+ 1) is also irreducible. Proof. Suppose f⊥ = g · h. Then (f⊥)⊥ = g(x + 1)h(x + 1) = g⊥ · h⊥ = f , which contradicts the fact that f is irreducible. 2 5 Clearly, the dual of a reducible polynomial can be defined analogously. This general- ization will be treated in Section 6. Let f ∗(x) denote the reciprocal of f(x), i.e. f ∗(x) = xnf(x−1). The reciprocal of the characteristic polynomial plays an important role, e.g. as the connection polyno- mial of LFSRs as was introduced in the previous section. Taking the reciprocal of a polynomial is also an involution operation, provided the polynomial does not contain x as one of its factors. Therefore, one usually considers polynomials with irreducible factors of degree 2 and higher. This is of particular importance, if one considers the interplay of both operators, as (x+ 1)⊥ = x and x has no reciprocal. A natural question to ask is how the jump indices of a polynomial, its dual and its reciprocal are related. The answer is given by the next theorem: Theorem 2 Let f be an irreducible polynomial of degree n ≥ 2 over GF (2) with jump index J . The jump indices of f⊥ and f ∗, denoted by J⊥ and J∗ respectively, have the following relation to J : J⊥ = J−1 mod per(f) (6) J∗ = 1− J mod per(f) (7) Proof. Let α, α2, . . . , α2 n−1 be the roots of f , then αJ = α + 1. The reciprocal f ∗ has α−1, α−2, . . . , α−2 n−1 as its roots, and so α−J ∗ = α−1 + 1. Multiplying both sides of the latter equation with α gives α1−J ∗ = 1 + α = αJ , hence accounting for (7). Similarly, f⊥ has roots αJ , α2J , . . . , α2 n−1J and so (αJ)J ⊥ = αJ + 1 = α, implying that J · J⊥ ≡ 1 mod per(f). 2 A consequence of (6) is that the jump index of the dual polynomial only exists if J is relatively prime with the period of f . Conversely, if f has a jump index, but f⊥ has not, then gcd(J, per(f)) > 1. In the case that gcd(J, per(f)) = d > 1, αJ has order per(f)/d and so the period of f⊥ will also be per(f)/d. Theorem 2 also implies that if f has a jump index, then so has f ∗. From (7) un upperbound for the jump index is obtained. Together with J ≥ deg(f) this gives the following result. deg(f) ≤ J ≤ 1 + per(f)− deg(f). (8) Example 1 As an example, let us consider the LFSR shown in Figure 2 of length 7 and characteristic polynomial x7+x6+1, which is a primitive polynomial of Mersenne- prime period 127. Its reciprocal has characteristic polynomial x7 + x+ 1 with a jump index of 7, equal to its degree. Hence, the jump index of the original polynomial is 127 + 1− 7 = 121 and the dual polynomial has a jump index of 121−1 mod 127 = 21. The dual of the reciprocal is x7 + x6 + x5 + x4 + x3 + x2 + 1 and has a jump index of 7−1 mod 127 = 109. The modified LFSR with this characteristic polynomial is shown in Figure 3. The impact on shift-multiple-shift sequence generator design of the theory pre- sented in this section should start to become visible. Apparently, by choosing a very 6 s0 s1 s6s ff M6M5 M0 ? - m+ ff Figure 2: LFSR of length 7 and characteristic polynomial x7 + x6 + 1 i i i i i i i+ + + + + + +ff ff ff ff ff ff ffff ff ff ff ff ff? ? ? ? ? ? ?sisff M6 M5 M0 ? - m+ 6 Figure 3: Dual of the Reciprocal: characteristic polynomial x7+x6+x5+x4+x3+x2+1 specific number of multiple shifts, the transition matrix of the LFSR raised to this number will be identical to the transition matrix except for the entries on the main diagonal, which are inverted (ones XORed). Equivalently, by adding ones to the entries on the main diagonal of the transition matrix a number of multiple shifts is obtained, equal to the jump index of the characteristic polynomial of that matrix. The modification of the transition matrix as described here, is of very low com- plexity, adding only one XOR gate for every cell in the LFSR. Moreover, the number of shifts in a jump of the register, caused by this modification is at least as high as the register length, but can be substantially higher in general. Hence, for many application areas, the method described in this section is much more attractive than the method of rewiring. Although the general idea is described in this section, many detailed questions concerning e.g. existence conditions of jump indices of polynomials with non-maximal periods are left unanswered here. The intricate consequences of the non-commuting operators ⊥ and ∗ on sets of dual and reciprocal polynomials is discussed in Section 5. First we will look at clock-controlled LFSR’s in more detail. 4 LFSR’s with clock-controlled jumps A typical clock-controlled binary sequence generator is shown in Figure 4. The first LFSR generates a binary sequence s1 of period p1, which is some divisor of 2 L1 − 1 in the case of an irreducible feedback, where L1 is the length of the LFSR. This sequence, comprising N0 zeroes and N1 ones, is used to clock the second LFSR, i.e. let the second LFSR step through its state space, depending on the bits of the driving sequence by stepping it c0 or c1 times if the output bit is a 0 or a 1 respectively. The total number Ns of steps made by the second LFSR in one period of the first LFSR satisfies Ns = N0c0 +N1c1. Assume that the second LFSR has irreducible feedback. 7 ff ff m+- ff ff m+- s2 s1 @ @I @ @I0: c0 st 1: c1 st ff clock Figure 4: Clock controlled LFSR sequence generator In order for the output sequence s2 of the second LFSR to have a maximal period of p1p2 a necessary condition is that gcd(Ns, p2) = 1. This condition is not sufficient, see [3, Thm 3, pg. 19]. In many situations it is advantageous [19, Ch. 5] to use maximum-length LFSR’s, i.e. LFSR’s of length L having period p = 2L − 1. In this case the numbers of zeroes and ones, given by N0 = p−1 2 and N1 = p+1 2 , have a disparity of 1, caused by the fact that the all-zero state does not occur. The total number of steps is now given by Ns = c0p+(c1−c0)2L−1. Consequently, if the second LFSR has a period p2 equal to p (or one of its divisors), then the necessary condition for maximum s2 period becomes gcd(Ns, p2) = gcd(c1 − c0, p) = 1. (9) This condition can be generalised in the case of more clocking constants. Consider for example the NESSIE proposal LILI-128 [16], which uses four different clocking constants (1,2,3 and 4), based on two different taps of a driving maximum-length LFSR. Let c00, c01, c10 and c11 denote the number of steps if the two taps have values 00, 01, 10 and 11, occurring N00, N01, N10 and N11 times in a period p respectively. Because of the maximum-length sequence N01 = N10 = N11 = p+1 4 and N00 = p − 3p+1 4 = p−3 4 . Hence, Ns = (c01+c10+c11) p+1 4 +c00 p−3 4 = (c01+c10+c11−3c00)2L−2+c00p. The condition for maximum period now becomes gcd(c11+ c10+ c01− 3c00, p) = 1. In LILI-128 this condition does not apply as the LFSR’s have different lengths, but the maximum period condition is trivially satisfied by the fact that p2 = 2 89 − 1, which is a Mersenne prime. In the special case that jumping LFSR’s are used, that either make one step or a jump equivalent to J steps, it is seen that condition (9) can be written as gcd(J − 1, p) = 1, (10) or also gcd(J∗, p) = 1, (11) where (11) follows from (10) by application of (7). In other words: the jump index of the feedback polynomial (of the jumping LFSR) must be relatively prime with its period. 8 5 Classes of binary irreducible polynomials Let f(x) be an irreducible polynomial over GF (2