. 5
( 16)


Can we modify ORYX so that it is more secure? If, at each itcration, we
output a single bit instcad of a byte, that would probably improve the security
3.4 RC4 103

significantly. For example, suppose we were to compute each keystream bit
keystreamBit = s ( X )@ s ( L [ H ( A ) ] ) s ( L [ H ( B ) ] ) ,

where s selects, say, the high (rightmost) bit of a word or byte. Provided
that a complete iteration occurs between each keystreamBit computation,
this modification would frustrate the attack discussed above-even if much
more known plaintext were available-since the number of candidates to be
considered would grow rapidly, instead of being reduced at each iteration.
However, this modification would make the cipher eight times slower, which
is almost certainly not practical for its intended application. Also, other
attacks on this “secure” version of ORYX would need to be considered.


Suddenly she came upon a little three-legged table, all made o f solid glass:
there was nothing on it but a tiny golden key.. .
- Alice in Wonderland

RC4 was invented by Ron Rivest in 1987. The “RC” is reputedly for “Ron™s
Code,” although officially it is “Rivest Cipher.” RC4 is without doubt the
most widely used stream cipher in the world today. It is used, for example,
in the Secure Socket Layer (SSL), which is the de facto standard for secure
transactions over the Internet, and in Wired Equivalent Privacy (WEP), a
widely deployed networking protocol that purports to semi-secure a wireless
local area network (LAN).
The RC4 algorithm is considered secure, if used properly. However,
WEP--the Swiss cheese of security protocols--somehow managed to imple-
ment nearly all of its security functions insecurely, including RC4. As a result,
there is a feasible attack on RC4 encryption as used in WEP. But before we
discuss this cryptanalytic attack, we briefly mention a few of the many other
security issues with WEP.
Perhaps the most egregious security problem with WEP is that it uses
a cyclic redundancy check (CRC) for “integrity” protection. The primary
purpose of integrity protection is to detect malicious tampering with the
data-not just to detect transmission errors. While a CRC is an excellent
error detection method, it is useless for cryptographic integrity, since an in-
telligent adversary can alter the data and, simultaneously, the CRC value so
that the “integrity check” is passed. This is precisely the attack that a true
cryptographic integrity check, such as a MAC or HMAC, will prevent [142].
Furthermore, since RC4 is a stream cipher, WEP encryption is linear, which
allows changes to be made directly to the ciphertext--by an attacker who

does not know the key or plaintext-and to the CRC value so that the re-
ceiver will not detect the tampering. The bottom line is that this supposed
“integrity check” provides no cryptographic integrity whatsoever. Perhaps a
CRC was used in WEP due to resource limitations, but that is no excuse for
promoting the CRC calculation as an integrity check.
WEP encrypts data with the stream cipher RC4 using a long-term key
that seldom (if ever) changes. To avoid repeated keystreams, an initialization
vector, or IV, is sent in the clear with each message, where each packet is
treated as a new message. The IV is mixed with the long-term key to produce
the message key. The upshot is that the attacker, Trudy, gets to see the IVs,
and any time an IV repeats, Trudy knows that the same keystream is being
used to encrypt the data. Since the IV is only 24 bits, repeated IVs will occur
relatively often, which implies repeated keystreams. Since a stream cipher is
used; a repeated keystream is at least as bad as reuse of a one-time pad. That
is, a repeated keystream provides statistical information to the attacker who
could then conceivably liberate the keystream from the ciphertexts.
However, in WEP, there are several possible shortcuts that make an at-
tacker™s life easier. For example, if the attacker Trudy can send a message over
the wireless link and intercept the ciphertext, then she knows the plaintext
and the corresponding ciphertext, which enables her to immediately recover
the keystream. This same keystream will be used to encrypt any message
that bears the same IV, provided the long-term key has not changed-which
it seldom does, since a key change is manual, and the key must be shared
with all users of a particular wireless access point.
How realistic is it for Trudy to send a known message over the wireless
link? As long as she can contact someone on the wireless LAN (for exam-
ple, by sending an email message), she can potentially accomplish this trick.
The primary practical difficulty for Trudy is to determine which intercepted
message corresponds to her chosen plaintext.
There are many more WEP security vulnerabilities. For example, sup-
pose that Trudy knows (or can guess) the destination IP address of a given
WEP-encrypted packet. Then-without knowing the key-she can change
the destination IP address to an IP address of her choosing (for example,
her own IP address), and change the CRC “integrity check” so that her tani-
pering goes undetected. WEP traffic is only encrypted from the host to the
wireless access point (and vice-versa). Therefore, when the altered packet
arrives at the access point, it will be decrypted and forwarded to Trudy™s
preferred IP address. Note that this attack is made possible by the lack of
any real integrity check.
Below, we discuss a cryptanalytic attack on the RC4 stream cipher as it is
used in WEP. This attack succeeds due to the specific way that W E P creates
the session key from an initialization vector IV and the long-term key, not
3.4 RC4 105

due to any inherent weakness in the RC4 algorithm i t ˜ e l f . ˜ attack has a
small work factor, and it will succeed provided that a sufficient number of IVs
are observed. This clever attack, which can be considered a type of related
key attack, is due to Fluhrer, Mantin, and Shamir [51].

3.4.1 RC4 Algorithm
RC4 is simplicity itself. At any given time, the state of the cipher consists of
a lookup table S containing a permutation of all byte values, 0 , 1 , 2 , .. . ,255,
along with two indices i and j . When the cipher is initialized, the permutation
is scrambled using a key which can be of any length from 0 to 256 bytes. In
the initialization routine, the lookup table S is modified (based on the key)
in such a way that S always contains a permutation of the the byte values.
The RC4 initialization algorithm appears in Table 3.9.
Table 3.9: RC4 Initialization

f o r i = 0 t o 255
Si = i
Ki = key[i (mod N ) ]
next i
f o r i = 0 t o 255
j = ( j Si Ki) (mod 256)
swap(S2, S j )
next i

The RC4 keystream is generated one byte at a time. An index is deter-
mined based on the current contents of and the indexed byte is selected
as the keystream byte. Similar to the initialization routine, at each step
the permutation S is modified so that S always contains a permutation of
{0,1,2,. . . ,255). The keystream generation algorithm appears in Table 3.10.

3.4.2 RC4 Attack
In 2000, Fluhrer, Mantin, and Shamir [51]published a practical attack on RC4
encryption as it is used in the Wired Equivalent Privacy (WEP) protocol. In
WEP, a non-secret 24-bit initialization vector, denoted as IV, is prepended
to a long-term key and the result is used as the RC4 key. Note that the
role of the IV in WEP encryption is analogous to the role that the message
indicator (MI) plays in the World War I1 cipher machines discussed in the
˜The attack does highlight a shortcoming in the RC4 initialization process-a shortcom-
ing that can be fixed without modifying the underlying RC4 algorithm.

RC3 Keystreani
Table 3.10: RC4 Keystream Generator

previous chapter. As with the 511 in the WWII cipher machines. the W E P IV
is necessary t o prevent messages from being sent in depth. Recall that two
ciphertext messages are in depth if they were encrypted using the same key.
Alessages in depth are a serious threat t o a stream cipher.
In WEP. Trudy, the crypt analyst, knows many ciphertext messages (pack-
ets) and their corresponding IVs, and she would like t o recoaw the long-term
key. The Fluher-Mantin-Shamir attack provides a clever. efficient, and el-
egant way to do just that. This attack has been successfully used t o break
real WEP traffic [145].
Suppose that for a particular message, the three-byte initialization vector
is of the form
where V can be any byte \-due. Then thcse three IV bytes become K O ,Kl
and Kz in the RC-2 initialization algorithm of Table 3.9, while K3 is the first
byte of the unknown long-term key. T h a t is. the message key is

here V is known to Trudy. but K 3 , K4, K j . are unknown. To understand

the attack. we need t o carefull\ consider what happens to the table S during
the RC4 initialization phase when K is of the foiin in (3.9).
In the RC4 initialization algorithm in Table 3.9 we fir5t set S t o the
identity permutation, so that we have

Suppose that K is of the form in (3.9). Then at the i = 0 initialization step.
we compute the index j = 0 + SO+ K O= 3 and elements i and j are swapped.
resulting in the table

+ ++
At the next step, i = 1 and j = 3 S1 t K1 = 3 1 255 = 3, since the
addition is modulo 256. Elements i and j are again swapped, giving
3.4 RC4 107

i 5
1 2
s, . .. .
0 14 5

... 5 + v
5 ...
i 34
s, ...
0 5+v ... .

2 ...
3 5
2 0 1
5 ...
5+V 4
3 0
... 5 + V . .. 6 + V + K : 3 ...
i ...
... ...
2 1

++ +
assuming that, after reduction modulo 256, we have 6 V K3 > 5 V . If
++ +
this is not the case, then 6 V K3 will appear to the left of 5 V ,but this
has no effect on the success of the attack.
Now suppose for a moment that the RC4 initialization algorithm were to
stop after the i = 3 step. Then if we generate the first byte of the keystream
according to the algorithm in Table 3.10, we find i = 1 and j = Si = S = 0,
+ +
so that t = S SO= 0 3 = 3. Then the first keystream byte would be
+ K3) (mod 256).
S3 = (6 + V (3.10)
keystreamByte =

Assuming that Trudy knows (or can guess) the first byte of the plaintext, she
can determine the first byte of the keystream. If this is the case, Trudy can
simply solve (3.10) to obtain the first unknown key byte, since

(keystreamByte - 6 - V )(mod 256). (3.11)
K3 =

Unfortunately (for Trudy), the initialization phase is 256 steps instead of
just four steps. But notice that as long as SO, 1 and S3 are not altered in any
subsequent initialization step, then (3.11) will hold. What is the chance that
these three elements remain unchanged? The only way that an element can
change is if it is swapped for another element. From i = 4 to i = 255 of the
initialization, the i index will not affect any of these elements since it steps
regularly from 4 to 255. If we treat the j index as random, then at each step,
the probability that the three indices of concern are all unaffected is 253/256.
The probability that this holds for all of the final 252 initialization steps is,
E) = 0.0513.

Consequently, we expect (3.11) to hold slightly more than 5% of the time.
Then with a sufficient number of IVs of the form (3.8) Trudy can determine K3
from (3.11), assuming she knows the first keystrearn byte in each case.
What is a sufficient number of IVs to recover K3? If we observe n en-
crypted packets, each with an IV of the form (3.8), then we expect to solve
for the actual K3 using (3.11) for about 0 . 0 5 ˜ ˜ these. For the remain-
ing 0.95n of the cases, we expect the result of (3.11) to be a random value
in { 0 , 1 , 2 . . . . ,255}. Then the expected number of times that any particular
value other than K3 appears is about 0.95n/256 and the correct value will
have an expected count of 0.05n 0.95n/256 E 0.05n. We need to choose n
large enough so that we can. with high probability, distinguish K3 from the
random “noise”. If we choose n = 60, then we expect to see K3 three times,
while it is unlikely that we will see any random value more than twice (see
also Problem 7).
This attack is easily extended to recover the remaining unknown key bytes.
Wc illustrate the next step, that is, assuming that Trudy has recovered K3,
we show that she can recover the key byte K4. In this case, Trudy will look
for initialization vectors of the form

IV = (4,255,V ) , (3.12)

nhere V can be any value Then at the 1 = 0 step of t h e initialization.
,I = 0 + So + I<" = 3 and elcnients 7 and j are snapped, resulting in

0 4 ...
i 12
s, ....
4 5

i = 1 and j = 4 + S1 + A', = 4 (since tlie addition is
At the next step.
mod 256) and elements S and 5™˜ swapped. giving
1 are

3 45
0 1 2

z ... .
2 15
4 3
- V and after thc swap
At step i = 2 we liavc j = 3 S2 =G

6+V ...
i 0 1 3 45
6+V ...
0 3
4 2
+ V + K;<* K:c is
+ 1' + S:j
A t tlic ricxt step, i = 3 and j = t5 and
1<:3 = 9
knowri. Aft or swapping

3 4
0 1
9+V+K3 5
S4 0 6+V
... 6 + V ... ...
a ... ... ...
2 3
3.4 RC4 109

++ +
assuming that 9 V K3 > 6 V when the sums are taken mod 256.
Carrying this one step further, we have i = 4 and

5 .
io 1 4
Sa 4 6+V 9+V+K3 10+V+K3+K4
0 ...

... 6 + V ... 9+V+K3 ... lO+V+K3+Kq
i ...
s ... ...
a ...
3 ... .
2 1

If the initialization were to stop at this point (after tho i = 4 step) then
for first byte of the keystrcam we would find i = 1 and j = S,= 5 = 0, so

+ +
that t = 5™1 5™0 = 4 0 = 4 . The rcsulting keystreani byte would be

+ V + K 3 + K.1) (mod 256),
kcystrcamI3yte = Sq = (10

where the only iiiikiiowri is I<l. rc.siilt

10 - I - - K : ] )(rriod 256). (3.13)
= (keystreaninytc -

Of course. thc initialization does not stop after the i = 4 step, but, a s
in th: K:$ (xw. the chanco that (3.13) holds is h o i i t 0.05. Chsoquently.
with a sufficient riiimbcr of I s of the forni (3.12), ˜I™rudy can detcrmiric K;1.
Coiitiiiiiirig in this way, any nwribcr of key hytes call hc recovered, provided
enough IVs of the correct form (about 60 for cacti key byto) arc availablr and
˜I™rudy knows tho first keystreani hytc of oach corresponding packet.
This same tcchnique can h!extended to rccovcr additional key bytes,
K s , Ktj,. . .. In fact, if a sufficient riiiinber of packets arc availablc, ti key of
any lcrigth can t)c rccovered with a trivial amoiirit of work. This is one reason
why WEP is said to be “uiisaf<™at any koy size“ [154].
Coiisider oiicc again the attilck to rewvor thr: first uiikrion.n key byte Ks.
It is worth notirig that soine IVs that arc riot of the form (3, 255, V ) will
be uscful bo Trudy. For examplc. supposc the I V is (2,253,O). ˜Then after
the i : initialization step. the array S is
... 3+K3
2 01 2 ...
z .
02 3
1 3+K3 ...

If and $3 arc not altcrcd in t.ho remaiiiiiig iiiitialization steps, thc first
S1, 5™2,
keystrcmii t)ytv will be 3 + K:<,frorn which T r u d y can rcc˜over I<:<. Notice that
for a givexi three-byte IV, T r u d y caxi coniputc™ t hc initialization up through
the i = 3 step ilnd, by doing so. she can easily tictc˜rminr:whether a given IV
will bc useful for her attack. Siriiilar commciits hold for siibscquent key bytes.

By using all of the useful IVs, Trudy can reduce the number of packets she
must observe before recovering the key.
Finally, we mention that it is also possible to attack RC4 if the IV is
appended t o the unknown key instead of being prepended (as in WEP);
see [51, 961 for the details.

3.4.3 Preventing the RC4 Attack
It is easy to prevent the WEP-RC4 attack, and similar attacks that target
the RC4 initialization. The standard suggestion is to add 256 steps to the ini-
tialization process. that is. after the initialization in Table 3.9 has completed.
generate 256 keystream bytes according to the RC4 keystream generation al-
gorithm in Table 3.10, and discard these bytes. Then generate the keystream
in the usual way. As long as both the sender and receiver follow this proce-
dure, no modification to t,he inner workings of RC4 are required. There are
many other ways that thc key and IV could be combined that would effec-
tively prevent the attack described in this section; Problem 11 asks for such
met hods.


I f you fail to abide by the terms of this license,
then your conscience will haunt you for the rest o f your life.
- ARC shareware licensv [66]

In the late 1980s, Phil Katz invented the ZIP file format and made it publicly
available. Due to its clear superiority over the competition, the ZIP format
quickly became a de facto standard-which it remains to this day. When you
create, send, or receive a compressed file, you are almost certainly using Phil
Katz™s ZIP format.
PKZIP is an acronym for “Phil Katz™s ZIP program” [114]: which is a util-
ity created by (no surprise here) Phil Katz to manage ZIP archives. PKZIP,
which first appeared in 1989, was much superior to AR.C, the leading com-
pression tool of the tirric. ARC was developed by System Enhancement As-
socia.tcs, Iric., or SEA, and sold as shxeware. Today we “ZIP” files, whereas
for much of the 1980s people would “ARC” their files.
Prior to creating the ZIP format and his PKZIP utility, Phil Katz had
developed utilities to handle ARC cornpressed files--tools that were, by all
accounts, better then those provided by SEA. This competition did not
please SEA, and they siiccessfiilly sued. Shortly after these legal wranglings,
Katz developed his ZIP format, and PKZIP soon far outpaced SEA™S ARC
3.5 PKZIP 111

utility.6 The company Katz created, PKWare, Inc., still exists. Tragically,
Phil Katz died in 2000, a t age 37, as a result of alcohol abuse [106].
PKZIP is primarily a compression utility, but since ARC provided a n
encryption option, PKZIP needed one as well. ARC encryption was trivial-
simply a repeated XOR with the password-and Katz wanted something
stronger. The obvious cipher choices were DES or triple-DES, but efficiency
was a major issue, as were concerns over export controls, which limited the
strength of encryption that could be used on products destined for non-US
markets. As a result, PKZIP used its own “homebrew” cipher, designed by
Roger Schlafly [78].
Although the PKZIP cipher is weak, it is not trivial t o break. Export
controls in force at the time limited key sizes to 40 bits or less, and the work
factor to break the PKZIP cipher is close t o that limit, unless a large amount
of known plaintext is available, in which case the work factor can be reduced
The PKZIP cipher employs a n interesting and unorthodox design. For
one thing, it may be one of the first ciphers t o use “mixed-mode” arithmetic
as an efficient way t o achieve a degree of nonlinearity. This is a common
strategy today, employed in such well-known and respected ciphers as IDEA
and TEA. However, it is clear that there was little, if any, peer review of the
PKZIP cipher, in violation of Kerckhoffs™ Principle. Not surprisingly, PKZIP
proved t o be weak when exposed t o the light of day.
Biham and Kocher [13]developed a known plaintext attack on the PKZIP
cipher which we discuss in this section. However, the paper [13]is itself diffi-
cult to decipher-Conrad™s implementation [30] is the key to understanding
the Biham-Kocher attack. Attacks that require slightly less known plaintext
are known [143].

PKZIP Cipher
We ignore the PKZIP compression process and instead focus on the encryp-
tion. Here, we are concerned with the so-called “internal representation” of
the key, a 96-bit quantity derived from a user-supplied password [13]. We de-
note this key as three 32-bit words, X , Y ,and 2.The attack will recover this
key, which enables us to decrypt the message, as well as any other messages
encrypted under the same password.
The PKZIP stream cipher generates one byte of keyst,ream a t each step.
Being a stream cipher, the keystream is XORed with the plaintext t o produce
the ciphertext. The same keystream is XORed with the ciphertext t o recover
the plaintext.
˜The success of ZIP and the rapid demise of ARC was not only due to the technical
superiority of the ZIP format. Another factor was the widespread belief amongst nerds
that Phil Katz had been persecuted by SEA.

Below, we follow the convention that upper case letters represent 32-
bit words, while lower case represent 8-bit bytes- for the one require 16-bit
quantity, we also use lower case. All arithmetic is to be taken modulo 232. As
in other sections of this book, we adopt the convention that bits are numbered
from left-to-right, beginning with 0. In the PKZIP attack discussed below,
we often need t o specify a range of bits within a byte or a 32-bit word. We
where j 2 i , for the string of bits of length j - i 1
use the notation (A)i,..j,
beginning with bit i and ending with bit j of A.
The PKZIP encryption algorithm appears in Table 3.11. Here, p is the
current plaintext byte, c the resulting ciphertext byte, and k is the keystream

Table 3.11: PKZIP Encryption

// encrypt plaintext byte p
// result is ciphertext byte c
// given current X ,Y , Z
k = getKeystreamByte(2)
update(X, y,2, ) P

The functions getKeystreamByte and update are defined in Tables 3.12
and 3.13, respectively. T h e decryption process is easily derived from these
encryption routines.

Table 3.12: PKZIP getKeystreamByte

getKeystrciamByte( 2)
(2 3)16...31 // 16-bit quantity
t V
k = ( ( t .( t @ 1)) > 8 ) 2 4 ...31
end getKeystreamByte

The CRC function in Tahle 3.13 is a cyclic redundancy check, which can
be computed as shown in Table 3.14. This is the same CRC calculation used
for error detection in t h e ZIP compression process and, undoubtedly, it is
reused here for efficiency.
A more efficient way t o carry out the CRC calculation in Table 3.14 is dis-
cussed in Problem 18, where it is shown that there exists a table, CRCtable[b],
where for any byte b, we have
3.5 PKZIP 113

Table 3.13: PKZIP update

// update values of X ,Y , 2
update(X, y,2,P )
X = CRC(X,p)
+ +1
Y = (Y (X)24...31) 134,775,813
Z = CRC(Z,(Y)o 7 )
end uDdate

Table 3.14: PKZIP CRC Calculation

// X is a 32-bit integer
//b is a byte
for i =0 to 7
i f X is odd then
X = ( X >> 1) CE Oxedb88320
else // X is even
end i f
next i
return X
end CRC

Problem 19 shows that there is a table, CRCinverse, that is the inverse
of CRCtable in the sense that if

˜ 3 CE b],
B = (A)0 23 CE CRCtable[(A) (3.14)
... 2 1

A = ( B < 8) CE CRCinverse[(B)o...7]@ 6.
< (3.15)
Let (Xi,y Z , Zi) denote the 32-bit words (X, Y, ) used to generate the ith
keystream byte and let ki be the ith keystream byte, for i = 0 , 1 , 2 , . . .. We
are now in a position to discuss the Biham-Kocher attack.

PKZIP Attack
We first summarize the PKZIP attack, then we provide details for each of the
points in the summary. We call ko, k l , k2, . . . , k , a k-list. Define plist, X -
list, Y-list, and Z-list similarly. The attack assumes known plaintext, which
implies that the k-list and plist are both known.

If we can recover any valid triple ( X i , X , & ) , then the internal state of
the keystream generator is known and we can determine the keystream k j for
all j 2 i . This attack will enable us t o find such a triple (Xi,y ,2i) with a
nontrivial, but, feasible, amount of work.
In outline form, the attack c0nsist.s of t,he following steps:
1. Use the k-list to find a set of putative 2-lists.

2. For each putative 2-list, we find rnultiple putative Y-lists.
3. For each putative Y-list, we use the p-list t o obtain a single putative

4. The true X-list must be among the putative X-lists. By using the p-list,
we can determine the correct X-list, and once we find the correct X-list,
we know thc corresponding Y-list and 2-list, so we can determine the
A total of n + 1 known plaintext bytes are r e q ˜ i r e d . ˜ number the known
plaintext bytes from 0 t o n. These plaintext bytes must be consecutive,
but need not be the first n 1 bytes. Then each list (k-list, X-list, etc.)
contains n 1 elements, which are numbered from 0 t o n,even though these
might not represent the first n 1 el˜rnents generated. Eventually, we will
show that 13 consecutive known plaintexts is sufficient (that is, rb = l a ) , but
for now we leave n unspecified.
Next,, we expand on each of the points in thc attack outlined above. For
this attack, we assurne that we have available the p l i s t , that is, we have p,,
for z = 0 , 1 , 2 . . . . ,n, which implies that we also know the corresponding k-list.
We number the steps in the attack below t o correspond with the numbers in
the outline of the attack, above.

1. Problem 20 shows that given a key byte k, there are 64 choices for the
value t in Table 3.12, which, in turn, gives 64 possible values for the 14
bits ( 2 ) 1 ˜ , , , 2 9 . Consequently, given any k i , we have 64 putative values
for (ZZ)lS...29.
We use k , t o determine 64 putative values for ( Z n ) 1 6 . . . 2 g and we use k,-l
t o determine 64 putative values for (Zn-l)l6,,.2g. Next, we loop over
the 216 possible choices for (Zn)o...15 For each of these, we have 64 puta-
tive ( Z 7 2 ) 1 6 . . . 2 ywhich implies that we have 222candidates for (Zn)o
, ...29.

From update in Table 3.13, we have

2.i = CRC(Zi-i,(X)o...7 )
71n PKZIP, the plaintext bytes are actually cornprctssfd text. This has no effect on the
attack discussed here, except that we are implicitly assuming that the compressed bytes
are known
3.5 PKZIP 115

and from the inversion formula in (3.15) it follows that
< (K)o...7.
ZZ.-I= (ZZ. 8) @ CRCinverse[(Zi)o @ (3.16)

Let i = n in (3.16). Then given a candidate (2,)0...29, we know bits 0
through 21 on the right-hand side of (3.16). On the left-hand side, there
are 64 possible values for ( Z n - l ) 1 6 . . . 2 9 . For the correct 2,-1 and Z,,
bits 16 through 21 on both sides of (3.16) must match. For any given Z,,
there is a probability of about 1/64 that a given Zn-l matches in these
six known bit positions. Since we have 64 putative ( Z n - 1 ) 1 6 ...29, we
expect, on average, one of these 64 to match in the corresponding bits
of the given 2,.
Once we find a ( Z ,-1)16...29 that is consistent with a putative Z,, we
can then fill in bits 0 through 15 of 2,-1 based on the right-hand side
of (3.16). At this point, we have found a (putative) pair consisting
of ( Z n - l ) 0 . . . 2 g and ( Z n ) 0 . . . 2 g , and we expect to find the same number of
such pairs as we have putative ( Z n ) o . . . 2 9 . We can repeat this process
for n - 1,n - 2, n - 3, . . ., and thereby obtain complete putative 2-lists
of the form (Z˜.)0...29, i = 0 , 1 , . . . ,n.
We can extend each putative 2,from 30 known bits to its full 32 bits
as follows. From (3.16), we have
(ZZ 8) = ZZ.-1 CRCinverse[(Z,)o...71 @ (3.17)
In this form, bits 22 and 23 are known on the right-hand side. But
these correspond to bits 30 and 31 of 2i on the left-hand side, which
allows us to fill in these (previously) unknown bits on the left-hand
side. In this way, for each putative 2-list, we can determine bits 30
and 31 of Zi, for i = 1 , 2 , . . . , n, and we can thereby complete each ZZ.,
except for 2 0 . Note that we cannot determine bits 30 and 31 of 20
using (3.17), since Z Z . -is required on the right-hand side. Also note
that the expected number of putative 2-lists is equal to the number of
putative Z,, that is, about 222.
The number of putative 2-lists can be reduced as follows. For all pu-
tative ZZ., can determine the corresponding
we values, then sort
the resulting lists based on Zz-1, removing any duplicates. The sav-
ings provided by this refinement are explored further in Problem 29.
In [13] it is suggested to carry out this reduction for 28 steps, which,
it is claimed, reduces the expected number of 2-lists from 222 to 218.
While this reduces the work by a factor of 24, the price that is paid is
that 28 additional known plaintext bytes must be available.
For simplicity, in the remainder of our discussion of this attack, we ig-
nore this duplicate-reduction step. Consequently, we expect to have 222
putative 2-lists.

2 . At this point we have about 222 putative 2-lists, each of which is of the
form Z1,Z2,. . . ,Z,.Now we rewrite (3.16) as

(K)o...7 = (zi < 8) @ Zi-i
< (3.18)
@ CRCinverse[(Z,)o ...7],

which, for each 2-list, immediately gives us (Y)o...7of the corresponding
Y-list, that, is, we obtain bits 0 through 7 of each of Y2, Y3,. . . , Y,. Note
that Y cannot be recovered using (3.18) since Zi-1 is required t o find K,
and 20was not recovered.
From update in Table 3.13, we have

Y , = (x-1+ (Xi)24...:31). 134,775,813 1, (3.19)

which we rewrite as

(x + ( x z ) 2 4 ...31,
1) C (3.20)
= x-1
- '

whcre C = 134775813-1 = 3645876429 (mod 232). From this equation
and Problem 23, it, follows that with high probability we have

((K - 1) . cO 7
) ... (K-1)O ...7. (3.21)

Letting i = n in (3.21) we have

1) ' C)O... 7
((yn = (yn-1)O ...7.

Since (Yn)o...7 and (Yn-1)o...7 are known, we can test all 224 choices
for (Yn)8...31against the known right-hand side. The probability of a
match is 1/28, so we expect t o find 216 putative Y,. Note that we obtain
this number of Y per putative 2-list, since the (y2)0...7 are derived based
on a particular 2-list. Since there are about 222 2-lists, a t this point
we have about 238 partial Y-lists, each consisting of just Y,.
Now from (3.20), we have

(Y7, 1 ) .c a
Y,-l (3.22)
= - -

for some unknown a E { 0 , 1 , 2 , . . . ,255). Given a putative YTL, sub-
stitute each choice for a into (3.22) and obtain a putative Y,-l. Each
of these is then is tested t o determine whether

cO 7 = ( y n - 2 ) O ...7
) ...
((Yi-1 - 1) '

holds; if so, Yn-l saved, and if not, it is discarded. Since (Yn-2)o...7
is a known 8-bit quantity, on average, we expect one of the 256 corm
puted Y,- 1 t o pass this test. That is, the number of Y-lists docs not
3.5 PKZIP 117

expand at this step, where we extend each putative Y-list from Y ,
to Yn-l. Consequently, we expect to find about 238 partial Y-lists, each
consisting of Y and Y,-l.
Now for each Y,-1, there are 256 possible Y,-z from
Yn-2 = (Yn-l - 1 ) .c - a
and, on average, only one of these will satisfy

1) ' cO 7 = (Yn-3)O ...7.
) ...
((yn-2 -

In this way we extend the putative Y-lists to include Yn-2, without
increasing the number of lists to more than 238. Continuing, we obtain
about 238 putative Y-lists, each consisting of y Z , for i = 3 , 4 , 5 , . . . , n.
Note that we cannot find Y by this method, since (Y1)0...7would be
required, which is not known.
The computation of Y-lists discussed here can be made more efficient
by using lookup tables. Specifically, given the byte (yZ-1)0...7, we would
simply look up the corresponding ( ( y Z - 1) . C)O...˜,
saving the cost of
many multiplications.
3. At this point, we have about 238 putative Y-list, each of the form
Y3, Y4, . . . , Y,. For each of these we determine one corresponding X -
list as follows. We rewrite (3.20) as

(X - 1) . c - x-1, (3.23)
( x z ) 2 4 ...31 =

from which we immediately obtain

. . , (Xn)24...31,
( X 4 ) 2 4...31, ( x 5 ) 2 4 ...31,.

but not (X3)24...31.
Now from update in Table 3.13 together with (3.14), we have
CRCtable[(Xi-1)24 ...31 @pZ].
Xi = (XZ-1)O ...23 @I
A consequence of (3.24) is that if we know one complete Xi, we can
compute all bits of X j , for j > i, assuming that the corresponding
plaintexts p j are known. By using the CRC inversion formula, we can
also use this Xi to recover Xj for j < i, again, provided that the
corresponding plaintexts p j are known.
To determine one complete X i , first note that according to (3.24) we

(xz)O23 = Xi+i @ CRCtable[(Xi)24...31 @ p i + 1 ] (3.25)

(Xi+l)O (3.26)
2 3 = Xi+2 @ CR,Ctable[(Xi+l)24 31 @ pi+2]

(Xi+z)o 23 CRCtable[(Xi+z)z4...31 @ p i + 3 ] .
= Xi+3 @

Since we know (Xi+3)24...31 and (Xi+2)24...31, frorn (3.27) we can de-
termine (Xi+2)16.,.2:3 which gives us (Xi+2)16. . . 3 1. Combining this result
which, together with (3.25), allows us to
with (3.26), we find (Xi+1)8...31,
determine all bits of X .We can now use this recovered X i and (3.24) to
firid putative X-lists, of the form X4, Xg, . . . , X,,, as discussed, above.8
We obtain one putative X-list for each putative Y-list, so that the ex-
pected number of X-lists is 238.

4. Finally, to determine the correct X-list from the collection of putative
X-lists, we compare the values of (Xz)24 31 obtained from (3.24) with
the values obtained from (3.23). We expect each such comparison to
reduce the number of remaining lists by a factor of 256. Since we have
about 238 X-lists, we need to make five such comparisons before we
expect to obtain the correct X-list.
At this point we have a single X-list along with the corresponding
Y-list and 2-list. Given any triple (X,,Y,,Z,) we can compute the
keystream kJ for all 3 2 z and therefore decrypt the ciphertext to recover
the (compressed) plaintext.

The overall work factor for this att,ack is on the order of 238 (the number
of lists generated). The work factor can be reduced by using more known
plaintext, as discussed in [13] and Problem 29.
We still need to precisely determine the minimum number of known plain-
text bytes required, that is, the smallest value of n for which the attack
will succeed. From (3.25), (3.26), and (3.27), we see that four consecu-
t,ive (XL)24...31 needed to completely determine the X-lists. Also, five
additional Xi arc needed to find the correct X-list from the set of 238 lists.
This means nine X-list elements must be available. However, each X-list is
only determined for i = 4,5, . . . , ri, which implies n = 12 is the smallest value
for which we obtain the required nine X-list elements. Since our indexing
begins at 0, we need a minimum of 13 consecutive known plaintext bytes for
the attack described here.
Finally, we describe a slightly different implementation of this PKZIP
attack, which is easier to program. The attack discussed above requires that
we store all putative 2-lists and so on. This is essential if want to do the
duplicate-reduction step, where the number of of 2-lists is reduced from 222
to some smaller number using additional known plaintext (see Problem 29).
But if wc do not employ this reduction step, we can obtain an algorithm
that is easier t,o implement. The idea is essentially to turn the breadth-first
approach described above into a depth-first attack.

'We could u s e (3.24) t o solve for additional X , , but only through X,, are r e q u i r d
for this attack.
3.5 PKZIP 119

Instead of generating all of the putative 2-lists, then all of the Y-lists,
followed by all of the X-lists, we generate a single 2-list, then all of the Y-
lists that are consistent with this 2-list, then the X-lists that are consistent
with the Y-lists. The resulting X-lists are then tested to determine whether
we have found the correct list, and the entire process is repeated for each
putative 2-list until the solution is found. In this way, we only need to store
a relatively small set of lists at any given time--not the entire set of 238 lists.
This simplified attack is outlined in Table 3.15.

Table 3.15: Outline of PKZIP Attack

// given keystream bytes Ico, Icl, . . . , kl2
f o r i = 0,1,. . . , 1 2
Find (Zi)l6...29 consistent with ki // expect 64
next i
f o r each ( 2 1 2 ) 1 6 ...29 // expect 64
f o r each (212)0...15 // 216 choices
f o r i = 11,10,. . . , O
Find (Zi)16...29consistent with (Zi+l)o 29 ...
Extend (Zz)l6 ...29 to ( 2 i ) O ...29
next i
Complete to 2-list: 2, = (Zi)O,,,31, = 1 , 2 , . . . , 1 2
Solve for (K)o i = 2,3,. . . , 12
x, i = 3 , 4 , . . . , 1 2 // expect 2" lists
Solve for Y-lists:
f o r each Y-list // expect 2"
Solve for (Xi)24 1, i = 4 , 5 , . . . , 1 2
Solve for Xg using ( X 9 ) 2 4 ...31, ( x 1 0 ) 2 4 ...31,
(xll) 4 . 3 and (x12) ...31
2 24
Solve for X-list: X i , i = 4 , 5 , . . . , 1 2
i f (Xi)24,..31 o r i = 8 , 7 , 6 , 5 , 4 verified t h e n
r e t u r n X-list, Y-list, 2-list
end i f
n e x t Y-list
next ( 2 1 2 ) O ...15
n e x t (212)16...29

Note that for the attack in Table 3.15, the maximum number of ( X ,Y, 2)-
lists generated is 238, so that the expected number of lists generated before
the solution is found is 237. The price we pay for this simplification is that we
cannot implement the duplicate-reduction step which reduces the number of
putative 2-lists, and thereby reduces the overall work factor. If more than 13
bytes of known plaintext is available, the simplified attack given here will have
a higher work factor than the nonsimplified attack discussed above, provided

that the duplicate-reduction step is implemented.

Improved PKZIP?
Unlike the ORYX cipher, for example, the Achilles™ heel of the PKZIP cipher
is not immediately obvious. It seems that many aspects of the design are
slightly weak, and these combine to create an overall weak cipher.
However, the use of the CRC appears to be the weakest link in the chain.
The problem with the CR.C is that there exists a relatively simple inversion
formula. Perhaps if we replace the CRC with some other operation that is
harder to invert, the resulting cipher would be st,ronger.
Recall that the CRC calculation is of the form Y = CRC(X,b), where X
and Y are 32-bit integers, and b is a byte. So to replace the CRC, we need a
function that takes as input a 32-bit word and a byte, and generates a 32-bit
output. We also want our function to be hard to invert. A cryptographic hash
function would seem to be the ideal choice here (see Chapter 5), where we
let Y = h ( X ,b ) for some hash function h,, with the output truncated to 32 bits,
if necessary. Then we would expect about 256 collisions for each possiblc Y .
In fact, a CRC is sometimes mistakenly used where a cryptographic hash is
required (sce t,he discussion of WEP in Section 3.4, for example), arid this
may explain why a CRC was used in PKZIP. However, it is more likely that
the CR.C was used in the PKZIP cipher since it was already available as part
of the ZIP compression routine, and it was necessary to minimize the overall
size of the code.
In keeping with the spirit of PKZIP, we should replace the CRC with
something that does not have much computational or coding overhead. This
might preclude a sophisticated cryptographic hash function, which makes the
problem more challenging (see Problem 30).

RC4, ORYX and PKZIP present interesting but very different cryptanalytic
challenges. For RC4 (as used in WEP), a subtle issue in the method used
to conibiiie the IV and the long-term key leads to a devastating attack. A
slight modification to the usage of RC4 renders this attack infeasible. In
stark contrast, ORYX is a fundamentally flawed cipher. If known plaintext
is available, the work factor to break ORYX is trivial. Not surprisingly, there
is also a ciphertext-only attack on ORYX [153].
Of the three attacks considered in this chapter, the PKZIP attack is the
most challenging. It is not particularly difficult to see that PKZIP has an
exploitable weakness, but working through the details is not for the faint of
3.7 PROBLEMS 121

1. Complete steps N = 4 through N = 15 of the Berlekamp-Massey Al-
gorithm for the example in Table 3.2. Give the connection polynomial
and verify that your answer is correct by generating the first 16 fills of
the LFSR corresponding the your claimed connection polynomial, with
initial fill 10011. Hint: The linear complexity is L = 6.

2. Illustrate the smallest LFSR (including the initial fill) that can generate
the sequence in (3.3).

3 . Suppose that K = ( k o ,k l , . . .) is a keystream bit sequence. If there ex-
ists a bit sequence I? = (,&, &, . . .) that differs in only a few elements
from K and I? has a small linear complexity, why is K a cryptograph-
ically weak keystream sequence?

4. The Chan--Games Algorithm [141] is more efficient than the Berlekarnp-
Massey Algorithm, for the special case where the binary sequence s has
period 2n. The Chan-Games Algorithm computes the linear complex-
ity L of s as follows:

a = s , L = 0 , m=2n
while m > 1
m = m/2
e = aoa1 . . . a,- 1
r = a,a,+l.. . a2,-1
if b == 0 0 . . . 0 then
end if
end while
if wo == 1 then
end if

Note that t is the left half of the sequence a and T is the right half. Use
the Chan-Games Algorithm to determine the linear complexity of the
sequence with period s = 10011100.

5. Recall the correlation attack discussed in Section 3.2.4. Consider the
stream cipher in Figure 3.8, and suppose that Trudy recovers the con-

seciitive keystream bits

( k o ,k l , . . . , k30) = 0000110011001001011101100010010.

Determine the initial fills of registers X , Y ,and 2

6. Show that the size of the state space of the RC4 cipher is bounded
216 . 256! 21700.

7. In the RC4 attack, suppose that 60 IVs of the form (3,255,V) are
available. Empirically determine the probability that the key byte A3
can be distinguished. What is the sniallest number of IVs for which
this probability is greater than 1 / 2 ?

8. In (3.11) and (3.13) we showed how to recover RC4 key bytes K3 and Ks,

a. Assuniing that key bytes K:3 through Kn-l have been recovered,
what is the desired form of the IVs that will be used to recover Kn?
b. For I what is the formula corresponding to (3.11) and (3.13)'?

9. For the attack on RC4 discussed in Section 3.4, we showcd that the
probability that (3.11) holds is (253/256)"'. What is the probabil-
ity that (3.13) holds? What is the probability that the corresponding
equation holds for K,?

10. In the discussion of the attack on RC4 keystream byte K3 we showed
that IVs of the form ( 3 , 2 5 5 , V ) are useful to the attacker. We also
showed that IVs tha.t are not of this form are sometimes useful to the
attacker, and we gave the specific example of the (2,253,O). Find an-
other 1V r i o t of the form (3,255, V )that is iisefiil in the attack on A'3.

1I . The attack on RC4 discussed in this section illustrates that preperiding
an IV to a long-term key is insccure. In [51] it is shown that appending
the IV to the long-term key is also insecure. Suggest more secure ways
to employ RC4 when a long-term key is combined with an IV.

12. In the ORYX attack, suppose that the recovered bits (using the first 29
keystream bytes) are

( X > 1) = 0˜9b874560b
( A > 1) = Oxacd789046
( B >> e) = Ox19910954207e2

and that KO= Ox9f. Find and the initial fills of ( X ,A, B ) .
3.7 PROBLEMS 123

13. This problem deals with the branching that occurs in the ORYX attack.

a. How much branching is expected at the K1 step of the ORYX
attack? Hint: After the KOstep, there are 65,536 putative fills. At
the next iteration, we test 12 extensions of each of these putative
fills. How many of these 65,536 produce more than one result that
is consistent with an extension of X ?
b. What is the expected branching at each of steps K1 through K N ?
c. Suppose that we implement the ORYX attack without branching.
That is, no more than one valid extension of any given fill is re-
tained. If this is the case, what is the probability that the solution
is found?

14. When analyzing the ORYX attack, we assumed that the permutation L
acts as a “random” permutation of the values {0,1,2,. . . ,255). Suppose
that instead, L is the identity, that is, L[i]= i, for i = 0 , 1 , 2 , .. . ,255.
In this case, explain why the ORYX attack given in this chapter will
fail and describe an alternative attack that will succeed.

15. Discuss possible ways that the ORYX keystream generator can be modi-
fied to prevent the attack given in this chapter. Consider methods that
result in a more efficient cipher than the modifications mentioned in
Section 3.3.3.

16. Analyze the modified version of ORYX discussed in Section 3.3.3 for
potential weaknesses. You may assume that unlimited known plaintext
is available.

17. Give the PKZIP decryption routine that corresponds to the encryption
routine in Table 3.11.

18. For b = 0 , 1 , 2 , .. . ,255, define

CRCtable[b] = CRC(O,b),

where CRC(X,b) is defined for the PKZIP stream cipher in Table 3.14.
Show that

19. For b = 0, 1 , 2 , .. . ,255, define

CRCinverse[(CRCtable[b])24I] = (CRCtable[b] << 8) @ b,

where CRCtable[b] is defined in Problem 18. Show that if

(x)O23 @ CRCtable[(X)24...31 @ b],
y = ...

(Y < 8) @ CRCinverse[(Y)o.,,7] b.
X @

20. Consider the getKeystreamByte function of the PKZIP cipher, which
appears in Table 3.12. Verify that for any value of the keystream byte k ,
there are precisely 64 distinct values t that yield k .
21. Verify that for 32-bit integers X and Y ,

{ if X 2 Y (mod 224)
(X)O 7 ( y ) O ... 7
(x ... -
y)O 7
... =
if X < Y (mod 224)
(Y)o7 - 1
(X)o...7 ...

3,645,876,429 (mod 2 3 2 ) .
22. a. Verify that 134,775,813-1 =
b. Let C = 134,775,813-1 = 3,645,876,429 (mod 2 3 2 ) . Show that for
any byte values a and b,

(ac f b)0...7 (aC)0... 7 , (3.28)

where the addition is modulo 232
c. For which 32-bit integers C does (3.28) hold for all byte values a
and b?

23. Suppose that
B + u (mod 232),
A .C =

where A, B and C are 32-bit words, with C = 3,645,876,429 and a is
a byte. Then what is the probability that ( A. C ) O . .=˜(B)0...7? The
motivation for this choice of C can be found in Problem 22.

24. Use the results of Problenis 21 and 22, along with (3.19), to show that

{ (((x cO 7
) ...
l)' C . C)O...7
1) ( ( X i ) 2 4...3 1
- -

( X - 2 ) O ...7 =
cO 7
) ...

c - 1) 1
( x) 4 ...31
( i2 c ) O ... 7
- -
- ' ' '

where the conditions that determine which half of the equation applies
are analogous to those in Problem 21.
25. Suppose that A and B are randomly sclected 32-bit integers. Let

x = A + ( w 2 4 ...3 1 ,
where the addition is taken modulo 2 3 2 . What is the probability that

(x)O7 # (A)0 77
... ...

26. In the PKZIP attack, show that if you are given (y2-1)0...7 and (x)0...7,
(Xi-1)24...31 and J' that sat-
then the riurnber of 32-bit values K-1
isfy (3.19) is in the range of 65,534 to 65,538, inclusive.
3.7 PROBLEMS 125

27. In step 1 of the PKZIP attack, as specified beginning on page 114,
we explain how t o recover Zi-1 given 2,.Give precise equations for
z - ) 4 and ( ˜ 2 - 1 ) 3 0 . . , 3 1 ,given Zi
(zi-1)02 3 , ( i 1 2

28. As a function of x, find the precise distribution on the number of solu-
tions a t o the equation
x = { aC
where a and x are bytes with x given, and C 3,645,876,429. Also
give the average number of solutions.

29. For the PKZIP attack, experimentally determine the expected num-
ber of surviving Z-lists when n additional keystream bytes are used
in the duplicate-reduction step, for n = 0 , 1 , 2 , . . . , m, where m is at
least 10,000. For each n,run a t least 100 trials. Plot your results on a

30. In Section 3.5.3 it is suggested that the weakest component in the
PKZIP cipher is the use of the cyclic redundancy check (CRC), and
we argue that a cryptographic hash function would be ideal. Suggest
a possible replacement F for the CRC in PKZIP, where Y = F ( X ,b ) ,
where X and Y are 32-bits, and b is a byte. Your function F must be
computationally efficient and only require a small number of lines of
code. Explain why your suggested replacement is better than the CRC
used in PKZIP.
This Page Intentionally Left Blank
Chapter 4

Block Ciphers

Through block play, children are confronted with man,y mental challenges
having to do with measurement, equality, balance, shape,
spatial relationships and physical properties.
- Creativity and Play [I121

Recall that a classic codebook cipher uses books filled with “codes” to encrypt
and decrypt messages. Such codebooks have some inherent weaknesses. For
example, any known plaintext immediately gives away part of the codebook.
Also, information about the codebook can be obtained based on a statisti-
cal analysis of the ciphertext, in much the same way that information leaks
through a simple substitution (although far more data is required to attack a
respectable codebook than a simple substitution). Due to the threat of such
attacks, new codebooks would have to be issued on a regular basis.
Modern block ciphers can be viewed as roughly the electronic equivalent
of classic codebooks. In block ciphers, a block of n plaintext bits is encrypted
to a block of n ciphertext bits. Provided that the same key is used, the same
plaintext block will always be encrypted to the same plaintext block, and vice
versa. This is analogous to a classic codebook, except that the “book,” which
would contain the binary n-tuples, is virtual in the sense that the lookups are
accomplished using an algorithm that computes the required bits. That is,
the entries of the codebook are computed as needed instead of being stored
in an actual book.
In a block cipher, the key determines the codebook. Consequently, if we
change the key, we have, in effect, switched codebooks. If the key is k bits,
then the block cipher algorithm can be viewed as 2k codebooks, indexed by
the key. Therefore, by occasionally changing the key, we can avoid the classic


codebook attack mentioned above.
A generic block cipher is illustrated in Figure 4.1, where P, is the ith
block of plaintext and C, is the corresponding block of ciphertext,. The inner
workings of the block cipher can be complex, but when encrypting, the net
effect, is simply to “lookup” the ciphertext block that corresponds to the given
plaintext block in the specified codebook, where the codebook is determined
by the key.

Figure 4.1: Generic block cipher.

Next, we consider some of the different ways that a block cipher can be
used in practice. This further highlights the connection between modern
block ciphers and codebooks. Then we discuss one popular rnethod of block
cipher design before we consider the cryptanalysis of some particular block

Block Cipher Modes
Classic codebook ciphers often employed a so-called additive to make code-
book attacks more difficult, and thereby extend the useable lifetime of the
codebook. Typically, a codebook would convert words or phrases t o strings
of decimal digits. An additive book was filled with random string of digits.
For each message, a random point in the additive book was selected, and
subsequent entries in the additive book were added to the ciphertext before
it) was transmitted. The starting point in the additive book was usually sent
in the clear (or slightly obfuscated) at the start of the message.
For modern block ciphers there is a somewhat analogous concept to the
additive. But before we get to that, we consider an example to show why
sornetliing like this is necessary for block ciphers.


. 5
( 16)