. 4
( 16)



Furt,herniore, suppose the following index rotors are available.

a. Calculate the work factor for an attack on this three rotor Sigaba,
using the analogous assumptions and approach a s the Sigaba at-
tack discussed in this chapter. Specify the primary work and the
secondary work. Also estiniate the number of known plaintext
letters required.
b. Implement this three rotor Sigaba and encrypt the message below.
where aiu” represents a blank space. Use thc following settings:
cipher rotors 233, cipher rotor orientations 101 (where 0 is the
forward orientation and 1 is reverse orientation). cipher rotor ini-
tializations ABC. control rotors Ol5>control rotor orientations 110,
control rotor initializations ZYX, index rotor ordering 201, index
rotor initialization 965.
i 0 1 2 3 4 5 6 7 8 9 1011121314151617181920
Plaintext I Y0U ARE HE
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Plaintext Y0U ME AND
i 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
Plaintext W E ARE ALL

c. Iniplenient the attack in part a. Show that you can recover the
settings used to encrypt the message given in part b.

27. This problem deals with the secondary phase of the Sigaba attack dis-
cussed in the text.

a. For any pair of iiiputs to the index rotors, the corresponding num-
ber of control rotor output letters ranges from 1 to 11. All pairs
and their corresponding values are listed in Table 2.10. Any index

permutation yields five pairs of outputs, one pair for each C, in
Figure 2.22. These five output pairs correspond to five input pairs.
Since the index permutation is a permutation, the five input pairs
must include each of 0 through 9 exactly once, and all 26 letters
from the output control rotors must appear. Count the number of
valid sets of five pairs, using Table 2.10.
b. How many distinct groupings are there in a., where groupings are
considered distinct only if the numbers are different, not just the

28. Consider the Sigaba attack discussed in the text. There are = 45
choices for the pairs of index permutation inputs that get mapped to
the C,. As discussed in the text and in Problem 27, the probability
that C, is active (and, therefore, rotor i steps) is determined by the
number of control rotor letters that feed into the pair of outputs that
determine C,. The number of letters that can feed into a C, is in the
range of 1 , 2 , 3 , .. . , 11.

a. For each value k = 1 , 2 , 3 , .. . ,11, determine the “stepping percent-
age” for Ci when it is connected to exactly k control rotor letters.
These percentages will sum to much more than one, since more
than one rotor generally steps. Hint: Assume all outputs of the
control rotors are equally likely. Generate all of these equally
likely outputs, map these to the corresponding index perniutation
inputs, and count the number of times that at least one element
of each of the pairs in Table 2.10 occurs. Use this information to
answer the question.
b. Suppose that only one cipher rotor, say, i steps. What do you
irnmediatcly know about the index permutation inputs that are
combined to form Ci?
c. Suppose that exactly two cipher rotors, say, i and j step. What do
you immediately know about the index permutation inputs that
are combined to form Ci and Cj?

29. For each letter encrypted by the Sigaba cipher machine, all five cipher
rotors step and three of the five control rotors step. The two remaining
control rotors and all five index rotors do not step. Since the cipher and
control rotors each permute 26 letters, the maximum possible period for
Sigaba is 268. However, in [146] it is claimed that the Sigaba cipher has
a period of just 264, regardless of the initial settings. Write a program
to determine the period of Sigaba for a given key. Use your program to
verify that the Sigaba period is 264 for each of 100 randomly selected
keys, or find a key that does not yield a period of 264.

30. Suppose that we create a new cipher, Sigaba Lite (SL), which is similar
to Sigaba with the exception that SL uses only four cipher rotors. As
with Sigaba, in SL from one to four (inclusive) of the cipher rotors steps
with each letter encrypted. All other components of SL are the same
as those of Sigaba. Also, SL is equipped with nine cipher and control
rotors, that is, the number of rotors that will fit in the device (as is the
case for Sigaba). Show that if sufficient known plaintext is available,
then there is an attack on SL requiring work of about 2*' or less. Hint:
Mimic the Sigaba attack outlined in this chapter.

31. For the primary phase of the Sigaba attack:

a. Determine the expected number of consistent paths (without merg-
ing) in the random case and the causal case.
b. Determine the expected number of consistent paths (with merging)
in the random case and the causal case.

32. Consider the Sigaba attack discussed in this chapter.

a. Using the results in Table 2.7, estimate the number of survivors
from the primary phase, assuming that 40 know plaintext letters
are available and paths are merged, but otherwise all surviving
paths are saved.
b. What is the work factor for the primary phase using the method
in part a?
c. What is the total work, including the secondary phase, for the
attack as outlined in this problem?

33. This problem deals with the Sigaba attack discussed in this chapter.

a. Compute the average probability p,, for i = 1 , 2 , 3 , 4 , that pre-
cisely i cipher rotors step, where the average is taken over all pos-
sible index permutations and all possible control rotor outputs.
Hint: Model the control rotor outputs as uniformly random. Then
there are equally likely outputs of the control rotors and these
outputs are combined as indicated in (2.7). Test each of these with
each of the 10!/32 distinct index permutations (see Section 2.4.3).
Compare your results to Problem 22, part c.
b. How can you use the result of part a of this problem to improve
on the Sigaba attack described in this chapter?
This Page Intentionally Left Blank
Chapter 3

Stream Ciphers

If we are carried along the stream we fear nothing,
and it is only when we strive against it,
that its progress and power are discernible.
- John Owen

Stream ciphers are a class of symmetric ciphers that operate something like
a one-time pad. The crucial difference is that a stream cipher only requires
a small key, whereas a one-time pad cipher requires a key that is the same
length as the original message. While a one-time pad cipher is provably secure
(provided it is used correctly), it is generally impractical since the key is the
same length as the message. After all, if Alice and Bob can securely distribute
a key that is the same length as the message, why not simply distribute the
message by the same means as the key and do away with the cipher?
In a stream cipher, a relatively small key is “stretched” into a long
keystream that can then be used just like a one-time pad. A stream ci-
pher has far fewer keys than the number of possible keystreams, so we cannot
prove that such a cipher is secure-at least not using a similar argument as
is used to prove the one-time pad is secure. In effect, a stream cipher trades
the provable security of a one-time pad for practicality.
A generic stream cipher is illustrated in Figure 3.1, where the key is
input to the stream cipher algorithm, which then generates the keystream ki,
for i = 0, 1 , 2 , . . .. This keystream can be generated in bits, bytes, or other
sized chunks. Encryption is accomplished by XOR of the keystream ki with
the plaintext pi to yield the ciphertext ci. To decrypt, the same key is input
to the stream cipher algorithm, so that the same keystream is generated.
Then the keystream bits are XORed with the ciphertext to yield the original


plaintext. As with the one-time pad, this decryption relies on the fact that
if c, = p , @ k, then c, @ k, = ( p , fBk , ) @ k, = p,. That is, regardless of the
value of the bit k,, we have k , @ k , = 0.

L L,
stream stream



Figure 3.1: Generic stream cipher.

We must assunie that Trudy, the cryptanalyst, knows (or can guess) some
of the plaintext. For a stream cipher, known plaintext and the corresponding
ciphertext immediately enables Trudy to recover part of the keystream. If
Trudy can recover more of the keystream from such a captured segment:
then the stream cipher is insecure. Therefore, the security of a stream cipher
depends on properties of the generated keystream.
But what properties should a keystreani ideally satisfy? The keystream
needs to be “random,” but there are many definitions of randomness, and
many of these “random” sequences would be poor keystreams. For example,
a common method for generating pseudo-random sequences is to employ a
linear congruential generator (LCG). The output from these generators satisfy
many statistical properties that make them excellent random sources for a
variety of applications (for exaniple, simulations). The bits generated by an
LCG could be used as a keystream, with the seed value acting as the key.
However, an LCG would make a very poor stream cipher, since given a sniall
section of the keystreani it is not difficult to determine the entire sequence [9].
This is exactly what we must avoid with a stream cipher keystream. In
other words, statistical randomness is insufficient to ensure the security of a
keyst rcarn.
The crucial property required of a keystream sequence is that it be unpre-
dictable, or cr?gptop-aphically strong. Intuitively, it is clear what we mean by
unpredictable, but there is no entirely satisfactory technical definition. We
discuss this problem briefly in the ncxt section.
In this chapter we first discuss linear feedback shift registers (LFSRs),
which are often used as building blocks for stream ciphers. We also consider
correlation attacks against a particular class of LFSR-based stream cipher.

Then we discuss attacks on three specific stream ciphers, namely, ORYX,
RC4 and PKZIP. Although many (if not most) stream ciphers generate their
keystreams one bit at a time, coincidentally, all three of these ciphers generate
their keystreams one byte at a time.
The ORYX cipher is based on shift registers. Its design is inherently weak
and we present a relatively straightforward attack.
Although most stream ciphers are designed to be efficient in hardware,
RC4 was specifically designed to be efficient in software implementations.
The RC4 attack that we cover relies on a specific weakness in the way that
the key is used. This attack is a serious concern in WEP, a wireless protocol
that we briefly discuss. However, a minor modification to the way that RC4 is
used in WEP renders this attack ineffective and, consequently, RC4 itself can
be considered secure (when properly used) in spite of this particular attack.
PKZIP is an interesting cipher. As with RC4, the design of PKZIP is not
based on shift registers, and it was designed to be highly efficient in software.
The PKZIP cipher is somewhat weak, but the attack is relatively complex
and involved.

Shift Registers

“Give your evidence,” said the King;
“and don™t be nervous, or I™ll have you executed on the spot.”
This did not seem to encourage the witness a t all:
he kept shifting from one foot to the other and in his confusion
he bit a large piece out of his teacup instead of the bread-and-butter.
- Alice in Wonderland

A shift register consists of a series of memory elements or stages, each capable
of containing a single bit. The register stages are initialized with an initial
fill, then at each step, the contents are shifted one position to the left™, with
a new bit shifted into the rightmost position. The bit that is shifted off the
left end is usually taken as the output. For the shift registers we consider, the
new rightmost bit is calculated as a function of the current fill of the register.
Appropriately, this function is known as the feedback function.
For example, consider the shift register in Figure 3.2. If the function f is
given by
f(G, l , G + 2 ) = 1 CE 5 CE 2i+2 CE %+lZi+2
Zi+ 2

and the initial fill is 111, then one period of the output sequence is given
˜Of course, shift registers can also be viewed as shifting to the right, but for our purposes
it is more convenient to consider left-shifting shift registers.

by 11100010, which happens to be a de Bruijn sequence.'

Figure 3.2: Shift register.

If a shift register has a linear feedback function, that is, if the function
involves only XOR operations, not multiplication (equivalently, AND oper-
ations), then it is known as a linear feedback shift register (LFSR). For our
purposes, LFSRs are the most important shift registers. Historically, stream
ciphers employed in high data-rate systems were based on LFSRs, since shift
registers are easily implemented in hardware and they can produce keystream
bits at, or near, the clock speed. Today, software-based systems are capable
of encrypting at extremely high data rates, which is one reason why stream
ciphers in general, and LFSR-based cryptosystems in particular, are on the
decline. In the realm of symmetric ciphers, software-based block ciphers
are in the ascendancy, and this trend appears certain to continue. How-
ever, there remain applications where stream ciphers are preferable, such as
error-prone wireless environments and some extremely resource-constrained
A simple LFSR is illustrated in Figure 3.3. This type of LFSR is some-
times referred to as a Fibonacci register. There is another common type of
linear shift register known as a Galois register, where the shifting and the
feedback is slightly more complex. We do not discuss Galois registers further
here; see [57] for more details on these two types of LFSRs.

Figure 3.3: A linear feedback shift register.

The feedback function for the LFSR. in Figure 3.3 is

It is standard practice t o denote linear feedback functions as polynomials,
where the indices become exponents. For example, x+ is represented by z2;

'A de Bruijn sequence is a binary sequence of period 2" in which each binary n-tuple
appears exactly once, provided we consider the sequence as a cycle.

while xi+5 is represented by x5 and xi by xo = 1. Then rewriting (3.1)
as zi+5 @ xi+2 @ xi = 0, we have the equivalent polynomial representation

x5 + x2 + 1.
Such a polynomial is known as the connection polynomial of the LFSR, since
it compactly represents the “connections” required to implement the LFSR.
There is a rich mathematical theory applicable to connection polynomi-
als, which enables us, for example, to determine the period of the sequences
generated by an LFSR. For an introduction to this mathematical theory and
further pointers to the literature, see Rueppel™s book [125]. There is also a
corresponding theory for so-called feedback with carry shift registers (FCSRs,
also known as 2-adic shift registers). An introduction to FCSRs can be found
in [61].

Berlekamp-Massey Algorithm
Given a binary sequence, the Berlekamp-Massey Algorithm provides an effi-
cient method to determine the smallest LFSR that can generate the sequence.
Here, “size” refers to the number of stages in the LFSR. The size of the mini-
mal LFSR is known as the linear complexity (or linear span) of the sequence.
Due to the threat of known plaintext attacks, a keystream must have a
large period. Furthermore, due to the Berlekamp-Massey Algorithm, there
must not exist any small LFSR that can generate a given keystream sequence.
We expand on this point below, after we have discussed the Berlekamp-
Massey Algorithm and some of its implications.
The Berlekamp-Massey Algorithm appears in Table 3.1, where

s = (so, s1,. . ., Sn-1)
denotes the binary sequence under consideration, L is the linear complexity
and C ( x ) is the connection polynomial of the minimal LFSR. Note that the
coefficients of all polynomials are to be taken modulo 2 . Also, d is known as
the discrepancy, and the connection polynomial is of the form

+ q x + c2x2 f . . . + c&.
C ( x ) = co

The Berlekamp-Massey Algorithm processes the sequence s sequentially
and at step k , the polynomial C ( x ) is the connection polynomial for the
first k 1 bits of s and L is the corresponding linear complexity. At step k , if
the discrepancy is d = 0, then the connection polynomial C ( x ) computed at
step k - 1 is also the connection polynomial for so, s1,. . . , s k and no change
to C ( x ) or L is required. If, on the other hand, the discrepancy is d = 1,
then C ( x ) must be modified, and the linear complexity L increases if the
current value of L lies below the n/2 line.

Table 3.1: Berlekamp˜-MasseyAlgorithm

// Given binary sequence s = ( S O , S I , s2,. . , ˜ ˜ - 1 )
// Find linear complexity L and connection polynomial C(z)
C(z) = B ( z )= 1
m = -1
while N < n // n is length of input sequence
d = SN C CISAT- 1 CB C ˜ S N - ˜. . . @ C L S N - L
B @
if d == 1 then
T ( z )= C(z)
C ( x )= C ( x )+ B(z):CN-T'L
if L 5 N / 2 then
B ( z )= T ( z )
end if
end if
end while
end BM

Next, we illustrate the Berlekamp-Massey Algorithm. Consider the peri-
odic sequcnce s,with one period given by

. . ,s7) = 10011100.
s= (3.2)

For this sequence, the first few steps of the Berlekamp-Massey Algorithm are
illustrated in Table 3.2.
For the periodic sequence ( 3 . 2 ) , the linear complexity is L = 6 (Problem 1
asks for the connection polynomial). Therefore, if we let 10011 be the ini-
tial fill of the LFSR corresponding to the connection polynomial determined
by the Berlekamp-Massey Algorithm, the LFSR generates the sequencc s
in (3.2).
Here, we do not attempt to prove the validity of the Berlekarnp-Massey
Algorithm. but we note in passing that the algorithm is closely related to
the extended Euclidean Algorithm and continued fraction algorithms. We
also note one important- but non-obvious--fact, namely, that any 2L con-
secutive bits can be used to completely determine a sequence that has linear
complexity L. That is, after processing 2 L bits through the Berlekamp-

Table 3.2: Berlekamp--Massey Example

sequence: s = (SO, s1,. . , s7) = 10011100
initialize: C ( 5 )= B ( z )= 1, L = N = 0, m = -1
T ( 5 )= 1, C ( 5 )= 1 + z
L = 1, m = 0, B ( z )= 1
d = SI CB cis0 = 1
T ( z )= 1 5 , C ( 2 )= 1
d = s 2 CB cis1 @ ˜ =0 0
2 ˜

d = s3 CB c i s 2 C‚¬ ˜ 2 CB˜CQSO = 1
T ( 5 )= 1, C ( 5 )= 1 + 5 3
L = 3 , m = 3, B ( z )= 1

Massey Algorithm, the minimal LFSR will have been obtained. Below, we
see that this property has implications for stream cipher design.
It is not too difficult to show that the Berlekamp-Massey Algorithm re-
quires on the order of n2 operations [62], where n is the number of bits
processed and the operations are XOR. This is the most efficient known gen-
eral algorithm for solving the shift register synthesis problem. However, there
are more efficient algorithms for certain special cases; see Problem 4 for an
example of such an algorithm.

Cryptographically Strong Sequences
Before illustrating the use of LFSRs in stream ciphers, we first take a slight
detour to briefly consider some of the properties that keystrearn sequences
must satisfy. Here, we relate these properties to shift registers.
Keystream sequences that are unpredictable, according to some speci-
strong. However, it is
fied set of conditions, are said to be cryptographically
important to realize that this definition is relative to the specified criteria.
While we can specify necessary conditions that a keystream sequence must
satisfy, there are no known sufficient conditions that ensure that a sequence

is cryptographically strong. In a sense, this situation parallels cryptography
in general, where the best that can be said about any practical cipher is that,
as far as we know, nobody has found an efficient attack. That is, we can
never prove that a cipher is absolutely secure, but we can show that it satis-
fies certain criteria that give us some confidence that is likely to be secure in
Note that if at some point, the fill of an LFSR is all zero, then the register
fill will be all zero at every subsequent step. Therefore, an upper bound on the
period length of any LFSR sequence is 2n - 1, where n is the number of stages
in the LFSR. In fact, it is possible for an LFSR to attain this upper bound,
and the resulting maximal length sequences are known as m-sequences. For
example, a 3-stage LFSR with connection polynomial C ( x ) = 1 x2 will
generate a sequence of period length seven for any nonzero initial fill. In
general, if C ( x )is a primitive polynomial [43], then the resulting LFSR will
yield m-sequences for all nonzero initial fills.
While m-sequences have many nice statistical properties [59],they would
be poor choices for keystream generators. Suppose we have a 32-bit key
and we decide to use a stream cipher that consists of a 32-stage LFSR, with
the connection polynomial chosen so that the resulting keystream is an m-
sequence. Then if Trudy is able to obtain just 64 consecutive keystream
bits, she can use the Berlekamp-Massey Algorithm to determine the entire
keystream, which is of length 232 - 1. Recall that with a stream cipher, known
plaintext reveals the keystrearn, so for this example, a very small amount of
known plaintext completely breaks the cipher. Consequently, a single shift
register that generates an m-sequences would be an extremely poor stream
cipher, in spite of its excellent statistical properties and long period length.
In a sense, m-sequences are among the worst keystream sequences. How-
ever, it is possible to combine m-sequences to generate usable keystreams.
We give examples of such keystream generators in the next section.
This discussion of rn-sequences highlights the fact that, as a consequence
of the Berlekamp-Massey Algorithm, a cryptographically strong keystream
must have a high linear complexity. But is this sufficient'? That is, if we

have a sequence with a high linear complexity, can we be certain that it is
a cryptographically strong keystream? In fact, it easy to see that this is not
the case, since any sequence of the form
000. . . 00 1 (3.3)
n.- 1

has linear complexity n, which can be seen from the Berlekamp--Massey Algo-
rithm, or simply by rioting that the only LFSR capable of generating (3.3) is
necessarily of length n. Note that n is the maximum possible linear complex-
ity for a sequence of period n. Nevertheless, the sequence in (3.3) obviously
would not make a good keystream.

One problem with the sequence in (3.3) is that the linear complexity is,
in a sense, concentrated in just a single bit. That is, the linear complexity
is zero, until the last bit is processed, then the complexity jumps from the
minimum to the maximum possible value. Recognizing this, Rueppel [125]
proposes the linear complexity profile as a practical measure of the quality
of a keystream. This profile is simply the graph of the linear complexity L
of S O , s1,. . , s k for each k = 0 , 1 , 2 , .. .. The required L values are obtained
when the linear complexity of s is computed using the Berlekamp-Massey
Algorithm, so it is efficient to determine such a profile. Rueppel has shown
that most sequences have a linear complexity profile that follows the n/2 line
“closely but irregularly,” and he proposes this as a criteria for judging the
quality of a keystream. Figure 3.4 illustrates a linear complexity profile that
satisfies Rueppel™s criteria and would therefore be considered cryptographi-
cally strong by his definition.

0 50
10 20 30 60

Figure 3.4: Linear complexity profile.

In [141] a different criteria for cryptographically strong sequences is con-
sidered. Although the keystream in (3.3) has the highest possible linear com-
plexity, it differs by only one bit from the all-zero sequence, which has the
minimum linear complexity. That is, the sequence in (3.3) is “too close” (in
Hamming distance) to a sequence with small linear complexity. In general, if
a sequence is close to a sequence with a relatively low linear complexity, then
regardless of the linear complexity of the original sequence, it is an undesir-
able keystream. The k-error linear complexity is defined to be the smallest
linear complexity that can be obtained when any k or fewer bits in one period
of a sequence are changed from 0 to 1 or vice versa.

Given a sequence, we can plot the k-error linear complexity versus k , and
for a cryptographically strong sequence, the graph should not have any large
drops, particularly for relatively small k , since any such drop would indicate
that a sequence with much smaller linear complexity lies close to the given
keystream. We refer to the graph of the k-error linear complexity as the
k-error linear complexity profile.
In Figure 3.5 we have illustrated an undesirable k-error linear complexity
profile. This profile shows that the sequence is close to a sequence with a
much smaller linear complexity, as indicated by the sharp drop below the
dotted line for a relatively small value of k .


0 5 15

Figure 3.5: k-Error linear complexity profile.

In fact, the linear complexity profile in Figure 3.4 and the k-error linear
complexity profile in Figure 3.5 were both obtained from the periodic sequence
with period

s = 0001 1010 1001 1010 1000 1010 1001 1010.

The linear complexity profile of this particular sequence appears to satisfy
Rueppel™s criteria, since it follows the n/2 line closely and no regular pattern
is evident. However, the k-error linear complexity profile indicates that this
particular sequence is probably not a strong keystream, since it lies “close” to
a keystream with low linear complexity. For this example, the k-error linear
complexity is more informative than the linear complexity profile.
In the general case, no efficient algorithm for computing the k-error linear
complexit,y is known. However, for the special case where s is periodic with
period length 2n, an efficient algorithm is given in [141].

Shift Register-Based Stream Ciphers
Due to the Berlekamp-Massey Algorithm, we cannot directly use the output
of an LFSR as a stream cipher. The fundamental problem lies with the
linearity of LFSRs. However, LFSRs have useful mathematical and statistical
properties, so it would be desirable to construct stream ciphers based on
There are two generic approaches that are often used to create keystream
generators based on LFSRs. One such approach is illustrated in Figure 3.6,
where a nonlinear combining function f is applied to the contents of a shift
register to yield the keystream sequence. The combining function is intended
to mask the linearity of the LFSR, while taking advantage of the long period
and good statistical properties of LFSR sequences.



Figure 3.6: Stream cipher using one LFSR.

A second approach to constructing a keystream generator from LFSRs
is illustrated in Figure 3.7. Again, the purpose of the nonlinear combining
function f is to effectively hide the linearity of the underlying LFSRs. In
both of these examples, the key is the initial fill of the LFSR or LFSRs.




Figure 3.7: Stream cipher using n LFSRs.

The keystream generator in Figure 3.6 is actually a special case of the
generator in Figure 3.7. To see that this is indeed the case, suppose that all

LFSRs in Figure 3.7, are identical to the single LFSR in Figure 3.6, except for
the initial fills. Let the initial fill of LFSRo be identical to the initial fill of the
LFSR in Figure 3.6, while LFSRl has as its initial fill the initial fill of LFSRo
stepped once and, in general, the initial fill of LFSRi is the initial fill of LFSRo
stepped i times. Then the nonlinear combining function f in Figure 3.7 has
access to precisely the same bits at each step as t,he function f in Figure 3.6.
That is, the stream cipher in Figure 3.6 is a special case of that in Figure 3.7.
Consequently, in the discussion below, we restrict our attention to the more
general case, as represented by Figure 3.7.

Correlation Attack
In this section we discuss a correlation attack on a shift register-based stream
cipher. Consider the keystream generator in Figure 3.8, which consists of
three small shift registers and a nonlinear combining function f. The feedback
functions of the shift registers X , Y ,and 2 are

respectively. Suppose that the function f , which determines the keystream
bits k 2 ,is given by


Figure 3.8: Keystream generator.

Lct Ix he the length of the cycle grrierated by the shift register X , and
define l y and t z similarly. Then the keystream generated by stream cipher in
Figure 3.8 has a cycle length of lcm(i?x, t y , i ? z ) . For the registers in Figure 3.8,
the cycle length are i?,y = 7, l y = 15, and l , = 31, provided that none of the

initial fills are all zero and, consequently, the cycle length of this keystream
generator is 3255.
To use the keystream generator in Figure 3.8 as a stream cipher, we require
a 12-bit key, which is used to determine the initial fills of the registers, with
the restriction that no initial fill can be all zero. If Trudy can recover the
initial fills, then she has broken the stream cipher. Of course, in this example,
Trudy can simply use an exhaustive search to recover the initial fills, but we
use this simple example to illustrate a shortcut attack.
Suppose that the initial fill of register X is 011, register Y is 0101 and
register 2 is 11100. Then the key that Trudy wants to recover consists of
these 12-bits of initial fill. For these initial fill bits, the first 31 output bits
for registers X , Y , and 2 in Figure 3.8 are given in the first three rows of
Table 3.3, with the keystream given in the fourth row.

Table 3.3: Register Bits and Keystream

0 , 1 , 2 , . . . ,29,30
Bits =



By Kerckhoffs™ Principle, we assume that Trudy knows the LFSR feedback
functions and the nonlinear boolean function f . Trudy™s attack will take
advantage of certain properties of the function f .
The truth table for the boolean function f(z,y, z ) = zy @ yz @ z is given
in Table 3.4. Note that f ( z , y , z ) = z and f ( z , y , z ) = z both occur with
probability 314. Trudy can take advantage of this fact to efficiently recover
the initial fills (that is, the key) for the keystream generator in Figure 3.8.

Table 3.4: Truth Table for f ( z ,y, 2 ) = zy @ yz @ z

x g z “y
0 0 00 0 0
0 0 10 0
00 0 0
0 1
0 1 10 1 0
00 0 0
1 0
1 0 10 0 1
1 1 01 1
11 1 1
1 1 -

The attack we consider here requires known plaintext. Since we are deal-
ing with a stream cipher, known plaintext immediately gives Trudy the cor-
responding bits of the keystream.
Suppose that Trudy, via known plaintext, recovers the 31 keystream bits
in the last row of Table 3.3. Trudy can then simply try all possible initial
fills for the X register, and for each of these, she can generate the first 31
bits of the corresponding X sequence. For the correct initial fill of X she
expects to find Ici = xi with probability 3/4, and for an incorrect initial fill
she expects that the keystream will match the X register sequence with a
probability of about l/2. Therefore, Trudy can recover the X register initial
fill by simply trying all 23 possibilities and computing the correlation with
the known keystream bits for each putative fill.
For example, suppose that Trudy guesses the initial fill of X is 111. Then
the first 31 bits of X would be


If we compare these bits to the keystream bits Ici in Table 3.3, we find 15
of the 31 bits match, that is, about 1/2 of the bits match, which implies
that, 111 is not the correct initial fill of X . On the other hand, if Trudy tries
the correct initial fill for X , namely, 011, she finds 26 matches, as can be
seen in Table 3.3. Since this is close to the expected number of matches for
the correct initial fill, Trudy can assume that she has found the initial fill
of X . For this particular combining function f , Trudy can apply the same
and with knowledge of the X and 2
technique to recover the initial fill of 2,
fills, she can easily recover the initial fill of Y .
In this example, the work required for the correlation attack is on the
order of
+ 2 4 + 23 < 25,

while a nai've exhaustive key search attack has a work factor if 2". In general,
if there are n shift registers of sizes No, N1,. . . , Nn-l, respectively, then the
work for an exhaustive key search attack is
2 IV,,+N , + ...+N,, .˜1 1

while, in the ideal case, the work factor for a correlation attack is

which highlights the strength of this method of attack. This type of correla-
tion attack is a classic divide and conquer approach.
Stream ciphers based on designs such as that in Figure 3.8 must) be corre-
that is, the conibining function f must not leak information
l t o immune,
about, the individual shift registers. Many techniques have been proposed
3.3 ORYX 93

to combine shift registers in ways that are intended to frustrate correlation
attacks. For example, in A5/1 (used in the GSM cell phone system), the
shift registers step irregularly, while in Eo (used in Bluetooth) the stepping
function includes memory of previous stepping, again, creating irregular mo-
tion. For more information on correlation attacks, see [77, 991, Siegenthaler's
original paper [135] or Golit's survey in [58].
Next, we turn our attention to three specific stream ciphers. The first of
these, ORYX, is based on shift registers. However, the attack on ORYX that
we consider does not rely on any correlation properties or similar features
of the shift registers. Instead, other weaknesses in the design of ORYX are
exploited. This attack is relatively straightforward, but is does require that
we delve into the inner workings of the cipher.
Neither RC4 nor PKZIP-the other two stream cipher we discuss in this
chapter-are based on shift registers. Instead, these ciphers are designed
to be implemented in software, which makes them somewhat unusual in the
world of stream ciphers. The attacks on these two ciphers are both relatively
complex, with the PKZIP attack being the more intricate of the two.


Oryx \O"ryx\, n. A genus of African antelopes which includes the gernsbok,
the leucoryx, the bisa antelope (0. beisa),
and the beatrix antelope (0. beatrix) of Arabia.
- dictionary.net

ORYX is a stream cipher developed by the Telecommunications Industry
Association (TIA) as part of an overall cell phone security a r ˜ h i t e c t u r e . ˜
TIA system was briefly used in the late 1990s until its many security flaws
were exposed. Before considering the ORYX cipher, we briefly discuss cell
phone security in general.
TIA is not the only flawed cell phone security architecture. The Global
System for Mobile Communications (GSM) is another cellular system that
has more than its share of security issues. In GSM there are several cryp-
tographic weaknesses, along with protocol-level flaws that open the door to
many different feasible attacks [142]. The cryptographic flaws include attacks
on the encryption algorithms (specifically, A5/1 and A5/2), as well as serious
problems with the hash function (COMP128) that is used for authentication
and key generation. These crypto problems in GSM can be traced to the fact
that Kerckhoffs' Principle was violated, since the GSM crypto algorithms
3The all-uppercase rendering of ORYX is standard, but it is a mystery, since ORYX is
not an acronym.

never received public scrutiny before they were installed in millions of cell
In defense of GSM, it should be noted that it was designed early in the cell
phone (and wireless networking) era, and it was designed with very limited se-
curity goals. In fact, contrary to what you are likely to read elsewhere, it is not
unreasonable to consider GSM security a modest practical success, since none
of the many potential attacks ever became a serious issue in practice [142].
However, the GSM security design goals were clearly too limited, and this is
the root cause of most of the exploitable flaws. So-called “third generation™™
cell phones, as defined by the Third Generation Partnership Project (SGPP),
have a security architecture modeled on GSM, with all of the known flaws
patched [I].
The TIA cell phone security architecture was developed after most of the
flaws in GSM were well-known, so you might expect that TIA would have
learned from the crypto mistakes of GSM. If so, you would be mistaken.
Like GSM before it, TIA violated Kerckhoffs™ Principle, with predictable
results. The weak ORYX cipher discussed here is one of the consequences of
the decision to use ciphers that had not been thoroughly reviewed-the weak
Cellular Message Encryption Algorithm (CMEA) discussed in Chapter 4 is
yet another.
The ORYX cipher was designed to encrypt data sent to and from cellular
phones. Here, “data” includes voice and other messages sent over the phone.
This is in contrast to “control” or signaling information, such as the number
called, which was not encrypted using ORYX. Instead, the CMEA block
cipher mentioned above was used to protect the confidentiality of the control
information. A practical attack on CMEA is given in the next chapter.
The definitive cryptanalysis of ORYX appears in [153],where it is shown
that the entire 96-bit key can be recovered with a minimal work factor, given
about 25 bytes of known plaintext. The fundamental weakness in ORYX
arises from the fact that, for efficiency, it generates a keystream byte at each
step. when a single bit (or perhaps two) would probably be more realistic
given the inherent limitations of the algorithm.

ORYX Cipher
The ORYX cipher employs three shift registers, which we label X , A , and B .
Each register holds 32 bits. Denote the current bits of register X (that is,
the fill of X ) as 20:2 1 , 2 2 , . . . , 2 3 1 . Similarly, let a0 through a31 be the fill
of register A , and bo through b ˜ 1 the fill of register B . At each step of a
register, a single bit, say, y is computed as a function of the current register
fill, then each bit in the register is shifted one position to the right, with the
bit formerly in position 31 being discarded, and the bit y is then inserted into
position 0. For more information on shift registers and their role in stream
3.3 ORYX 95

ciphers, see Section 3.2 or Rueppel™s classic book [125].
When register X steps, the following sequence of operations occur

Y = PX(X)
= 31,30,29,. . . ,
i I
zi = xi-1 for
20 = Y

pX(x) = 2 0 @ x4 @ 2 5 @ 2 8 @ 2 9 @ 210 @ 213 @ 215 @ 217
@ 218 @ 227 @ 231.

Note that the feedback function P is linear and, consequently, X is a linear
feedback shift register (LFSR). Recall that LFSRs were discussed in some
detail in Section 3.2.
For register A we have

Y = PA(A)
31,30,29,. . . , 1
for i
ai = ai-1 =

a0 = Y

where PAis either

PAO(A) a0 @ a 1 @ a 3 @ a4 @ a 6 @ a7 @ a9 @ a10 @ all @ a15
@ a21 @ a22 @ a25 @ a31

PAI(A) a0 @ a1 @ a 6 @ a7 @ a8 @ a9 @ a10 @ a12 @ a16 @ a21
@ a22 @ a 2 3 @ a24 @ a25 @ a26 @ a 3 1 ,

depending on whether bit 229 of register X is 0 (in which case the feedback
function PAO selected) or 1 (in which case P 1 is selected). Note that this is
somewhat analogous to the way that the Sigaba cipher uses one set of rotors
to determine the stepping of another set of rotors.
For register B , a step consists of the sequence of operations

! = pB(B)
= 31,30,29,. . . , 1
for i
bi = bi-1
bo =Y

where the (linear) feedback function PB is defined by

PB(B)= bo @ b2 CE b5 CE b14 @ b15 @ b1g @ b20 CE CE
b30 b31.

We define one iteration of ORYX as follows:

1. Register X steps.

2. If 2 2 9 = 0, then register A steps using PA, to generate the feedback bit.
Otherwise register A steps using PA^.

0, then register B steps once, otherwise register B steps twice.
3 . If 526 =

4. Finally, a keystream byte is generated as

+ +
( H ( X ) L [ H ( A ) ] L [ H ( B ) ] (mod 256),
keystreamByte =

where H selects the “high” byte of the current fill of a register (in
our notation, bits 24 through 31) and L is a known permutation of
the numbers { 0 , 1 , 2 , . . . ,255}. The permutation L is variable, but it
remains fixed for the duration of a given message, and L is known
to the cryptanalyst. The permutation L plays a similar role to the
initialization vector (IV) in RC4 or the message indicator (MI) in the
WWII cipher machines discussed in Chapter 2.

Note that in ORYX, one iteration occurs before the first keystream byte is
The ORYX keystream generator is illustrated in Figure 3.9, where S signi-
and PA^ , and C controls
fies the selection between feedback polynomials PAO
whether register B is “clocked” (that is, stepped) once or twice.

Figure 3.9: ORYX cipher.

The ORYX key consists of the initial fills of the three registers X , A ,
and B , while L is the (non-secret) IV. Given the initial fills, the corresponding
keystream can be generated, as described above. Since each register holds 32
bits, the key is 96 bits.
3.3 ORYX 97

Like RC4, the ORYX cipher generates its keystream one byte at a time.
This improves the efficiency of the cipher, but, in the case of ORYX, it creates
a serious weakness.
Denote the ORYX keystream bytes as ko, k l , k 2 , . . .. Let X , A , and B be
the initial fills of the registers. Then the entire keystream is determined by
these fills and the known permutation L. As mentioned above, the ORYX
registers step before a keystream byte is generated. Consequently, the first
keystream byte is

+ +
ko = ( H ( X ) L [ H ( A ) ] L [ H ( B ) ](mod 256),
) (3.4)

where X , A , and B represent the register fills after one iteration of ORYX.

ORYX Attack
The ORYX attack discussed here requires that some number of keystream
bytes are known. Since ORYX is a stream cipher, known plaintext together
with the corresponding ciphertext would yield the necessary keystream bytes.
In practice about 25 known keystream bytes suffices to recover the entire key.
The attack proceeds by trying each of the 2'' possible values for the
pair ( H ( A ) , ( B ) ) in (3.4). Given a putative value for ( H ( A ) , ( B ) ) ,and
assuming ko is known, we can solve for H ( X ) as

H ( X )= (ko - L [ H ( A ) ] L [ H ( B ) ](mod 256).

Then we attempt to extend A and B by one iteration. To do so, we use the
known keystream byte k l , and solve for

Y = (kl L [ H ( A ) ] L [ H ( B ) ](mod 256).
) (3.5)
- -

If the value Y can be obtained as a shift of X , then A , B , and X are consistent
with the first two keystream bytes, and these partial fills are retained for the
next iteration, where we attempt to further extend A and B so that they
are consistent with k2. If the value of Y in (3.5) cannot be obtained by an
extension of X then the partial fills A and B are discarded.
How many ways are there t o extend a given pair A and B to the next
i t e r a t i ˜ n ?Register A always shifts one position to the right so that a single
new bit appears at the leftmost position in H ( A ) . Register B can shift once,
in which case one new bit appears in H ( B ) , or it can shift twice, in which
case two new bits appear in H ( B ) . This gives a total of 12 possible ways to
extend the current fills of registers A and B. These 12 possible extensions are
listed in Table 3.5. We denote the j t h extension of A as e ( A , j )and similarly
for B .
4Let me count the ways

Table 3.5: Extensions of A and B

Extend Extend
Shift B Fill B
i Shift A Fill A
01 0 0
1 1 1 0 1

2 1 1 0
3 1
1 1 1
1 2 00
1 1 01
1 10
1 1 11
1 00
2 0
9 1 01
1 0
10 10
11 1 11

Now we consider an example that illustrates the steps in the attack. Sup-
pose the key-that is, the initial fills of the registers X , A, and B--is given
by the register fills

( X ,A,El) = (Oxdeadbeef,0x01234567,0x76543210).

Since one iteration occiirs before the first keystream byte is generated, we
do not directly recover the initial register fills, but instead, we recover the
register fills after the first iteration. Let ">>" be the right shift operator.
Then t,he at,tack will recover X >> 1, A >> 1 and either B >> 1 or B > 2, >
depending on whether B shifts once or twice in the first iteration. In this
example, these fills are

( X > 1) = 0 ˜ 6 f 5 6 d f 7 7
( A> 1) = Ox0091a2b3
(I? >> 1) = Ox3b2a1908
(I? >> 2) = Oxld950˜84.
Once the appropriate shifted fills have been recovered, it is a simple matter to
step them back to the actual initial fills and thereby recover the original 96
bit key, if desired. However, this is not necessary if the goal is simply to
decrypt the message.
Trudy the cryptanalyst does not know the register fills, but we assume
that she docs know approximately 25 consecutive keystream bytes, and she
knows the table L used for the ˜nessageunder consideration. Here, we only
3.3 ORYX 99

illustrate the first two steps in the attack, so we only utilize the first and
second keystream bytes.
For this example, suppose

ko = Oxda and kl =Ox31 (3.6)
and the permutation L given in Table 3.6 was used to encrypt the message.
Then, for example, L[Oxa2] = 0x95 since 0x95 appears in row Oxa and col-
umn 0x2 of Table 3.6.

Table 3.6: Example ORYX Permutation L
0 1 2 3 4 5 6 7 8 9 a b c d e f
ed Od 20 a9 c3 36 75 4c 2c 57 00 ae O f
0 31
1 19 4d 44 a0 56 18 66 09 69 6e 3d 25 9c db 3f
2 65 58 la 6d ff d7 46 b3 bl 2b 78 cf be 26 42 2f
3 d8 d4 8e 48 05 b9 34 43 de 68 5a aa 9d bd 84 a2
4 3c 50 ce 8b c5 dO a5 77 If 12 6b c2 b5 e6 ab 54
5 81 22 9f bb 5c a8 dc ec 2d le ee d6 6c 5f 9a fd
6 c8 d5 94 fc Oc lc 96 4f f9 51 da 9b df el 47 37
7 dl eb af f7 a4 03 fO c7 60 e4 f4 b4 85 f6 62 04
8 71 87 ea 17 99 Id 3a 15 52 Oa 07 35 eO 70 b6 fa
9 cb bO 86 a6 92 fb 98 55 06 4b 5d 4a 45 bf 16
a 7c 95 28 38 82 f3 6a f8 fe 79 39 27 2a 5e e7
b 59 b8 lb ca 8d d3 7b 30 90 d2 d9 ac 76 8f 5b
C a7 O e 63 c4 b2 e9 97 91 53 7a Ob 41 08 cl 8c 7d
d 88 24 f5 f2 01 72 e8 80 49 23 9e c6 14 73 ad
e 8a c0 21
29 ef e5 67 61 ba e2 7e 89 64 02 6f fl
f dd b7 c9 cd 3b 93 2e 40 bc 4e a1 cc 74 32 7f

In this attack, Trudy will try all 2“ guesses for the 16 bits ( H ( A ) H ( B ) )
that were used to generate ko. Consider the case where Trudy selects

( H ( A ) H ( B ) )= ( O x b 3 , 0 ˜ 8 4 ) ,
, (3.7)
which is one of the 2“ values that she will test. In this case, Trudy computes
H ( X )= (ko - L [ H ( A ) - L[H(B)])
] (mod 256)
= (Oxda - L[Oxb3] - L[Ox84]) (mod 256)
= (Oxda - Oxca - 0x99) (mod 256)
= 0x77.

Now Trudy must attempt to extend the fills X , A, and B to the next
iteration by trying each of the 12 extensions listed in Table 3.5. For example,
for j = 2 in Table 3.5, Trudy shifts each of A and B by one, and chooses 1
for the next bit of A and 0 for the next bit of B . Then the resulting “high”
bytes are
H ( A )= Oxd9 and H ( B ) = 0x42.

Using these values Trudy solves for

H ( X )= ( k l - L [ H ( A )- L [ H ( B ) ] (mod 256)
] )
= (0x31 - L[Oxd9] - L[Ox42]) (mod 256)
= (0x31 - 0x13 - Oxce) (mod 256)
= 0x50.

However, the previous H ( X ) is 0x77 which can only be extended to ei-
ther Ox3b or Oxbb. Therefore, this particular extension is inconsistent with
the assumed ( H ( A )H ( B ) ) .
On the other hand, consider (3.7) again, and consider the case where
Trudy tries to extend this fill using j = 8 in Table 3.5. Then she shifts A by
one and B by two, choosing 0 for the next bit of A and 00 for the next two
bits of B . In this case, the extensions are

H ( A )= 0x59 and H ( B ) = Ox21

and using these bytes Trudy solves for

H ( X )= ( k lL[H(A)] - L [ H ( B ) ](mod 256)

= (0x31 - L[Ox59] - L[Ox21]) (mod 256)
= (0x31 Oxle - 0x58) (mod 256)

= Oxbb.

This is consistent with shifting the previous value of H ( X ) one position and
filling in the new bit with 1. Therefore, Trudy retains this fill and tries to
extend it further at the next iteration.
For any initial guess ( H ( A ) H ( B ) )Trudy can solve for a consistent value
of H ( X ) . Consequently, Trudy can only discover whether any guess was
correct or not when she tries to extend the fills beyond the first byte. And
it is possible that that some “false positives” will occur, that is, some fills
will be consistent with the keystream for a few steps before failing. We
carefully analyze these probabilities below. Note that, in effect, the attack
we have described performs a breadth-first search. However, a depth-first
search works equally well.
The attack algorithm is outlined in Table 3.7. This algorithm must be
repeated for each of the 2™™ guesses for the initial 16 bits of ( H ( A ) H ( B ) ) .
Recall that e ( A , j ) is our notation from Table 3.5 for the j t h extension of
register A.
Once an iteration of the attack in Table 3.7 returns a solution, there is no
need to continue searching, provided that a sufficient number of keystream
bytes are provided to uniquely determine the key. Below, we show that with
just six keystream bytes we only expect one surviving set of initial fills, and
3.3 ORYX 101

Table 3.7: Outline of ORYX Attack

// Given: keystream bytes ko, k l , k 2 , . . . , kiv,
// table L , and a guess for initial ( H ( A ) , ( B ) )
H ( X )= (ko - L [ H ( A )- L [ H ( B ) ](mod 256)
for i = 1 to N // for each keystream byte
for each (X, , B ) // putative fill
TO extend X with 0
TI = extend X with 1
for j = 0 to 11 // for each possible extension
T x = (ki - L[H(e(A,j))l L [ H ( e ( B , j ) )(mod 256)
if Tx == H(T0)then
save (To,e(A,j),( B , j ) ) next iteration
e for
end if
if TX== H(T1)then
save ( T Ie ( A , j )e ( B , j ) ) next iteration
, , for
end if
next j
next putative fill
next i

after 25 bytes we expect to have determined all of the bits of the (shifted)
initial fills.
Finally, we analyze the performance of this attack. For any initial choice
of H ( A )and H ( B ) , we can use ko to solve for a consistent value of H ( X ) .
This implies that with just a single keystream byte available, we would ob-
tain 65,536 consistent fills. In other words, the first keystream byte yields no
reduction in the number of potential fills. However, if we have ko and k l , then
for each of the 65,536 fills (X, A,B ) obtained in the first step, the pair ( A , )
can be extended in 12 different ways, and for each of these, the implied
extension of X is computed. Each valid extension must match in the seven
rightmost bits of the shifted H ( X ) . Consequently, on average, only one in 128
of the extensions will survive, assuming we can model the byte comparisons
as random. Since L is a permutation it is reasonable t o model the computed
value as a random selection from {0,1,2,. . . ,255). The bottom line is that
using only ko and k l , the expected number of valid fills remaining is
= 6144.
If we extend the attack to include k2, then the expected number of sur-
viving fills is
= 576

and so on. These results are tabulated in Table 3.8 along with a set of
empirically obtained results. It is interesting that the empirical results match
the theoretical results so closely.

Keystream Expected Computed
Bytes Fills
1 65,536 65,536
2 6144 6029
3 576 551
4 54 47
5 5
6 1

The results in Table 3.8 show that Trudy can expect to reduce the num-
her of surviving fills to one single candidate using only six keystream bytes.
However, to completely determine the 32 bits in each register will require at
least 25 keystream bytes, since ko is used to determine bits 24 through 31,
while each subsequent k , determines only a single bit of registers A and X ,
while, on average, each keystream byte determines 1.5 bits of register B .
Since t,he registers step before the first keystream byte is generates, this
attack does not recover the original fills ( X ,A , B ) ,but instead, it recovers the
fills ( X >> l , A >> l , B > s ) , where s is one or two, depending on whether B
steps once or twice on the first iteration. In any case, given the recovered
fills, it is a simple matter to determine the actual initial fills-although it is
not necessary to do so t o decrypt the message.
Assuming that !keystream bytes are used, the expected work required
for this attack is

+ 6144 + 576 + 54 + l) < 22"
1 2 . (65,536

This is an extremely efficient attack to recover a 96 bit key. The space
requirement for the attack is also minimal, as explored further in Problem 13
at the end of this chapter.

Secure ORYX?
As mentioned above, the fundamental problem with ORYX is that it attcmpts
to generate a byte of keystream at each iteration. While this makes for an
efficient cipher, it exposes far too much of the internal state to thc attackcr.


. 4
( 16)