The worm involved in the November Scan of the Month uses a simple stream cipher to obscure its network traffic. The cipher key used by the worm is fixed, so that there is no difficulty in decrypting intercepted messages. However, the worm could be modified to use a variable key. The cipher is subject to a trivial known-plaintext attack whereby a portion of the keystream used to encrypt a message can be recovered easily. If another message is encrypted with the same key, the corresponding part of that message can be decrypted with no trouble.

This document describes a somewhat more advanced known-plaintext attack which finds information about the cipher key. It may be useful if only part of the plaintext of a message is known, since it allows the known portion of the keystream to be extended. It may also be useful if the key is changed in some predictable fashion for each message. The attack can usually succeed in a few seconds with about 50 bytes of known plaintext. It may work with smaller amounts of plaintext, but the running time increases dramatically, and spurious keys become a problem.

The formulas in this document make use of the HTML ^{superscript}
and _{subscript} tags. If your web browser does not render the
words "superscript" and "subscript" slightly above and below the other
text in the previous sentence, you will have a hard time reading the
formulas.

The cipher makes use of a modified linear congruential pseudorandom number generator. The update function of the generator is given below.

update(x) = (((x* 0x39906773) % 2^{32}) % 0xffff) >> 1

Where * represents multiplication, % represents the modulus operator, >> represents binary right-shift, and 0x indicates hexadecimal notation, as in the C programming language. Note that the input to this function can be any 32-bit number, while the output is always a 15-bit number. All values from 0 to 0x7fff are possible outputs, but 0x7fff is about half as likely as the others, given uniform random inputs.

There are four 32-bit key values, denoted key_{0} to
key_{3}. These keys are used to determine the initial state
of the cipher, *x*_{0}.

x_{0}= (((key_{0}+ key_{1}) * key_{2}) % 2^{32}) ^ key_{3}

Where ^ denotes the bitwise exclusive-or operation. Next, the keys
are used in turn to produce successive values of the internal state
*x*_{i}.

y_{i+1}= update(x_{i}) +i

x_{i+1}= update(y_{i+1}+ key_{i % 4})

Here *y*_{i} is a sequence of temporary values
that will be used later in the analysis. Although *x*_{0}
is a 32-bit quantity, the other values of *x*_{i}
are only 15 bits. The cipher state is then used to produce a sequence
of bytes, which forms the keystream.

b_{i}=x_{i}% 2^{8}

For *i* > 0. These bytes are added to the plaintext,
mod 2^{8}, to produce the ciphertext.

c_{i}= (p_{i}+b_{i}) % 2^{8}

Obviously, there is no difficulty in calculating *b*_{i}
given *c*_{i} and *p*_{i}.

This section introduces a modified version of the cipher which produces the same output, though its inner workings are somewhat different. The modified cipher has the advantage that certain sets of keys which produce "nearly" the same effect on the keystream will be numerically close to each other. Observe that

x_{i+1}= ((((y_{i+1}+ key_{i % 4}) * 0x39906773) % 2^{32}) % 0xffff) >> 1

= (((((y_{i+1}* 0x39906773) % 2^{32}) + ((key_{i % 4}* 0x39906773) % 2^{32})) % 2^{32}) % 0xffff) >> 1

= (((z_{i+1}+w_{i % 4}) % 2^{32}) % 0xffff) >> 1

Where *z*_{i} and *w*_{i}
have their natural definitions.

z_{i}= (y_{i}* 0x39906773) % 2^{32},w_{i}= (key_{i}* 0x39906773) % 2^{32}

Because *z*_{i} and *w*_{i}
are both less than 2^{32}, their sum must be less than
2*2^{32}. Thus, the final mod 2^{32} step in the expression for
*x*_{i+1} removes at most one multiple of 2^{32}.
The number of such multiples is

d_{i+1}= 0 ifz_{i+1}+w_{i % 4}< 2^{32}

d_{i+1}= 1 otherwise

Now *x*_{i+1} can be rewritten using
*d*_{i+1} as follows.

x_{i+1}= ((z_{i+1}+w_{i % 4}- 2^{32}d_{i+1}) % 0xffff) >> 1

= ((z_{i+1}+ (w_{i % 4}% 0xffff) -d_{i+1}) % 0xffff) >> 1

Since 2^{32} = 1 mod 0xffff. Notice that, for fixed
*z*_{i+1}, the value of *x*_{i+1}
is "mostly" determined by the key-dependent value
*w*_{i % 4} % 0xffff,
which is no more than 16 bits in size.
The full 32-bit value of *w*_{i} contributes only one
more bit, through *d*_{i+1}. For this reason, the modified
cipher replaces each key_{i} value with a primary 16-bit
quantity, *k*_{i}, and a 32-bit quantity,
*u*_{i}, which is of secondary importance. The
expression for *d*_{i} can be restated in terms of
*u*_{i}.

k_{i}=w_{i}% 0xffff,u_{i}= 2^{32}-w_{i}- 1

d_{i+1}= 0 ifz_{i+1}<=u_{i % 4}

The seemingly extraneous "1" in the definition of
*u*_{i} ensures that the resulting value will fit in a
32-bit word, which is useful in a software implementation on a 32-bit
microprocessor.

The modified cipher is presented in a simplified form below. For clarity, some of the intermediate definitions have been removed.

k_{i}= ((key_{i}* 0x39906773) % 2^{32}) % 0xffff

u_{i}= 2^{32}- ((key_{i}* 0x39906773) % 2^{32}) - 1

z_{i+1}= ((update(x_{i}) +i) * 0x39906773) % 2^{32}

x_{i+1}= ((z_{i+1}+k_{i % 4}) % 0xffff) >> 1 ifz_{i+1}<=u_{i % 4}

x_{i+1}= ((z_{i+1}+k_{i % 4}- 1) % 0xffff) >> 1 otherwise

Before describing the attack, some words about its limitations
are in order. As mentioned earlier, the values of
*u*_{i} have a very small effect on the resulting
keystream. Therefore, it is not possible to determine them completely
using a small amount of known plaintext. In practice, it takes several
hundred kilobytes of data to do so. Instead of finding
*u*_{i}, bracketing values min_{i}
and max_{i} are found such that

min_{i}<=u_{i}<= max_{i}

Since the *u*_{i} values are not completely known,
the precise values of key_{i} cannot be determined. In turn,
the initial state *x*_{0} cannot be calculated by the ordinary
method. That presents no difficulty, as the value of *x*_{1}
can be found, and that is enough information to reproduce the keystream.

The attack assumes that a number of *b*_{i}s are
known. The *k*_{i}s are initially considered
independently of each other. Each of the roughly 2^{16} possible
key values is checked for feasibility using the algorithm below. In order
to be considered further, a key must be feasible with some seed at every
position in the message at which that key is reused. The lower 8 bits
of the seed at any position *i* are known to be
*b*_{i}. The upper 7 bits of the seed are filled
in by an exhaustive search.

is_feasible(i, key, seed, min, max)state <- ((update(seed) +i) * 0x39906773) % 2^{32}

next1 <- ((state + key) % 0xffff) >> 1

next2 <- ((state + key - 1) % 0xffff) >> 1

if next1 = next2 and next1 % 2^{8}=b_{i+1}key is feasibleelse if next1 % 2

next_seed <- next1^{8}=b_{i+1}and state <= max/* it is possible that state <=else if next2 % 2u_{i % 4}*/

key is feasible

min can be increased to state

next_seed <- next1^{8}=b_{i+1}and state > min/* it is possible that state >elseu_{i % 4}*/

key is feasible

max can be lowered to state - 1

next_seed <- next2key is not feasible

Note that next1 = next2 with a probability of approximately 1/2.
Thus, running this procedure with 128 different seed values can be
expected to produce about 128*(1/2*1 + 1/2*2) = 192 different
values of next1 and next2. Heuristically, about 1 in 256 of these can be
expected to produce the correct value of *b*_{i+1}.
Thus, about 192/256 = 3/4 of the possible keys will be accepted as feasible
at each position that is checked. Experiment shows that the process is
somewhat better at rejecting incorrect keys than this simplistic analysis
would suggest, due in part to the fact that different values of next1 and
next2 are sometimes equal mod 2^{8}, and also because the min
and max values were ignored. With 50 bytes of plaintext, usually only
a few hundred candidate keys survive the elimination.

Once candidates for each *k*_{i} have been found,
the next step is to make sure that they are feasible when used together.
This is done by using the next_seed value calculated with one key as the
seed value for the next key. If that proves to be infeasible for every
possible initial seed, then that pair of keys can be rejected. In most
cases, this process suffices to eliminate all but a few hundred viable
key pairs when 50 output bytes are known. The pairs can then be joined
together into larger groups.

The final step is to check that each set of candidate keys produces
the correct stream of output bytes. This step tries all 2^{7}
possible values for *x*_{1} and determines which one is
correct. With 50 known bytes, there are often several keys that reproduce
the same output. This problem becomes increasingly severe as the number
of known bytes is reduced.

This attack is implemented in the file
`crypt.c`.

It may now be possible to extend the known sequence of bytes.
At each step, if
*z*_{i+1} <= min_{i % 4} or
*z*_{i+1} > max_{i % 4}
then one more output byte *b*_{i+1} is determined
unambiguously. If there is some doubt about the next byte, it may
be possible to resolve it by examining a captured message which is known
to have a certain format.

An attack has been demonstrated which quickly determines information about the cipher key using a small amount of known plaintext. This shows that the cipher is weak and should not be used to encrypt important confidential information.