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) % 232) % 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 key0 to key3. These keys are used to determine the initial state of the cipher, x0.
x0 = (((key0 + key1) * key2) % 232) ^ key3
Where ^ denotes the bitwise exclusive-or operation. Next, the keys are used in turn to produce successive values of the internal state xi.
yi+1 = update(xi) + i
xi+1 = update(yi+1 + keyi % 4)
Here yi is a sequence of temporary values that will be used later in the analysis. Although x0 is a 32-bit quantity, the other values of xi are only 15 bits. The cipher state is then used to produce a sequence of bytes, which forms the keystream.
bi = xi % 28
For i > 0. These bytes are added to the plaintext, mod 28, to produce the ciphertext.
ci = (pi + bi) % 28
Obviously, there is no difficulty in calculating bi given ci and pi.
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
xi+1 = ((((yi+1 + keyi % 4) * 0x39906773) % 232) % 0xffff) >> 1
= (((((yi+1 * 0x39906773) % 232) + ((keyi % 4 * 0x39906773) % 232)) % 232) % 0xffff) >> 1
= (((zi+1 + wi % 4) % 232) % 0xffff) >> 1
Where zi and wi have their natural definitions.
zi = (yi * 0x39906773) % 232, wi = (keyi * 0x39906773) % 232
Because zi and wi are both less than 232, their sum must be less than 2*232. Thus, the final mod 232 step in the expression for xi+1 removes at most one multiple of 232. The number of such multiples is
di+1 = 0 if zi+1 + wi % 4 < 232
di+1 = 1 otherwise
Now xi+1 can be rewritten using di+1 as follows.
xi+1 = ((zi+1 + wi % 4 - 232 di+1) % 0xffff) >> 1
= ((zi+1 + (wi % 4 % 0xffff) - di+1) % 0xffff) >> 1
Since 232 = 1 mod 0xffff. Notice that, for fixed zi+1, the value of xi+1 is "mostly" determined by the key-dependent value wi % 4 % 0xffff, which is no more than 16 bits in size. The full 32-bit value of wi contributes only one more bit, through di+1. For this reason, the modified cipher replaces each keyi value with a primary 16-bit quantity, ki, and a 32-bit quantity, ui, which is of secondary importance. The expression for di can be restated in terms of ui.
ki = wi % 0xffff, ui = 232 - wi - 1
di+1 = 0 if zi+1 <= ui % 4
The seemingly extraneous "1" in the definition of ui 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.
ki = ((keyi * 0x39906773) % 232) % 0xffff
ui = 232 - ((keyi * 0x39906773) % 232) - 1
zi+1 = ((update(xi) + i) * 0x39906773) % 232
xi+1 = ((zi+1 + ki % 4) % 0xffff) >> 1 if zi+1 <= ui % 4
xi+1 = ((zi+1 + ki % 4 - 1) % 0xffff) >> 1 otherwise
Before describing the attack, some words about its limitations are in order. As mentioned earlier, the values of ui 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 ui, bracketing values mini and maxi are found such that
mini <= ui <= maxi
Since the ui values are not completely known, the precise values of keyi cannot be determined. In turn, the initial state x0 cannot be calculated by the ordinary method. That presents no difficulty, as the value of x1 can be found, and that is enough information to reproduce the keystream.
The attack assumes that a number of bis are known. The kis are initially considered independently of each other. Each of the roughly 216 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 bi. 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) % 232
next1 <- ((state + key) % 0xffff) >> 1
next2 <- ((state + key - 1) % 0xffff) >> 1
if next1 = next2 and next1 % 28 = bi+1key is feasibleelse if next1 % 28 = bi+1 and state <= max
next_seed <- next1/* it is possible that state <= ui % 4 */else if next2 % 28 = bi+1 and state > min
key is feasible
min can be increased to state
next_seed <- next1/* it is possible that state > ui % 4 */else
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 bi+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 28, 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 ki 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 27 possible values for x1 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 zi+1 <= mini % 4 or zi+1 > maxi % 4 then one more output byte bi+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.