7 Stream ciphers

In contrast to a block cipher, which regards messages as segmented into datablocks of

a fixed length, a stream cipher has a fixed beginning, but it has no fixed end. A stream
cipher encrypts a plaintext datastream of indefinite length, such as a long bitstream,
which we can regard as an infinite datastream. An infinite stream of plaintext symbols is
fed into an encryptor, using an encryption key of length m bits, and the infinite stream of
ciphertext symbols leaves the encryptor. Later, the infinite stream of ciphertext symbols
enters the decryptor, which uses the same key of length m bits, and the infinite stream
of plaintext symbols leaves the decryptor.
Stream ciphers have a long history, perhaps inspired by the one-time pad, and are
in widespread use in many applications. A common form of stream cipher, called an
additive stream cipher, converts the m-bit key into a semi-infinite binary stream,
called a keystream. The encryptor adds the binary keystream modulo two to the
binary datastream, bit by bit, to form the codestream. The decryptor adds the same
keystream, modulo two, to the codestream, again bit by bit, and in this way recovers the
datastream.
Recall that a binary one-time pad consists of a semi-infinite random sequence of
equiprobable bits that is known to both the encryptor and the decryptor. There is no
constraint on the random binary sequence used as a one-time pad other than that it
be maximally random. This means that the bits of the sequence are independent and
equiprobable.
An additive binary keystream, in practice, is specified by a master key consisting
of a block of m bits. This means that there can be only 2m keystreams in the cipher,
and the block key specifies which of these 2m keystreams is to be used. The goal
when designing a stream cipher is to choose these 2m keystreams so that they appear
to be arbitrary and mimicking randomness, with no evident accessible structure, and
yet are simple to construct from the m-bit key. Although the bits of the keystream are
dependent, this dependence must not be easy to extract.
A binary keystream, itself generated by a key of length m, may also be used in a
different way as a method of sequentially replacing the keys used by an adjacent block
cipher. Simply segment the semi-infinite binary keystream into a sequence of m-bit
blocks, each block now regarded as a new m-bit key for the adjacent block cipher

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 182 Stream ciphers

system. In this way, each block of the data can be block-encrypted with a different key,
or a key that is frequently changed. Although the sequence of such computed keys is
generated by a single initialization of the keystream generator by a master key, one
presumes that the block cipher is further protected because it continually changes its
key.

7.1 State-dependent encryption

To be practical, a stream cipher must be realizable, so the encryptor must have a finite
memory. Therefore, in general, the encryptor is a finite-state machine controlled by
a key. We suppose that the finite memory can hold L symbols taking values in some
finite alphabet A, usually the binary alphabet. The set of the current values of the L
symbols in the memory is called the state of the memory. The state takes its values
in a block alphabet of size (#A)L . For a binary alphabet, the state can take on 2L
values.
For example, the keyed function

yi = ek (xi , xi−1 , xi−2 , . . . , xi−L )

forms a stream cipher with a state memory of length L and an encryption key k. In
this example, the state is equal to the L most recent symbols of the plaintext. The state
memory is simply used to store these L most recent symbols of the plaintext. The
ith symbol of the ciphertext is computed directly from these L stored symbols of the
plaintext. This kind of encryptor is called a feedforward encryptor, the name referring
to the fact that the window on the past, from i to i − L, moves forward as i increases,
and past plaintext symbols are eventually discarded by the encryptor. The encryption
of the current symbol is not affected by the plaintext symbols that are older than the L
most recent symbols.
More generally, let the memory at time i hold the state vector, defined as
(s1(i) , s2(i) , . . . , sL(i) ) = s(i) . At each i, the new state is computed from the current state
history and the new input symbol. Then the finite-state machine is described as

yi = ek (xi , s(i−1) )
s(i) = f (xi , s(i−1) ).

Even more generally, the function f that updates the state may also depend on the key
k. Then the encryptor, as a finite-state machine, is described as follows:

yi = ek (xi , s(i−1) )
s(i) = fk (xi , s(i−1) ).

The general form of an encryptor for a steam cipher is shown in Figure 7.1.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 183 7.2 Additive stream ciphers

State State
x1 memory memory x1

Plaintext
Encryptor Channel Decryptor
source y1 y1
1 1

k k

Figure 7.1 State-dependent encryption

The decryptor has a similar structure. It is described as a finite-state machine as

follows:

xi = dk (yi , s (i−1) )
s (i) = fk (xi , s (i−1) ).

Notice that in the decryptor the function defining the state s (i) is the same as in the
encryptor. Moreover, the plaintext symbol xi is recovered without reference to the new
state s (i) . All of the values needed by the decryptor to compute the new state s (i) are
then available after the plaintext symbol xi is computed.
One method of forming a state-dependent encryptor for a stream cipher is to
use a block encryptor as the core of the encryptor, augmented by simple exter-
nal operations that turn the block encryptor into a stream encryptor. For exam-
ple, as was discussed in Section 6.4, let y = ek (x) denote a block encryption
function on blocks of length n. Let x  , for  = 1, . . ., denote a series of data
blocks, each of length n. Then define a stream encryption as the stream of blocks
y = ek (x  + y−1 ), starting with any specified initial block y0 . Thus each ciphertext
block is added to the next plaintext block prior to block encryption. The ciphertext
blocks are concatenated to form the ciphertext message. The stream decryption is
x  = dk ( y ) + y−1 , which removes the previous ciphertext block after each block is
decrypted.

7.2 Additive stream ciphers

A simple and widely used stream cipher is the additive stream cipher, which is a special
case of a stream cipher. An additive stream cipher is sometimes said to be inspired by
Shannon’s one-time pad. A one-time pad requires a semi-infinite, truly random binary
sequence. In contrast, an additive binary stream cipher uses a periodic binary sequence
of very large period that imitates a one-time pad and superficially has the appearance
of a random binary sequence.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 184 Stream ciphers

Keystream Keystream
Key Key Key Key
expansion expansion
1 1

_
Plaintext To
Channel
source + user
1 1
Datastream Codestream
Figure 7.2 Additive keystream cipher

An additive stream cryptography system over the abelian group G encrypts by adding
componentwise an infinite sequence of symbols of G to the plaintext. Thus

yi = xi + zi(k) ,

where the sequence {zi(k) }, called the keystream, is an infinitely long sequence with
symbols from the group G. The binary field, F 2 , which uses modulo-two addition,
usually suffices for G. The keystream to be used is specified by a master block key k
from a set of keys K. There is one such keystream for each master key k ∈ K. If the
keys are m-bit binary numbers, then there are 2m keystreams. The task of key expansion
is to stretch a block key k into a semi-infinite keystream. Although the keystreams are
generated from the master keys deterministically by a finite-state machine, one attempts
to design this process so that the keystreams appear to be maximally random, and so
that the future values of the keystream cannot be predicted from a segment of the past
values of the keystream. Accordingly, such keystreams are often called pseudorandom
keystreams.
An additive keystream cryptographic system is shown in Figure 7.2. To form the
keystream, denoted z(k) , we compute the ith bit by the rule

zi(k) = ek (s(i−1) )
s(i) = fk (s(i−1) ),

where k is the master key, i is the time index, and s(i) is the state vector
(s1(i) , s2(i) , . . . , sL(i) ). The ciphertext is the sequence of bits given by

yi = xi + zi(k) = xi + ek (s (i−1) ) (mod 2).

The additive keystream cipher is a special case of a stream cipher in that fk and ek
do not have the databit xi as an argument, and so the keystream does not depend on
the data. Because there are only #K = 2m keys, there are only 2m keystreams, each of
which is an infinitely long sequence. A practical keystream generator must have finite
complexity, so it uses a finite-state machine to form the infinite keystream. Because a
finite-state machine has only a finite number of states, it must eventually repeat a state.
Once it repeats a state, it must repeat the same history of states following that state.
Thus every keystream generated by a finite-state machine is eventually periodic.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 185 7.3 Linear shift-register sequences

An additive keystream cipher is linear if the sum of the keystream and any cyclic
translate of that keystream is equal to yet some other cyclic translate of the original
keystream. That is, for any , there exists an  such that
zi + z((i+)) = z((i+ ))
for all i, where the double parentheses mean modulo-n indexing and n is the period
of the cyclic sequence. Because linear sequences can be generated by a shift register,
they are called linear shift-register sequences. The theory of linear additive keystreams
begins with the study of linear shift-register sequences.
An additive keystream must be synchronized at the encryptor and decryptor. This
means that the decryption must subtract the keystream symbol zi from the cipher-
text symbol yi . If it subtracts the keystream symbol zi  , for i  = i, then we have the
computation
yi − zi  = xi + zi − zi  ,
which would be unintelligible to the user. This requirement is not unique to additive
keystreams. Any state-dependent stream cipher must be given an initial state, and this
must be synchronized with the first symbol of the keystream. Indeed, synchronization
is always a requirement in any system that communicates digital bitstreams. Even a
block cipher must be properly segmented into blocks for decryption.
While these points may be obvious, what may not be obvious is that the method of
keystream synchronization may possibly provide a vulnerability that could be exploited
by the cryptanalyst, although we have no evidence for this concern. One must always
be wary of secondary functions that support the encryption.

7.3 Linear shift-register sequences

A periodic sequence over F q is an infinite sequence v = (v0 , v1 , v2 , . . .) of field ele-

ments that satisfies vi+n = vi for some integer n, called the period of the sequence. A
shift-register sequence v = (v0 , v1 , . . . , v0 , v1 , . . .) is a periodic sequence of elements
that can be generated by a feedback shift-register circuit. By this broad definition, how-
ever, every periodic sequence would be a shift-register sequence. The term is usually
used to refer only to a periodic sequence that can be generated by a nontrivial feedback
shift-register circuit, whose period is q m − 1 or a divisor of q m − 1 for some value of
m. A feedback shift-register circuit is another name for a kind of recursion.
A shift register is an ordered set of q-ary memory cells, with each cell used to hold
one element of the field. Each cell is updated at each clock cycle by taking its new value
from its leftmost neighbor. The cell at the left end has no neighbor on the left. That
cell takes its new value as a linear combination of the contents of the other cells. This
linear combination is called the feedback. To generate a periodic sequence of period

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 186 Stream ciphers

q m − 1 requires a finite-state machine with at least m memory cells and at most q m − 1

memory cells. A shift-register circuit can be represented as a recursion

vi = f (vi−1 , vi−2 , . . . , vi−L ),

where, for a sequence of period q m − 1, L is at least m and at most q m − 1.
A linear sequence over the field F q is a sequence formed by a shift register whose
feedback is a linear function of the contents of the cells. A maximal linear shift-register
sequence over the field F q is a linear sequence of period q m − 1 formed by a shift
register with only m memory cells. A maximal shift-register sequence is also called an
m-sequence.
We consider only shift-register sequences over the binary field F 2 . A maximal
sequence over F 2 is closely related to an irreducible polynomial over F 2 , and there-
fore related to the field F 2m . A periodic sequence over F 2 of period q m − 1 can
be constructed by using an irreducible polynomial p(x) of degree m over F 2 . The
sequence will have period 2m − 1 if the irreducible polynomial p(x) is required to have
the property that the element x has order 2m − 1 under modulo p(x) arithmetic. This
means that p(x) is a primitive polynomial and the element x is a primitive element of
F 2m . Primitive polynomials and primitive elements are discussed in Chapter 9.
Each nonzero element of F 2m can be represented as an m-bit binary word or as a
power of a primitive element α. This means that there is a unique m-bit binary word
corresponding to α  for each  from zero to 2m − 2. For each , take the high-order
bit of the binary word corresponding to α  to form a sequence of 2m − 1 bits. This
periodic sequence – or any of its cyclic shifts – is an m-sequence. Such an m-sequence
can be constructed from any primitive polynomial. Despite the rigid structure of such
sequences, we will see that they display many properties that one might like to see in
a random sequence.
Let p(x) be a primitive polynomial with the elements of F 2m represented as poly-
nomials in x. Then x = α is a primitive element, and
x m + pm−1 x m−1 + pm−2 x m−2 + · · · + p1 x + p0 = 0

where the coefficients are elements of F 2 . Therefore

x  = pm−1 x −1 + pm−2 x −2 + · · · + p1−m+1 x + p0−m

for  = m, m + 1, . . .. This describes exactly the operation of a linear-feedback shift

register of length m with taps given by p(x). The m-sequence is the sequence of
feedback bits generated by this circuit.
All of the structure of an m-sequence follows easily from the fact that the primitive
element x has order 2m − 1. This requires that, at each of the 2m − 1 steps, the linear-
feedback shift register must hold a different m-bit binary word; otherwise the pattern
would repeat earlier. Each of the 2m − 1 nonzero m-bit binary numbers must appear
exactly once in the shift register. This means that the number of zeros and ones is nearly

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 187 7.3 Linear shift-register sequences

Table 7.1 The cycle of α

α0 = 0 0 0 1
α1 = 0 0 1 0
α2 = 0 1 0 0
α3 = 1 0 0 0
α4 = 0 0 1 1
α5 = 0 1 1 0
α6 = 1 1 0 0
α7 = 1 0 1 1
α8 = 0 1 0 1
α9 = 1 0 1 0
α 10 = 0 1 1 1
α 11 = 1 1 1 0
α 12 = 1 1 1 1
α 13 = 1 1 0 1
α 14 = 1 0 0 1

Figure 7.3 A simple linear-feedback shift register

balanced. Similar reasoning about the high-order r-bit subsequence in the shift register
leads to similar conclusions about all r-bit subsequences for r at most m.
The m-sequence is a linear sequence, meaning that the sum of two cyclic translates
of the sequence is equal to another cyclic translate of the sequence. That is, because
the low-order bit of α i+a and α i+b , satisfy

α i+a + α i+b = α i+c

for some c. The linearity property follows from the field structure because for any a
and b in F q , there is a c in F q such that

αa + αb = αc .

For example, let α be a zero of the primitive polynomial p(x) = x 4 + x + 1. Then

α is a primitive element of F 16 . The shift-register circuit that multiplies by the element
α is shown in Figure 7.3. Table 7.1 shows the orbit of α in F 16 with the elements
expressed in the polynomial basis. The leftmost column of Table 7.1 gives the periodic
sequence 000100110101111. Every other column is a cyclic translate of this column.
This periodic sequence is a linear shift-register sequence.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 188 Stream ciphers

…1110100

Figure 7.4 Generation of an m-sequence of period 7

A maximal sequence emulates many properties of a random sequence. Approxi-

mately half of the bits of a random binary sequence will be ones and approximately
half of the bits will be zeros.1 Similarly, the doublets 00, 01, 10, and 11 each will occur
about one-fourth of the time. Likewise, each 3-bit pattern will occur about one-eighth
of the time, and a similar remark holds for longer multituples not longer than m. The
m-sequence mentioned above satisfies these conditions. Indeed, one might say that it
satisfies the conditions too well. It has seven zeros and eight ones, and when viewed
cyclically, three instances of 00, and four each of 01, 10, and 11; one instance of 000,
and two each of 001, 010, 011, 100, 101, 110, and 111. This is as close to balanced as
is possible for a sequence of period 15.
Another example of linear-feedback shift register is shown in Figure 7.4. The poly-
nomial p(x) = x 3 + x + 1 is a primitive polynomial of degree three. Consequently,
an m-sequence of length seven can be generated using the feedback shift register
of Figure 7.4. When initializing the shift register with x 0 , represented from left to
right as 100, the sequence of generated bits at the output, now from left to right,
is
0 0 1 0 1 1 1 ... ,
which repeats periodically. This is an m-sequence of period seven. Again, the number
of zeros and ones in one period differs by one, which is as nearly equal as is possible for
a sequence of odd blocklength. With the sequence viewed cyclically, the overlapping
2-bit subsequences are 00, 01, 10, 01, 11, 11, 10. Except for the subsequence 00, there
are two sequences of each kind, which is as nearly equal as possible for a sequence of
odd blocklength. The 3-bit subsequences, viewed cyclically, are also balanced; each
appears once except for the subsequence 000.
This behavior holds for any m-sequence. For example, choose a primitive polynomial
p(x) of degree thirty. The m-sequence will have a period of length 230 − 1, or about
109 bits. For each r smaller than thirty, all subsequences of length r except the all-zero
subsequence of length r will occur with equal frequency.
The set of all maximal linear shift-register sequences is the set of sequences that can
be obtained in this way by the choice of the primitive polynomial p(x). The degree m

1 Of course, a sequence is not itself random. This phrasing refers to the selection from an ensemble of sequences.
The sequence is the outcome of this selection.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 189 7.4 The linear-complexity attack

of p(x) determines both the extension field F 2m and the period 2m − 1 of the maximal
sequence. The number of primitive polynomials p(x) of degree m is limited, as will be
counted in Theorem 9.13.5 of Section 9.13, so the number of maximal sequences of
length 2m − 1 is limited as well.

7.4 The linear-complexity attack

The length of the shortest linear recursion that produces the periodic sequence
v = (v0 , v1 , . . . , vn−1 ) is called the linear complexity of the periodic sequence. If the
linear recursion is known, then the entire periodic sequence is known except for the
starting phase. A linear-complexity attack is a partially-known-plaintext attack against
an additive keystream. From any known segment of the keystream, a linear-complexity
attack attempts to compute a linear recursion
L
vi = − k vi−k
k=1

that will produce all of the keystream from that known segment.
Because a known plaintext is easily removed from an additive stream cipher to reveal
the keystream, the linear-complexity attack can be used whenever a sufficiently long
segment of the plaintext is known. The attack first finds the shortest linear recursion
that produces the known segment of the keystream, and then uses that linear recursion
to produce a continuation of the known keystream in the hope that the continuation will
be the entire keystream. This attack will fail if the known segment of the keystream is
too short.
The linear-complexity attack is an attack on the keystream itself, not on the procedure
that generated the keystream. The attack does not inquire how the keystream was
actually generated. The keystream need not have been generated by a linear recursion,
but if it is a periodic sequence, it can always be regarded as having been so generated
by a sufficiently long linear recursion. This is because every periodic sequence over
the field F of period n can be produced by the trivial linear recursion xi = xi−n for
i = n + 1, n + 2, . . .. Thus the linear complexity of every periodic sequence in F of
period n is not larger than n, and often is much smaller.
Neither the linear recursion nor its initial state nor its length L is known prior
to the attack. The unknowns i for i = 1, . . . , L, specify the unknown recursion
and the unknowns vi , for i = 0, . . . , L − 1, determine the unknown initial state.
Both must be determined by the linear-complexity attack when given only a sub-
sequence of 2L consecutive symbols of the keystream. If the linear complexity of the
keystream is indeed at most L, then the recursion gives a system of L linear equa-
tions in the L unknown j . This system of linear equations can be written in matrix

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 190 Stream ciphers

form as
⎡ ⎤ ⎡ ⎤⎡ ⎤
vL+1 vL vL−1 ··· v1 1
⎢ vL+2 ⎥ ⎢vL+1 vL ··· v2 ⎥ ⎢ 2 ⎥
⎢ ⎥ ⎢ ⎥⎢ ⎥
⎢ . ⎥ = ⎢. .. ⎥⎢ . ⎥ ,
⎣ . ⎦ ⎣..
. . ⎦⎣ . ⎦
.
v2L v2L−1 ··· vL−1 L

where v1 , v2 , . . . , v2L is the observed segment of the keystream, a total of 2L consec-

utive symbols. All vi needed by the stated equations are known, and the i are the
unknowns. The recursion is found by solving this matrix equation for the vector of tap
weights i . The recursion can then be executed to produce the entire periodic sequence.
The linear-complexity attack will succeed whenever the length of the observed
segment of the keystream is at least twice the actual linear complexity of the keystream
(defined in the next section) because then all elements of the above matrix equation
except the coefficients of (x) are known. It is not necessary that the linear complexity
L be known prior to the attack. The attack will succeed if the length of the observed
segment of the keystream satisfies the necessary condition that it is at least twice as
large as the linear complexity; otherwise, it will fail. For this reason, a linear-complexity
attack is a threat only if the linear complexity is significantly smaller than one-half
of the period of the keystream. If the linear complexity is nearly half of the period or
length of the keystream, then the linear-complexity attack requires that nearly all of
the keystream be known in order to produce the rest. In this case, a linear-complexity
attack is not a suitable attack.
A linear-complexity attack is both tractable and meaningful because of the properties
of the matrix equation describing the recursion. A linear-complexity attack is tractable
because there are efficient computational algorithms that will solve this form of matrix
equation. The matrix itself is known as a Toeplitz matrix. There are fast algorithms to
invert a matrix of this form. Moreover, because of the special form of the system of
linear equations, even faster algorithms are available to solve this system of equations
without inverting a matrix. A linear-complexity attack is meaningful because any
2L consecutive known components of the sequence will do to reconstruct the entire
sequence if the linear complexity is indeed L. Even some patterns of nonconsecutive
blocks of components will sometimes suffice to set up an invertible matrix. Such
patterns can be analyzed in terms of the heft and rank of the matrix describing the
recursion. These terms are defined in Section 9.12 of Chapter 9.

7.5 Analysis of linear complexity

We have stated that an additive keystream may be vulnerable to a linear-complexity

attack, which is an attack that produces an entire keystream from a small known segment
of the keystream by setting up a linear recursion. If this attack were to succeed, then

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 191 7.5 Analysis of linear complexity

the keystream is only as secure as is that keystream segment. A linear-complexity

attack requires that some segment of the keystream be received in the clear, or can be
otherwise deduced by some means from an observed segment of the ciphertext. This
amounts to a (partially) known-plaintext attack.
A linear recursion of length L in the field F – or the ring R – is an expression of
the form
L
vi = − k vi−k i = L, L + 1, . . . .
k=1
A linear recursion of length L produces the entire sequence v from its first L com-
ponents. For example, the elementary linear recursion vi = vi−1 + vi−2 in the ring Z
produces the well-known Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, . . .).
The linear complexity of any sequence v is defined to be the length of the shortest
linear recursion that will produce that sequence. For example, the linear complexity
of the Fibonacci sequence is two because the linear recursion vi = vi−1 + vi−2 will
produce the Fibonacci sequence, but no shorter linear recursion will produce the
Fibonacci sequence.
A linear-complexity attack is an attempt to find a linear recursion that produces a
sequence, when given a segment of that sequence. To protect against a linear-complexity
attack, one wants sequences of large linear complexity, but to be practical, the structure
of these sequences must not be too complicated. Otherwise, the sequences would be
too difficult to generate.
The linear-complexity attack is based on the observation that if a sequence v satisfies
the recursion
L
vi = − k vi−k i = L, L + 1, . . . ,
k=1
and vi is known for 2L consecutive values of the index i, then the recursion gives a
system of L linear equations in the L unknown coefficients i .
There are several theorems that are useful for studying linear complexity. We begin
with a theorem that states a condition under which two linear recursions will continue
to agree if they agree up to a certain point. This theorem is used in the proofs of the
two theorems that follow.

Theorem 7.5.1 (Agreement theorem) If two linear recursions (x) and  (x)
of length L and L , respectively, both produce the sequence v0 , v1 , . . . , vr−1 , and if
r ≥ L + L , then both linear recursions produce the same sequence thereafter.

Proof It is enough to show that both recursions produce the same rth term under the
conditions of the theorem. We must show that
L L
− k vr−k = − k vr−k ,
k=1 k=1

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 192 Stream ciphers

under the assumption that

L
vi = − k vi−k i = L, . . . , r − 1
k=1

and
L
vi = − k vi−k i = L , . . . , r − 1.
k=1

Because r ≥ L + L , we can set i = r − j in each of these two equations. Then we

can write
L
vr−j = − k vr−j −k j = 1, . . . , L
k=1

and
L
vr−j = − k vr−j −k j = 1, . . . , L,
k=1

with all indicated terms from the given sequence v0 , v1 , . . . , vr−1 . Finally, we have
L L L
− k vr−k = k j vr−k−j
k=1 k=1 j =1
L L
= j k vr−k−j
j =1 k=1
L
=− j vr−j ,
j =1

as was to be proved. 

Theorem 7.5.2 (Massey’s theorem) If the shortest linear recursion that produces
the sequence (v0 , v1 , . . . , vr−2 ) has length L and does not produce the sequence v =
(v0 , v1 , . . . , vr−2 , vr−1 ), then every linear recursion that produces v has a length of at
least r − L.

Proof Suppose a linear recursion of length L satisfying L < r − L exists that

produces the sequence (v0 , . . . , vr−1 ). Then we have two recursions that produce
(v0 , . . . , vr−2 ). But L + L ≤ r − 1, so by the agreement theorem, both must produce
the same value at the next iteration, contrary to the premise of the theorem. 

For example, the recursion vi = vi−1 + vi−2 produces the Fibonacci sequence. In
particular, it produces the finite-length sequence (1, 1, 2, 3, 5, 8, 13, 21, 34), but it does

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 193 7.5 Analysis of linear complexity

not produce the longer sequence (1, 1, 2, 3, 5, 8, 13, 21, 34, A) unless A = 55. For
other values of A, Massey’s theorem states that every linear recursion that produces
the sequence has length at least 8. Likewise, the smallest linear recursion over F 2 that
produces the finite-length sequence 1, 1, 0, 1, 1, 0, 1, 1, 0, 0 has a length at least 8.
Let ω be an element of order n in F or possibly in an extension field of F. Such
an ω always exists if F has characteristic zero, and such an ω always exists if the
characteristic p of the finite field F p is coprime with n. Furthermore, such an ω of
order n exists in F pm if, and only if, n divides p m − 1. Then any vector v of length n
has a Fourier transform, V , given by
n−1
Vj = ωij vi j = 0, . . . , n − 1.
i=0

The properties of the Fourier transform are summarized in Section 9.12.

The next theorem characterizes the Hamming weight of a Fourier transform, where
the Hamming weight of a vector is defined as the number of nonzero components of
that vector.

Theorem 7.5.3 (Blahut’s theorem) The linear complexity of a periodic sequence

over F of period n is equal to the Hamming weight of its Fourier transform, provided
a Fourier transform of blocklength n exists.

Proof Let v be the periodic sequence of blocklength n, and let V be the Fourier
transform of v given in terms of its components as
n−1
Vj = vi ωij
i=1

for any ω of order n in F or in an extension of F, provided such an ω of order n exists.

Consider any recursion of the form
L
vi = − k v((i−k))
k=1

where the double parentheses denote modulo n. Let (x) = 1 + Li=1 i x i and v(x) =
n−1 i
i=0 vi x . The recursion can be rewritten as a polynomial product

(x)v(x) = 0 (mod n),

from which we can write

(ω−i )v(ω−i ) = 0

where ω is any element of order n, possibly in an extension field. Therefore, if λi =

(ω−i ) and vi = V (ω−i ), we see that λi = 0 whenever vi = 0. Because (x) cannot

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 194 Stream ciphers

have more zeros than its degree L, we conclude that L ≥ wt(v). Moreover, we can
always construct a (x) of degree wt(v) with zeros at the nonzeros of v i . This (x)
corresponds to a recursion of minimum length, and the length of this recursion must
be L = wt(v). 

7.6 Keystreams from nonlinear feedback

A linear shift-register sequence is an elementary example of a keystream. It is perhaps

the most commonly used mathematical structure out of which additive keystream
ciphers are constructed, but it is normally augmented with embellishments that are
included to increase the security. The embellishments are needed because a linear
shift-register sequence, although rather elegant with a clean mathematical structure,
is vulnerable to a linear-complexity attack. There are many such embellishments of
linear shift-register sequences that are intended to counter the linear-complexity attack.
We will consider constructions that are based on nonlinear shift-register feedback
in this section, constructions that combine several linear shift-register sequences in
Section 7.7, and constructions that are based on nonlinear operations on the output of
a linear-feedback shift register in Section 7.8.
A recursion of the form vi = −f (vi−1 , vi−2 , . . . , vi−m ) is called a nonlinear recur-
sion if the function f is not linear. A binary recursion is one in which all the variables
and operations are in F 2 . To specify an arbitrary nonlinear binary recursion, observe
that for each of 2m possible states of an m-bit memory, the value of f can be either
zero or one. Thus the function f can be described as a binary number of length 2m .
m m
There are 22 such binary numbers, and so there are 22 such binary functions. Of
these, 2m are linear functions. Every recursion is eventually periodic because the state
corresponding to the argument of the function f can only take a finite number of
values and so must repeat. Some such recursions can have a starting transient (which
depends on the initialization) prior to entering the periodic behavior. These recursions
are called singular recursions. Recursions that are periodic for any initialization are
called nonsingular recursions.
As we have seen, a linear-feedback shift register of length m cannot produce a
sequence with period larger than 2m − 1, even though a memory of m bits could hold
2m values. This is because, to produce a periodic sequence of period 2m using m bits of
state memory, the linear-feedback shift register must never contain all zeros. If ever it
did contain all zeros, it would continue to hold all zeros thereafter. A nonlinear periodic
sequence, however, can have period 2m and can be produced by a finite-state machine
with m bits of memory. It cannot produce a sequence with a period that is larger
than 2m .

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 195 7.6 Keystreams from nonlinear feedback

1 00

10 01

11

Figure 7.5 A shift register for a deBruijn sequence

Definition 7.6.1 A deBruijn sequence is any periodic sequence over a q-ary alphabet
of period q m in which every pattern of m symbols begins once in each segment of length
q m.

The definition recognizes the fact that q m m-tuples begin in any segment of length
m, and some will extend beyond that segment. Indeed, those q m m-tuples will be in an
interval of length q m + m − 1. Because we restrict the continuing discussion to binary
sequences, there will be 2m m-tuples beginning in any period.
Every deBruijn sequence can be formed by a nonlinear boolean feedback function
of the form

vi = f (vi−1 , vi−2 , . . . , vi−m )

= vi−m + g(vi−1 , . . . , vi−m+1 ).

Only those functions g for which the period is 2m give deBruijn sequences. There are
2(2 −m) binary deBruijn sequences of period 2m , up to translation.
m−1

There is only one deBruijn sequence of length four, two of length eight, sixteen of
length sixteen, and 2048 of length thirty-two. Some examples are

m=2 0011
m=3 00010111
m=4 0000111101100101
m=5 00000100011001010011101011011111.

Because a deBruijn sequence has period 2m and m bits of memory, every possible state
of the memory must recur during every period. Inspection of the above sequences,
regarded cyclically, will reveal that the sequence of length 2m displays every m-bit
pattern as a subsequence. There can be no starting transient in a deBruijn sequence.
An example of a shift-register circuit that produces the only deBruijn sequence of
length four is shown in Figure 7.5. One period of the deBruijn sequence is 0011, which
then repeats. The sequence of states of the 2-bit memory is also shown in Figure 7.5.
This periodic sequence is clearly not linear because 0011 + 0110 = 0101 which is not
a cyclic translate of 0011. Nevertheless, this nonlinear sequence with m = 2 can be
produced by a linear-feedback shift register of length three, as is shown in Figure 7.6.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 196 Stream ciphers

Figure 7.6 A linear-feedback shift register for a deBruijn sequence

zi(1)
LFSR1

zi(2)
LFSR2
f zi

zi( n)
LFSRn

zi = f zi(1), zi(2),…, zi(n)

Figure 7.7 Nonlinear combining of shift-register sequences

It cannot be produced by a linear-feedback shift register of length two, so the linear

complexity of this sequence is three. No simple expression for the linear complexity
of a general deBruijn sequence is known.
The linear-feedback shift register shown in Figure 7.6 produces a nonlinear sequence
and the feedback is described by the polynomial equation z3 = z2 + z + 1 correspond-
ing to vi = vi−1 + vi−2 + vi−3 . We recall that an irreducible polynomial must produce
a linear sequence and this is not a linear sequence. But z3 + z2 + z + 1 is not an irre-
ducible polynomial, so the discussion of Section 7.3 does not assert that this recursion
produces a linear sequence, and indeed it does not.

7.7 Keystreams from nonlinear combining

A deBruijn sequence introduces nonlinearity in order to produce a periodic sequence

with the largest possible period that can be produced with m bits of state memory. How-
ever, maximizing the sequence period is usually not the only important consideration.
It is much more important to balance between maximizing security and minimizing
complexity. This balance might be obtained by some more elaborate nonlinearity,
as by combining several linear-feedback shift-register sequences. Figure 7.7 shows a

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 197 7.7 Keystreams from nonlinear combining

LFSR1

LFSR2 Output

LFSR3

Figure 7.8 Geffe keystream generator

general form that uses nonlinear operations on the outputs of the linear-feedback shift
registers. Some of these elementary methods of combining multiple recursions have
names.
A Geffe keystream is the combination of two shift-register sequences {ui } and {vi },
with periods n1 and n2 , under the control of a third shift-register sequence with period
n3 , as shown in Figure 7.8. A Geffe keystream is formed by the nonlinear, but mem-
oryless, combining of multiple linear-feedback shift registers. The Geffe keystream
is defined in F 2 as zi = wi ui + w i vi where wi = 1 + wi . The period of the Geffe
keystream is n = LCM[n1 , n2 , n3 ]. The linear complexity of the Geffe keystream is
(n1 + 1)n2 + n1 n3 , which is a direct consequence of the forthcoming Theorem 7.8.3. If
n1 , n2 , and n3 are pairwise coprime and approximately equal, then n ≈ n31 . Therefore
the linear complexity is about 2n2/3 , which is comparable to n. Accordingly, the Geffe
keystream is not especially vulnerable to a plaintext linear-complexity attack. However,
it is vulnerable to a correlation attack, as is described in Section 7.9.
A Beth–Piper keystream uses two shift-register sequences {ui } and {vi }. It repeats
the bits of {ui } while vi is zero. Thus for each i:

If vi = 0, then zi = u and  ← 
If vi = 1, then zi = u and  ←  + 1.

Each time a bit of v is a zero, it causes the most recent symbol of z to be repeated.
Each time a bit of v is a one, it selects the next unused symbol of u for the next symbol
of z. The linear complexity of the Beth–Piper keystream is apparently unknown, but
evidently this keystream falls to a correlation attack.
An alternating keystream uses a generator with three shift registers as shown in
Figure 7.9. Each bit of one sequence is used to enable the clock of one of the other two
shift registers, but not both. The two output sequences are then added.
A shrinking keystream uses two linear shift-register sequences {ui } and {vi }. It
deletes the bit ui whenever vi is zero. Thus for each i:

If vi = 0, then i ← i + 1
If vi = 1, then zi = ui , i → i + 1,  →  + 1.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 198 Stream ciphers

LFSR2

Clock LFSR1 Output

LFSR3

Figure 7.9 The alternating-step generator

Each time a bit of v is a zero, it causes the most recent symbol of u to be skipped.
Each time a bit of v is a one, it causes the next symbol of u to be the next symbol of z.
The linear complexity of the shrinking keystream appears to be unknown. A shrinking
keystream is believed to be immune to a correlation attack.
For examples of a Beth–Piper keystream and a shrinking keystream, let v and u be
the periodic sequences

v = 010011010111100 . . .
u = 000101111000101111 . . .

of period 15 and of period 7, respectively. Then

z = 00000110111 . . .

is the Beth–Piper keystream and

z = 00110001 . . .

is the shrinking keystream.

A majority-clocking keystream is based on an alternative method that combines the
outputs of three binary linear-feedback shift registers of different lengths by modulo-
two addition. Each shift register also provides a designated control bit taken from one
interior stage of the shift register. Accordingly, this control bit is a bit of that sequence
delayed from the current output bit. The three control bits are combined in some fashion
to form three clock-enabling bits, one for each of the three shift registers. A typical
rule is that the current output bit of any shift register is repeated without change for as
long as the control bit of that sequence differs from both of the control bits of the other
two sequences. This is done by disabling the clock of that shift register as is shown in
Figure 7.10. The three control bits are designated a, b, and c in the figure. From the
three control bits, a, b, and c, simple logic computes the three clocking bits, A, B, and
C, given by

A=a·b+a·b+a·c+a·c
B =b·c+b·c+b·a+b·a
C = c · a + c · a + c · b + c · b.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 199 7.8 Keystreams from nonlinear functions

LFSR1
A
a
Clock a A
LFSR2 Output b LOGIC B
c C
B
b

LFSR3
C
c
Figure 7.10 Majority-clocking keystream

By the logical multiplication of each clock-enabling bit with the clocking bit, the
clocking bit is enabled to reach the appropriate shift register. This means that each shift
register is clocked only about half of the time and always in an apparently irregular
pattern. One intends this irregularity to counter a linear-complexity attack.

7.8 Keystreams from nonlinear functions

A keystream can also be formed from a linear-feedback shift register by a nonlinear

function operating on the state of that linear-feedback shift register. We are interested in
binary sequences formed by nonlinear binary shift registers of length n, which means
that we are interested in binary functions from F n2 to F 2 .
Any function f (x1 , . . . , xn ) from F n2 to F 2 is called a boolean function. Every
boolean function can be expressed in a standard form, known as the algebraic normal
form, or more simply, as the normal form, which is given as the following sum of
products:

f (x1 , . . . , xn )
= [a0 ] + [a1 x1 + · · · + an xn ]
+ [a1,2 x1 x2 + a1,3 x1 x3 + · · · + an−1,n xn−1 xn ] + · · · + [a1,2,...,n x1 x2 · · · xn ].

The order of any term in the sum is defined to be the number of variables in that term.
The terms are grouped by brackets according to order. The first bracket, [a0 ], contains
the only zero-order term. The second bracket, [a1 x1 + · · · + an xn ] contains all first-
order terms. The (i + 1)th bracket contains all ith-order terms. The largest order of any
term in the standard form with a nonzero coefficient is called the nonlinear order λ of
the boolean function f (x1 , . . . , xn ). An affine boolean function is a boolean function
of nonlinear order one. A linear boolean function is an affine boolean function with
coefficient a0 equal to zero. A linear boolean function satisfies f (x1 , x2 , . . . , xn ) +

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 200 Stream ciphers

f (x1 , x2 , . . . , xn ) = f (x1 + x1 , x2 + x2 , . . . , xn + xn ). All other boolean functions are
nonlinear boolean functions.
Any binary function can be described by a truth table. The entries of this truth table
are indexed by the elements of F n2 . These are binary vectors of length 2n and can be
regarded as addresses of the table. The contents of the table at the location addressed
by (x1 , x2 , . . . , xn ) is the value of the binary function f at (x1 , x2 , . . . , xn ). This value
is a zero or a one.
The Hamming distance, denoted dH (v, u), between two binary vectors v and u is
the number of places in which they differ. The Hamming distance between v and u is
related to the Hamming weight by

dH (v, u) = wH (v − u).

The Hamming distance, denoted dH (f, g), between two boolean functions f and h
from F n2 to F 2 is equal to the number of values of the vector argument (x1 , . . . , xn ) for
which f (x1 , . . . , xn ) differs from h(x1 , . . . , xn ). The Hamming distance between two
such boolean functions can be as large as 2n . The degree of nonlinearity of the boolean
function f is the Hamming distance from f to the set of all affine boolean functions,
defined as

n(f ) = min dH (f, h),

h

where the minimum is over the set consisting of all affine boolean functions on n
variables. The degree of nonlinearity measures how closely the nonlinear function f
can be approximated by a linear function.
An example of a boolean function is the function from F 62 to F 2 given by

f (x1 , x2 , x3 , x4 , x5 , x6 ) = 1 + x3 + x1 x2 + x5 x6 .

This is a boolean function with nonlinear order λ = 2. This nonlinear function can
be used to alter the output of a linear-feedback shift register. A linear-feedback
shift register with feedback polynomial x 6 + x + 1 and the above nonlinear func-
tion used to produce a nonlinear output is shown in Figure 7.11, with an initialization
100000.
A second example is the function from F 42 to F 2 given by

f (x1 , x2 , x3 , x4 ) = 1 + x2 + x4 + x1 x2 x3

which has nonlinear order λ = 3.

Definition 7.8.1 A nonlinear-output linear-feedback shift register sequence is a

sequence over F 2 given by the nonlinear binary function zi = f (x1(i) , . . . , xm(i) ), where
(x1(i) , . . . , xm(i) ) is the binary representation of the orbit of an element α of the field F 2m ,
as given by (α 1 , α 2 , α 3 , . . . , α i , . . .).

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 201 7.8 Keystreams from nonlinear functions

1 0 0 0 0 0

1
Figure 7.11 A nonlinear-output linear-feedback shift register

Theorem 7.8.2 (Key’s theorem) The linear complexity of a nonlinear-output linear-

feedback shift register sequence produced
 by a shift register of length L and nonlinear
λ L
order λ is not larger than i=1 i .

Proof The proof is based on Theorem 7.5.3 which says that the linear complexity
of a periodic sequence v of period n is equal to the Hamming weight of its Fourier
transform V . If any linear-feedback shift register that produces v has length L, then
the linear complexity of the sequence v is at most L. Moreover, by superposition of
the feedback connections, the linear complexity of the sum of two sequences is not
larger than the larger of their two individual linear complexities. This means that it is
enough to prove the theorem for a nonlinear function, f (v1 , . . . , vn ), that has only a
single nonlinear term.
We begin with a proof for the special case of a nonlinear function that has only a
single nonlinear term of order two. As a function of i, the single term of order two
produces the cyclic sequence wi = vi−a vi−b abbreviated wi = vi vi where vi = vi−a
and vi = vi−b . The cyclic sequence w is a componentwise product, so the convolution
theorem says that

W = V  ∗ V 

in the Fourier transform domain, where V  and V  are the Fourier transforms of v 
 j
and v  , respectively, which are translates of each other. Let V  (x) = n−1
j =0 Vj x and
 j
V  (x) = n−1  
j =0 Vj x . The polynomials V (x) and V (x) are sparse, each having weight
at most L, and, by the translation property of the Fourier transform, both are nonzero in
exactly the same components. By Theorem 7.5.3, the linear complexity of the sequence
w with components wi = vi−a vi−b is equal to the weight of polynomial W (x) where
W (x) = V  (x)V  (x). There are L2 terms in the raw polynomial product V  (x)V  (x),
but many terms will have the same power of x and so will combine into one term, or
even cancel. The linear complexity of the nonlinear term of order two is not larger than
the number of nonzero coefficients of W (x).

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 202 Stream ciphers

0 0 1 1 0 0 0 0 0

Figure 7.12 Illustrating Key’s theorem

To determine the number of nonzero coefficients of W (x), let  index only the
nonzero coefficients of V (x) so that the product can be written as
L L
W (x) = Vj Vj x j +j .
 =1  =1

The product terms Vj Vj and Vji  Vji  add whenever j + j = ji  + ji  . The L2
terms under the sum may be written in matrix form. The diagonal terms, with  equal
to  , have a power of x that appears once. The off-diagonal terms, those with  not
equal to  , have a power of x that appears twice, once on each side of the diagonal.
This means that the number of such terms is
   
L L
LW = + ,
1 2
   
because there are L1 terms on the diagonal and L2 terms above the diagonal.
Possibly, because of cancellation, some of the terms may be zero. The linear complexity
of an output sequence is not larger than LW and, because some of the terms may cancel,
it may be smaller. This completes the proof for nonlinear functions of order two.
A similar analysis for a term of the form vi vi vi would show that
     
L L L
LW = + + .
1 2 3
This analysis is easily extended to a higher-order term.
Finally, because the linear complexity of a sum of terms is not larger than the largest
linear complexity of any one term, the theorem follows. 

An example of Key’s theorem is shown in Figure 7.12. On the left is a nonlinear-

output linear-feedback shift register of length three and nonlinear order two. The period
of the shift-register sequence is seven, and so the period of the output sequence is seven.
The linear shift-register sequence itself is

x = (1101001),

and from this, by multiplying two terms, the nonlinear output sequence is

z = (1100000),

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 203 7.8 Keystreams from nonlinear functions

0 0 0 1 0 0 1 0 0 0 0 0 0 0

Figure 7.13 Illustrating nontightness of Key’s theorem

each sequence read from right to left. Key’s theorem says that the linear complexity of
the output sequence is at most six. On the right of Figure 7.12 is a linear-feedback shift
register of length six that gives the same output when initialized as shown. No shorter
linear-feedback shift register produces this sequence. Thus the linear complexity of the
output sequence is actually six, which meets Key’s theorem with equality.
A second example of Key’s theorem is shown in Figure 7.13. On the left is a
nonlinear-output linear-feedback shift register of length four and nonlinear order three.
The linear shift register itself produces the sequence

x = (111010110010001),

and from this, by multiplying three terms, is computed the nonlinear periodic output
sequence

z = (001000010000000)

from left to right, respectively. On the right side of Figure 7.13 is a linear-feedback shift
register that produces this same periodic sequence. In this case, Key’s theorem says that
the linear complexity is not larger than fourteen. In fact, the linear complexity is ten
because we have exhibited a linear-feedback shift register of length ten that produces it,
and there is no smaller linear-feedback shift register that does so. This example shows
that Key’s theorem is not tight. By referring to the proof of Key’s theorem, this can be
understood as a consequence of various components canceling in the Fourier transform
domain.
Another approach is to use multiple linear-feedback shift registers with component-
wise multiplication of the outputs to generate a sequence. Using nonlinear combining
of only one of the outputs of each shift register is not as restrictive as it might appear
because the statement allows the use of multiple copies of the same shift register with
different phases. The left side of Figure 7.14 shows two linear-feedback shift registers
whose outputs are multiplied to form a keystream. The right side of Figure 7.14 shows
a single linear-feedback shift register that produces the same sequence. No shorter
such shift register exists. Thus the linear complexity of the nonlinear keystream is six.
This is equal to the product of the lengths of the two original shift registers, which is
consistent with the forthcoming theorem.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 204 Stream ciphers

0 1

1 0 1 0 0 1

0 0 1

Figure 7.14 A nonlinear combination generator and its equivalent

0 1

0 0 1 0 0

0 0 1

Figure 7.15 A linear combination generator and its equivalent

A similar conclusion holds if the outputs of the shift registers are added to form a
keystream, as shown in Figure 7.15. Again, the right side of the figure shows a single
linear-feedback shift register of length five that produces the same sequence. No shorter
such shift register exists. Thus the linear complexity of the linear keystream is five.
This is equal to the sum of the lengths of the original two sequences.
We are now motivated for the following theorem.

Theorem 7.8.3 The linear complexity of a nonlinear combination of n shift-register

sequences with linear complexity L1 , L2 , . . . , Ln , respectively, using a boolean com-
bining function

zi = f (zi(1) , zi(2) , . . . , zi(n) )

in normal form has linear complexity not larger than f (L1 , L2 , . . . , Ln ), where f is
now interpreted as a function on the integers.

Proof Let L = f (L1 , L2 , . . . , Ln ). We must show that the collection of linear-

feedback shift registers of lengths L1 , L2 , . . . , Ln can be replaced by one linear-
feedback shift register of length not larger than L. Because the boolean combining
function can be executed as a sequence of binary additions and binary multiplications,
it is only necessary to prove the theorem for a simple componentwise binary addition
zi = xi + yi and for a simple componentwise binary multiplication zi = xi yi . In each

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 205 7.8 Keystreams from nonlinear functions

case, the method of proof is to transform the problem into the Fourier domain and to
then refer to Theorem 7.5.3, which says that the Fourier transforms of x and y have
weights L1 and L2 , respectively.
Let the periodic sequences x and y have coprime periods n1 and n2 , respectively.
Now, regard the two periodic sequences of length n1 and n2 to each be a periodic
sequence of period n = n1 n2 as follows. Repeat the first sequence n2 times to form a
periodic sequence of period n. By Theorem 9.12.3, the Fourier transform of the new
sequence consists of the components of the original Fourier transform with n2 − 1 zeros
inserted after every component of the original sequence. Similarly, repeat the second
sequence n1 times to form a periodic sequence of length n. Again, by Theorem 9.13.3,
the Fourier transform of the longer sequence of period n consists of the components of
the original sequence with n1 − 1 zeros inserted after every component of the original
sequence.
First consider the case of multiplication with zi = f (xi , yi ) = xi yi , where as
described above, x and y are periodic sequences with coprime periods n1 and n2 .
Both sequences are regarded as lengthened to the common period n = n1 n2 . The
two new sequences of period n are multiplied componentwise, so their Fourier trans-
forms are convolved. Because the two Fourier transforms have L1 and L2 nonzero
components, respectively, the convolution has at most L1 L2 nonzero components. By
Theorem 7.5.3, the inverse Fourier transform then has linear complexity at most L1 L2 .
Indeed, if n1 and n2 are coprime, there will be exactly L1 L2 nonzero components in the
convolution. Therefore if n1 and n2 are coprime the linear complexity will be exactly
L1 L 2 .
Next, consider the case of addition with zi = f (xi , yi ) = xi + yi , where as described
above, x and y are periodic sequences with common period n = n1 n2 . The two
sequences have L1 and L2 nonzero components, respectively, so the sum has at
most L1 + L2 nonzero components. Because n1 and n2 are coprime, the nonzero
components in the Fourier transforms of the two sequences do not occur in the
same components. This means that there can be no cancellation, so there are exactly
L1 + L2 nonzero components. Again, by Theorem 7.5.3, the inverse Fourier trans-
form has linear complexity at most L1 + L2 . This holds with equality if n1 and n2 are
coprime. 

The next theorem states that Theorem 7.8.3 holds with equality under certain satis-
fying conditions.

Theorem 7.8.4 The inequality of the previous theorem holds with equality if the
component linear-feedback shift-register sequences are maximal-length sequences.

Proof The proof merely consists of inspection of the equality conditions in the proof
of Theorem 7.8.3, and will not be discussed further. 

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 206 Stream ciphers

18 17 16 13 8

to clocking logic A

21 20 10 0

to clocking logic B

22 21 20 10 7 0

to clocking logic C

A majority clock A
B clocking clock B
C logic clock C

Figure 7.16 The GSM stream cipher

As an example of the theorem, the Geffe cipher has a nonlinear combining function
in normal form f (z1 , z2 , z3 ) = z(3) + z(1) z(2) + z(2) z(3) and period LCM(L1 , L2 , L3 ).
By Theorem 7.8.3, the linear complexity is at most L3 + L1 L2 + L2 L3 , which, by
Theorem 7.8.4, holds with equality if all shift registers are of maximum length. Thus
with L1 = 30, L2 = 31, L3 = 29, the linear complexity of this linear combination
is 1858. A linear-complexity attack will succeed if at least 3716 consecutive bits of
the Geffe keystream are observed. The period of this Geffe keystream is 26,970, so the
linear-complexity attack requires that more than 10% of one period of the sequence be
observed.
A related construction intended to suppress any structure that may be useable to the
cryptanalyst is to combine the outputs of multiple shift registers that are individually
clocked in a stop-and-go manner with some irregularity in the pattern of clocking. In
order to have a keystream with a period at least in the billions, well over 30 bits of
memory will be required. This keystream may be obtained by nonlinear or irregular
combining of three linear-feedback shift registers. An example is the GSM stream
cipher, shown in Figure 7.16, consisting of the combination of three shift-register
circuits. This cipher uses three linear-feedback shift registers of lengths 19, 22, and

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 207 7.9 The correlation attack

23, respectively. It requires a total of 64 bits to initialize these three shift registers. The
three connection polynomials used by the GSM cipher are

p1 (x) = x 18 + x 17 + x 16 + x 13 + 1
p2 (x) = x 21 + x 20 + 1
p3 (x) = x 22 + x 21 + x 20 + x 7 + 1.

The irregular nonlinear behavior of this stream cipher is provided by a self-clocking

scheme that is suggestive of the Beth–Piper keystream.
To initialize the GSM stream cipher generator in a simple way, the 64-bit key for the
GSM cipher is shifted into all three shift registers by adding the key to the feedback
term at the right side of each shift register. The insertion of the 64-bit key fills the three
registers with the 64 initialization bits. Because of the feedback, the initialization bits
residing in the registers after the key is shifted in are not the same as the key, but do
depend on the key.
The three outputs of the three linear-feedback shift-register circuits are added
together to produce the keystream. To protect the keystream sequence from a linear-
complexity attack, the three shift-register circuits are not all shifted at every clock time.
Instead, the three clocking commands are generated by the three shift registers working
in concert. Each shift register has a special clocking bit, as shown in the figure. Each
shift register is clocked only if its special clocking bit agrees with at least one of the
two special clocking bits of the other two shift registers. Thus the shift register whose
clocking bit is in the minority, if there is one, will not be shifted. It is easy to see that
each shift register will be clocked three times out of four, and no shift register can be
permanently stagnant.

7.9 The correlation attack

One kind of known-plaintext attack for breaking certain forms of nonlinear stream
ciphers is known as a correlation attack. We have already discussed how one might
choose to use a binary keystream that is based on the nonlinear combining of sev-
eral shift registers in order to counter a linear-complexity attack. A Geffe cipher is
a simple example. However, this keystream might be vulnerable to attack in a dif-
ferent way. It might be vulnerable to a correlation attack. Nonlinear combining, as
used in the Geffe cipher, can be attacked using statistical-estimation methods to pene-
trate the nonlinearities, at least in part, so that something about the underlying linear-
feedback shift registers can be revealed. In response to this threat of a correlation attack,
the cryptographer will avoid some forms of nonlinear combining functions. Correla-
tion immunity should be built into the keystream generator to thwart a correlation
attack.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 208 Stream ciphers

A correlation attack requires that a significant segment of the plaintext be known

so that it can be used to find the key. This again has the form of an inverse problem.
Given partial knowledge of the keystream ek , find k. Here the key k corresponds to
the unknown parameters that determine the outputs of the multiple underlying linear-
feedback shift registers. In the standard version of this attack, the linear-feedback shift
registers and the nonlinear functions that combine their outputs are fully known. The
key then consists only of the initialization of the shift registers, and the goal of the
attack is to find the initialization. A correlation attack requires a significant correlation
between the keystream and the specific parameters of the underlying linear-feedback
shift registers.
We will describe a correlation attack for a Geffe keystream. This Geffe keystream
consists of the merging of two subkeystreams, one subkeystream from each of the two
linear-feedback shift registers. We will suppose that the structures of the two linear-
feedback shift registers are known to the cryptanalyst. The two linear-feedback shift
registers have lengths m1 and m2 , respectively, so the key consists of the m1 + m2 bits
that were used to initialize these two shift registers. This means that there are 2m1 +m2
possible keys, several of which, such as an all-zero initialization, are trivial and cannot
be used. The correlation attack will be directed against one of the two shift registers,
presumably the shorter one, which we can take to have length m1 . There are only
2m1 − 1 possible nonzero initializations of the linear-feedback shift register of length
m1 . That shift register can be initialized with any nonzero value and will eventually
cycle through all possible nonzero values. The output of that shift register is a periodic
sequence of period 2m1 − 1. If the parameters of the shift register are known, then that
periodic sequence is known to the cryptanalyst, and only its phase as determined by
the initialization is not known.
Each bit of the Geffe keystream consists of the bit value corresponding to one of the
two subkeystreams, the choice between them being controlled by a third shift-register
sequence. For our analysis, we will regard the control sequence as a random sequence.
Thus the Geffe keystream is randomly chosen from the first subkeystream for about
half of the bits, and randomly chosen from the second subkeystream for the other
half. When the second subkeystream is chosen, about half of the bits, on average, will
agree with the first subkeystream. Thus the Geffe keystream agrees with the first of
its subkeystreams about 75% of the time. Similarly, it agrees with the second of its
subkeystreams about 75% of the time.
A correlation attack requires that a subsequence of the Geffe keystream be known.
It correlates the known segment of the keystream with a reference subkeystream con-
sisting of one period of the output of the first linear-feedback shift register with an
arbitrary initialization. The reference cyclic subkeystream will contain a segment that
is equal to the actual m1 -bit initialization used in that shift register, but that segment is
(cyclically) delayed by some integer value 0 with respect to the reference keystream.
At the value of delay  equal to 0 , the content of the shift register is equal to the

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 209 7.9 The correlation attack

initialization key, and the reference subkeystream is fully correlated with the actual
subkeystream underlying the known segment. When  is equal to 0 , about 75% of the
bit positions in the two sequences will agree. When  is not equal to 0 , about 50%
of the bit positions will agree. Then the expected value of the normalized correlation
is 0.75. Thus, looking for a correlation with respect to the reference keystream peak
determines the phase of the shorter Geffe subkeystream.
Let zi for i = 0, . . . , t − 1 denote the t bits of the observed keystream that has been
uncovered from the known plaintext expressed in the bipolar alphabet {−1, +1}. Let
wi be the sequence of keystream bits that are produced by the first linear-feedback shift
register also expressed in the bipolar alphabet {−1, +1}. The correlation is defined as
t−1
φ() = zi wi+ .
i=0

When  = 0 , about 75% of the terms will be +1 and the remainder will be −1. Thus

1
t if  = 0
E [φ()] = 2
0 if  = 0 .

The variance in φ() is given by

E [φ()2 ] = n.

The estimated sequence phase is given by


0 = argmaxk φ().

The probability of error is the probability that some  other than 0 achieves the
maximum. To simplify the calculation of the probability of error by using an approx-
imate calculation, consider instead n gaussian random variables of variance σ 2 = n,
of which one random variable has mean A = n/2, and the remainder have mean zero.
This approximation can be motivated by appealing to the central limit theorem.
The probability pe that a gaussian random variable with mean A and variance σ 2 is
not larger than each of n − 1 other independent gaussian random variables, each with
zero mean and variance σ 2 , is
 ∞ ! z "n−1
1 −(z−A)2 /2σ 2 1 −x 2 /2σ 2
pe = 1 − √ e √ e dx dz,
−∞ 2πσ 2 −∞ 2πσ 2
which is written as one minus the probability that the random variable with mean A is
larger than every other random variable. This expression can be integrated numerically.
This expression is hard to interpret as it stands. To understand what it says, use the
standard inequality
 ∞
1 1 2
√ e−x /2 dx < e−z /2
2
for z > 0.
z 2π 2

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 210 Stream ciphers

Then
 ∞ !  ∞ "n−1
1 −(z−A)2 /2σ 2 1 −x 2 /2σ 2
1 − pe = √ e 1− √ e dx dz
−∞ 2πσ 2 z 2πσ 2
 ∞ ! "n−1
1 −(z−A)2 /2σ 21 2 2
> √ e 1 − e−z /2σ dz
−∞ 2πσ 2 2
 ∞ ! "
1 −(z−A)2 /2σ 2 (n − 1) −z2 /2σ 2
> √ e 1− e dz.
−∞ 2πσ 2 2
This can now be rewritten as

n−1 ∞ 1
e−(2z −2Az+A )/2σ dz.
2 2 2
pe ≤ √
2 −∞ 2πσ 2
Complete the square in the exponent to write

n − 1 ∞ −2(z−A/2)2 /2σ 2 −A2 /2σ 2
pe < e e dz
2 −∞
n − 1√
2πσ 2 e−A /2σ .
2 2
=
2
Because A = n/2 and σ 2 = n, this gives

pe < (n − 1) πn/2e−n/16 .
Ignoring constants, the dominant behavior can be coarsely expressed as e−(n−log n) . This
coarse expression shows that the probability of failure of a correlation attack eventually
goes to zero exponentially fast in the length of the available plaintext n.

7.10 Pseudorandom sequences

The task of additive keystream encryption requires the availability of a long and
seemingly random sequence of numbers. We will deal only with binary sequences of
this kind. The binary sequence should be many millions or even billions of bits in length,
and the same sequence must be known and synchronized at both the encryptor and the
decryptor. Such a sequence is called a one-time pad if it is maximally random. There are
severe practical problems in requiring such a long sequence to be maximally random
because a true maximally random sequence cannot be compacted; it must be stored
at a rate of one stored bit per sequence bit. To generate, distribute, and store millions
or billions of random bits securely may be impractical. The problem of generating
and communicating these bits to both the encryptor and decryptor, which, presumably,
are not normally at the same place is an important consideration. The transfer of the
random sequence must be through a secure channel, such as a courier, that uses no
encryption because if encryption were used, that encryption itself requires a random
sequence. The key must also be protected while waiting to be used. Consequently,

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 211 7.10 Pseudorandom sequences

in most practical applications, a shorter binary sequence is repeatedly modified and

reused in both the transmitter and the receiver according to a fixed procedure in
order to generate a long sequence, albeit one that is not maximally random. The long
sequence so generated is then called a pseudorandom sequence, and the short sequence
from which it is generated is called the key sequence. This chapter has considered such
sequences in considerable depth in terms of their generation. This raises some questions
about the generality of those sequences. The purpose of this section is to briefly
consider pseudorandom sequences as such, and not as the results of the methods of
generation.
Loosely, a pseudorandom binary sequence is a periodic sequence of ones and zeros
with period n that over small intervals has the appearance of a random sequence.
Roughly, the contiguous segments of r bits from the sequence will take on each of
its 2r possible patterns almost equally often. A pseudorandom sequence is generated
from a key sequence by a specific rule. Therefore if the key is known, pseudorandom
sequences are quite deterministic and not very complex; nevertheless, they exhibit a
superficial appearance of randomness. One tries to design the function that maps the
key sequence into the pseudorandom sequence so that the superficial randomness is as
unfathomable as would be true randomness.
How should one define a pseudorandom sequence? The theory of the generation of
pseudorandom sequences is quite extensive and full of subtlety. We have presented an
extensive introduction in this chapter. Apparently, to mimic randomness, we should
require that about one half of the bits are ones and about one half are zeros; that
about one fourth of all pairs of bits are of each possibility (00, 01, l0, and 11); and in
general, we should require that about 2−r of all r-tuples of bits are of each possibility.
However, we cannot insist on this requirement for an arbitrarily large r if the sequence
is generated by a finite-state machine, because such a pseudorandom sequence must
eventually be periodic.
Moreover, if we are too insistent on making every sequence appear to be fully ran-
dom, we eliminate many sequences from consideration. It is a philosophical curiosity
that the more constraints we put on a sequence in order to call it pseudorandom,
the less freedom there is in the sequence and the more deterministic it becomes.
If we impose strong enough constraints on the frequency of occurrence of subse-
quences, then we reduce the possible choices to those sequences known as deBruijn
sequences. These are the periodic sequences of period 2m for which every possible sub-
sequence of length m occurs. By deleting one symbol from the all-zero subsequence,
one obtains a periodic sequence of period 2m − 1 in which, except for the all zero
subsequence, every subsequence of length m occurs once. Among these shortened
deBruijn sequences are the maximal-length sequences which are those produced by a
cycle of an element of a finite field. In general, there are many such shortened deBruijn
sequences of period 2m , many of which have linear complexity much larger than m,
which means that they cannot be generated by a linear-feedback shift register of length

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 212 Stream ciphers

m or less. Moreover, we lack a general theory for generating the full family of long
deBruijn sequences.
We can define a pseudorandom sequence in terms of the periodic correlation function.
Let ck for k = 0, . . . , n − 1 be a binary sequence taking the values in the bipolar
alphabet {−1, +1}. The periodic autocorrelation function is
n−1
φi = ck c((k+i)) ,
k=0

where the double parentheses denote modulo n. A pseudorandom sequence of length n

is defined loosely as a binary sequence of length n taking values in the bipolar alphabet
such that for i = 0, |φi | is small compared to φ0 . This definition avoids firm constraints
on subsequences, yet it does impose some control over them. The imprecision in the
definition arises because we have not specified what it means to be small compared to
√
n. The rule of thumb is that small means on the order of n.
The definition can be generalized from one sequence to a set of sequences. A
pseudorandom set of sequences of length n is defined imprecisely as a set of pseudo-
random sequences of length n such that the cross-correlation between any two distinct
sequences is small compared to n.

7.11 Nonlinear sets of sequences

To complete the study of sequences in this chapter, we will briefly discuss sets of
sequences. Although sets of sequences do not play a significant role in cryptography,
they are a visible part of the literature of binary sequences, and so provide additional
context for the study of individual sequences. They are also a bridge into other related
topics.
A set of binary sequences consists of multiple sequences of the same length n defined
by a common rule. For example, the set of cyclic translations of a maximal sequence
of blocklength n, studied in previous sections, forms a set of sequences of blocklength
n. This set is an example of a set of binary sequences constructed in F 2 . It is a linear
set of F 2 sequences because the sum of two such F 2 sequences is another such F 2
sequence.
A maximal sequence can be used to construct other sets of sequences. We will
construct nonlinear sets of F 2 sequences, meaning that the sum of two sequences in
such a set is not, in general, an element of that set of sequences. In this section, we
describe two nonlinear sets of sequences, namely the Kasami sequences and the Gold
sequences, which are sets of sequences that have good correlation properties when
represented as sequences in the bipolar alphabet {−1, +1}. Two bipolar sequences
from the same set of Kasami sequences or the same set of Gold sequences are unlikely

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 213 7.11 Nonlinear sets of sequences

to be confused even when observed in the presence of severe noise and interference.
The Kasami sequences and the Gold sequences are constructed in F 2 from certain
combinations of the maximal sequences.
A designated set of Kasami sequences is also called a Kasami code. A standard
set of Gold sequences is also called a Gold code. First, we will describe the Kasami
sequences. Let n = 2m − 1 for m even, and choose an m-sequence a of blocklength
n = 2m − 1. Because m is even, n factors as

n = (2m/2 − 1)(2m/2 + 1).

Consequently, start with any bit position of a, and take every (2m/2 + 1)th bit of a
cyclically repeated to obtain n bits. This gives a sequence b of blocklength n that has
a period of length 2m/2 − 1 with 2m/2 + 1 repetitions of this period. In other words,
sequence b is obtained by cyclically decimating a by 2m/2 + 1. There are 2m/2 − 1
distinct cyclic translations of b. The Kasami code is the set of these cyclic translations
together with a itself. Thus

C = {a, a + T  b :  = 0, . . . , 2m/2 − 2},

where the operator T denotes a cyclic shift by one bit position. There are 2m/2 Kasami
sequences in a Kasami code, each sequence having blocklength n. We can evaluate
the Kasami code using the cross-correlation function. Given two sequences c and c of
length N, the periodic cross-correlation function is
N−1
 
φi (c, c ) = ck c((k+i)) .
k=0

The cross-correlation functions and the autocorrelation functions (except for the
main peak) of sequences of a Kasami code (in the bipolar alphabet) take values only
in the set {−1, 2m/2 − 1, −2m/2 − 1}. Hence, a pair of sequences from a Kasami code
has a cross-correlation function whose magnitude is never larger than 2m/2 + 1.
For example, a Kasami code with m = 10 has 32 sequences of blocklength 1023.
Any pair of Kasami sequences in this Kasami code has a cross-correlation function
with a magnitude not larger than 33, whereas the central value of each autocorrelation
function has magnitude 1023.
A Gold code is a different set of sequences that are also constructed from maximal
sequences, but by a different rule. These are the Gold sequences. For a given m, let
a and b be a pair of distinct maximal sequences that will be specified later. The Gold
code is the set

C = {a, b, a + T  b :  = 0, . . . , 2m − 2},

where the operator T denotes a cyclic translation by one bit position. The Gold code C
contains 2m + 1 sequences of blocklength 2m − 1.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 214 Stream ciphers

To complete the description, we need to specify a and b. These are two maximal
sequences of blocklength 2m − 1, chosen so that their cross-correlation function has a
maximum value 2(m+2)/2 + 1. Such a pair of maximal sequences will always exist.
The cross-correlation functions and – except for the main peak – the autocorrelation
functions of elements of a Gold code in the bipolar alphabet only take values in the
set {−1, −2(m+2)/2 − 1, 2(m+2)/2 − 1}. Hence, the largest magnitude of any cross-
correlation function of any pair of sequences from C is 2(m+2)/2 + 1.
For example, a Gold code with m = 10 consists of 1025 sequences each of block-
length 1023. Any two of the Gold sequences in this code have a cross-correlation
function whose magnitude is not larger than 65. Each autocorrelation function of
a Gold sequence has a central value equal to 1023, and elsewhere is not larger
than 65.

Problems for Chapter 7

7.1 By showing that it cannot be divided by any first-degree or second-degree

polynomial, prove that x 5 + x 2 + 1 is an irreducible polynomial over F 2 . Why
is this a proof? Is it a primitive polynomial? Sketch a linear-feedback shift register
based on this polynomial. What is the length of the maximal-length sequence
generated by this shift register? Plot the periodic autocorrelation function for
the sequence expressed in the bipolar alphabet.
7.2 Two periodic binary sequences with periods n1 and n2 are componentwise added
modulo two. What is the period of the resulting sequence?
7.3 Let p(x) be a primitive binary polynomial of degree m. Let c be an m-sequence
of length 2m − 1 generated by p(x).
a Prove that every cyclic shift of c is also an m-sequence generated by p(x).
b Prove that every linear combination of two such m-sequences is also such an
m-sequence.
c Prove that each of these m-sequences has 2m−1 ones and 2m−1 − 1 zeros.
d Prove that any two of these sequences agree in exactly 2m−1 − 1 places.
7.4 Prove that a maximal-length binary shift-register sequence of length 2m − 1
displays every r-tuple 2m−r times, except for the all-zero r-tuple, which it
displays 2m−r − 1 times.
7.5 Let f (v1 , v2 , . . . , vm ) be any function from F m
2 to F 2 . Define the sequence
v = (v1 , v2 , . . .), by

vm+i = f (vi , vi+1 , . . . , vi+m−1 )

for i = 1, 2, 3, . . ..

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 215 Problems

a Prove that the sequence is eventually periodic.

b Prove that there is a minimum value of L (called the linear complexity of the
sequence) for which a linear recursion
L
vi = − k vi−k
k=1

exists.
c Conclude that every finite-state sequence can be regarded as a shift-register
sequence. What can be said about the relationship between m and L?
7.6 a Does a periodic binary deBruijn sequence of length sixteen contain every
binary 4-tuple as a segment?
b Can a periodic binary deBruijn sequence of length sixteen be generated by a
linear-feedback shift register?
7.7 Show that it is easy to convert any maximal linear-feedback shift-register
sequence into a deBruijn sequence by adding m−1=1 v i− to the feedback, where
v is the complement of v.
7.8 a Is the binary recursion with boolean feedback function
f (vj −1 , vj −2 , vj −3 ) = 1 + vj −2 + vj −3 + vj −1 vj −2
a deBruijn sequence? Write out the first sixteen outputs.
b Show that the deBruijn sequence 0011 with period four can be produced by
a linear-feedback shift register of length three, but cannot be produced by a
linear-feedback shift register of length two.
7.9 How many periodic binary sequences of period four are there? How many
deBruijn sequences of length four are there? How many maximal-length
sequences of length four are there? Can every m-sequence be converted to a
deBruijn sequence by inserting an additional zero? Can every deBruijn sequence
be obtained in this way?
7.10 Prove that a binary nonlinear recursion vj = −f (vj −1 , vj −2 , . . . , vj −L ) with
boolean function f is nonsingular if, and only if,
f = vj −L + g(vj −1 , . . . , vj −L+1 )
for some boolean function g(vj −1 , . . . , vj −L+1 ).
7.11 Let p(x) be an irreducible polynomial over F 2 of degree n, and let β be a zero
of p(x) in a suitable extension field. What can be said about the order of β?
Express the other zeros of p(x) in terms of β.
7.12 How many cyclic binary maximal-length sequences of period n are there? How
many zeros are there in one period? How many ones? How many times does
each subsequence of length r bits appear (regarding the sequence cyclically)?
7.13 Prove that the GSM stream cipher clocking strategy will always eventually clock
each of the three shift registers, and so cannot stagnate.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 216 Stream ciphers

7.14 Prove Key’s theorem for an arbitrary output order λ.

7.15 A self-shrinking keystream consists of a linear-feedback shift-register sequence
that has been postprocessed two bits at a time by the following rule:

01 → 0
11 → 1
00 → skip
10 → skip .

Starting with a maximal sequence of length fifteen, determine the corresponding

self-shrinking keystream. What is its period? Are there any advantages in using
overlapping or noncontiguous bit pairs? How would you attack a self-shrinking
keystream?
7.16 Can you construct a periodic binary sequence of length fifteen that contains all
fifteen nonzero subsequences but is not a maximal shift-register sequence?
7.17 Is it meaningful to construct a self-shrinking keystream from a binary deBruijn
sequence?
7.18 Prove that
 ∞
1 1 2
√ e−x /2 dx < e−z /2
2

z 2π 2
for z > 0.

Notes for Chapter 7

A comprehensive early study of linear-feedback shift-register sequences can be found

in the books of Golomb (1964, 1967), who early on advocated the role of shift-register
sequences in cryptography. Shift-register sequences, also known as linear-recurring
sequences, have been studied by Carmichael (1920), Ward (1933), and Hall (1938). An
important special case consists of those sequences called maximal-length sequences
or, more simply, m-sequences. Maximum-period nonlinear sequences were introduced
by deBruijn (1946) and Flye Sainte-Marie (1894), who gave the formula for the num-
ber of such sequences. The linear complexity of deBruijn sequences was studied by
Etzion (1999). A general treatment of stream ciphers can be found in the book by
Rueppel (1986).
Many good algorithms, such as the Berlekamp–Massey algorithm, are known for
computing the shortest linear recursion that produces a given sequence. Massey gave
a statement relating the linear complexity of a sequence to the linear complexity of a
truncated subsequence. Blahut (1979) gave a statement relating the linear complexity
of a sequence to the Hamming weight of its Fourier transform. Key (1976) gave a

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]
 217 Notes for Chapter 7

bound on the linear complexity of a nonlinear recursion. We have emphasized the role
of the Fourier transform in the proof of Key’s theorem. Nonlinear recursions are also
studied in the work of Chan, Goresky, and Klapper (1990). Klapper (1994) shows
that the linear complexity of a binary sequence can be large when viewed as a binary
sequence, yet can be small when the sequence is regarded as a sequence of symbols in
an extension field.
The nonlinear combining of multiple shift-register sequences, or of multiple trans-
lates of a single shift-register sequence, has been widely studied, but this is a vast topic
with many aspects that have not yet been explored. A bound on the linear complex-
ity of a binary sequence obtained by nonlinear combining of shift-register sequences
was obtained by Selmer (1966) and Herlestam (1986). This bound was shown to be
tight under certain nonrestrictive conditions by Rueppel and Slaffelbach (1987). The
Geffe (1973) cipher, the Beth–Piper (1984) cipher, and the shrinking cipher that was
proposed by Coppersmith, Krawczyk, and Mansour (1993) are elementary nonlinear
ciphers. The correlation attack on nonlinear sequences was introduced by Siegen-
thaler (1984), with related work by Meier and Staffelbach (1988, 1989). Brynielsson
(1985) argues that binary sequences must have a conflict between good linear com-
plexity and strong correlation immunity because there are so few binary functions.
Sequence sets with good correlation properties are discussed in the books by Golomb
and Gong (2005) and by Goresky and Klapper (2012).
The GSM stream cipher is widely used in cellular telephony. That cipher, and its two
variations designated A5/1 and A5/2, were developed in 1987. All details of the GSM
cipher were kept secret, eventually becoming public only indirectly and over time. The
GSM cipher has received widespread and intense scrutiny and has been successfully
attacked, although it appears that the known attacks still require considerable effort to
recover a plaintext message and are far beyond the casual user.

Downloaded from [Link] University of Birmingham, on 19 Nov 2019 at 08:06:37, subject to the Cambridge Core terms of use, available at
[Link] [Link]