**ZIP Attacks with Reduced
Known-Plaintext**

Michael Stay

AccessData
Corporation

2500 N. University Ave. Ste.
200

Provo, UT 84606

staym@accessdata.com

**Abstract.** In [BK94] Biham and Kocher
demonstrated that the PKZIP stream cipher was weak and presented an attack
requiring thirteen bytes of plaintext.
The *deflate* algorithm “zippers” now use to compress the plaintext
before encryption makes it difficult to get known plaintext. We consider the problem of reducing the
amount of known plaintext by finding other ways to filter key guesses. In most cases we can reduce the amount
of known plaintext from the archived file to two or three bytes, depending on
the zipper used and the number of files in the archive. For the most popular zippers on the
Internet, there is a fast attack that does not require any information about the
files in the archive.

**1
Introduction**

PKZIP is a compression / archival
program created by Phil Katz. Katz
had the foresight to document his file format completely in the file
APPNOTE.TXT, distributed with every copy of PKZIP; there are now literally
hundreds of “zipper” programs available, and the ZIP file format has become a
*de facto* standard on the Internet.

In [BK94] Biham and Kocher
demonstrated that the PKZIP stream cipher was weak and presented an attack
requiring thirteen bytes of plaintext.
Eight bytes of the plaintext must be contiguous and all of the bytes must
be the text that was encrypted, which is usually compressed plaintext. [K92] shows that the compression method
used at the time, *implode*, produces many predictable bytes suitable for
mounting their attack.

Most zippers available today only
implement one of the compression methods defined in APPNOTE.TXT, called
*deflate.* This is in part due
to [BK94]’s results, and in part to the better compression ratio it
provides. *Deflate* uses
Huffman coding followed by a variant of Lempel-Ziv. Once the dictionary reaches a certain
size, the process starts over. It’s
easy to see that the codes for any of the plaintext depend on a great deal of
surrounding plaintext, and that there’s almost no way to get it right unless you
have the beginning of the file. The
difficulty of getting known plaintext was one reason Phil Zimmerman decided to
use it in PGP [PGP98]. Practically
speaking, if one has enough of the original file to get the thirteen bytes of
plaintext required for the attack in [BK94], one has enough to break the
encryption almost instantly.

Without the original file, all is
not lost; we have the file’s type as indicated by its extension, and we have its
size. We have at least one byte of
known plaintext used for filtering incorrect passwords. Zippers also encrypt output from a
pseudorandom number generator that may be vulnerable to
attack.

It is the author’s opinion that the
only reason the PKZIP cipher has held up so well in light of [BK94] is due to
the *deflate* algorithm and the difficulty of getting enough
plaintext. This paper treats the
question of how far we can reduce the plaintext requirement and still break the
cipher in a reasonable amount of time.

**1.1 The PKZIP Stream
Cipher**

The PKZIP stream cipher was designed
by Roger Schaffely and is fully described in the file APPNOTE.TXT found in most
PKZIP distributions. The internal
state of the cipher consists of three 32-bit words: *key0*, *key1*,
and *key2*. These values are
initialized to 0x12345678, 0x23456789, and 0x34567890, respectively. The internal state is updated by mixing
in the next plaintext byte; we follow [BK94] in our description, combining the
*decrypt_byte()* and *update_keys()* functions described in
APPNOTE.TXT into a single function:

unsigned char
PKZIP_stream_byte (unsigned char pt)

{

unsigned short
temp;

key0 = crc32 (key0,
pt);

key1 = (key1+(key0
& 0xFF)) * 0x08088405 + 1;

key2 = crc32 (key2,
key1 >> 24);

temp = (key2 &
0xFFFC) | 2;

return ( (temp * (temp
^ 1)) >> 8)&0xFF;

}

where
^ is XOR, | is OR, & is AND, and >> is right
shift.

For
the purposes of this paper, we define *crc32()* to be

#define crc32(crc, b) ((crc
>> 8) ^ crctab[(crc & 0xFF) ^ b])

The
old CRC state is shifted right eight bits and XORed with the 32-bit entry of a
byte-indexed table to produce the new state. The index is the low byte of the old
state XORed with b. The function is
linear; that is,

crctab[x
^ y] = crctab[x] ^ crctab[y].

The
cipher is keyed by encrypting the user’s password and throwing away the
corresponding stream bytes. The stream bytes produced after this point are XORed
with the plaintext to produce the ciphertext.

The
crux of all of our attacks is the fact that there is almost no diffusion in the
internal state. Of the ninety-six
bits of internal state, eight bits of *key0* affect *key1*; eight bits
of *key1* affect *key2*; and fourteen bits of *key2* affect the
output stream byte.

**1.2 Encrypted File
Format**

Zippers
must prepend twelve bytes to the beginning of the file to be encrypted. The ZIP file format specifies that the
first eleven should be random and that the last should be the low byte of the
archived file’s CRC. The entire CRC
is stored in plaintext, and this byte serves as a password filter. Some zippers, like InfoZIP [IZ] and
WinZip [WZ], store ten random bytes and the low two bytes of the
CRC.

We
assume that *deflate* was the algorithm used to compress the underlying
data. The author did a crude statistical test on a few hundred files of varying
types and sizes and found that given the file type, as indicated by its
extension, and its size, one can guess about the first two and a half bytes of
the compressed file. Since the
checksum bytes are at the very end of the prepended header, we can use them to
augment the plaintext from the file in mounting our
attacks.

**2 Biham and Kocher’s
Attack**

For
completeness, we review [BK94]’s results.
We begin with some terminology.
Bits are numbered from right to left: bit 0 is the ones’ place, bit 1 is
the twos’ place, bit 2 is the fours’ place, etc. Let *p*_{i} be the
*i*th known-plaintext byte, *i* = 1, 2, 3, ... Let *s*_{i} be the
*i*th stream byte. Let
*key0*_{i}, *key1*_{i}, and *key2*_{i} be
the value of *key0*, *key1*, and *key2* after processing
*p*_{i}. Note that
*s*_{1} is a function of the random header and the password; it is
independent of the plaintext. In
general, bits 2 through 15 of *key2*_{i} determine
*s*_{i+1}.

Their
attack proceeds as follows:

XOR
ciphertext and known plaintext to get known stream bytes *s*_{1}
through *s*_{13}.

Guess
22 bits of *key2*_{13}.

This
guess combined with *s*_{13} is enough to fill in eight more bits
of *key2*_{13}, for a total of thirty. *s*_{12} provides enough
information to derive 30 bits of *key2*_{12} and the most
significant of *key1*_{13}.
In general, each stream byte *s*_{i }allows us to calculate
thirty bits of *key2*_{i-1} and the most significant byte of
*key1*_{i}.

We
continue using stream bytes to make a list of the most significant bytes of
*key1*_{13} through *key1*_{8}.

For
each list, we find 2^{16} possibilities for the low 24 bits of
*key1*_{13} through *key1*_{9} by calculating the low
byte of *(key1*_{i}+*LSB(key0*_{i+1}*))* such
that you get the right high byte of *key1*_{i+1}.

From
each of the 2^{16} lists of complete *key1*’s, derive the low bytes
of *key0*_{13} through
*key0*_{10}.

Once
we have the low bytes of *key0*_{10}, *key0*_{11},
*key0*_{12}, and *key0*_{13}, we can use our knowledge
of the plaintext bytes to invert the CRC function, since it’s linear, and find
the complete internal state at one point along the
encryption.

Once
we have the complete internal state, we can decrypt backwards as far as we want;
we decrypt the ciphertext corresponding to *p*_{1} through
*p*_{5} and filter out wrong keys.

We
can break a file with work equivalent to encrypting around 2^{38} bytes
and negligible memory. We need a
total of thirteen bytes of known plaintext: eight for the attack, and five to
filter the 2^{38} keys that remain.

**2.1 Minor Improvement in the Amount of
Plaintext Required**

[BK94]
throws away six bits in *key1*_{7}. By using them, we can reduce the
plaintext requirement to twelve bytes at the cost of increasing the work factor
by four.

**2.2 More Files in the
Archive**

If
we have more than one file in the archive, we can make the reasonable assumption
that they were encrypted with the same password. “Zippers” encrypt at least one check
byte into every encrypted file to verify that the user entered the correct
password. Once we have the complete
internal state of the cipher, we can run it backwards to the beginning of the
file and read out *key0*, *key1*, and *key2*. Since this state is the same at the
beginning of each file (it only depends on the password), we can decrypt the
check byte in each file and use it to filter with instead of known plaintext
from a single file. This also works
if the files are in different archives, but have the same
password.

Since
the attack is so fast, we can afford to guess a couple of stream bytes. If we guess N of them, we get 2^{40 +
8N} keys to filter; this increases the amount of work and the number of
additional files we need, but reduces the amount of known plaintext required
from a single file.

Consider
the N=1 case: if the file was created in a zipper with two checksum bytes, we
can break the file with work equivalent to encrypting 2^{48} bytes. We need two checksum bytes followed by
only four more known plaintext bytes in one file, and three other files in the
archive (six check bytes) to filter the 2^{48} possible
keys.

If
there is only one checksum byte, we can break the file with the same amount of
work, but we need seven files in the archive and five bytes of known plaintext
in addition to the checksum byte.

**3 Divide and
Conquer**

The
limited diffusion of the internal state prompts us to ask how much of the state
we need to guess to process one byte.
If it is small enough, we can guess it and filter out keys that won’t
work with our known stream bytes, then proceed to the next
part.

It
turns out that we can get by with as few as 23 bits. Note that we don’t need to guess 16 bits
of *key0*_{0 }to calculate the low byte of *key0*_{1}:
if we distribute the XOR in the definition of *crc32()*, we see that we
only need to guess 8 bits of *crc32(key0 _{0},
0)*:

LSB(key0_{1}) =
LSB(crc32(key0_{0}, p_{1}))

= LSB(crc32(key0_{0}, 0)) ^
LSB(crctab[p_{1}]).

Now
we distribute the multiplication across the addition in the next
step:

MSB(key1_{1}) = MSB(
(key1_{0} + LSB(key0_{1})) * 0x08088405 + 1
)

(A) =
MSB(LSB(key0_{1}) * 0x08088405) +

(B)
MSB(key1_{0} * 0x08088405) + possible carry
bit.

** **

We
separate the equation into parts we know (A) and parts we need to guess (B), and
find we need to guess nine bits, including a possible carry bit. Note that since we know the low bits of
(*LSB(key0*_{1}*)* * 0x08088405), the carry bit will usually give us more
than one bit of information in the form of an upper or lower bound on the rest
of (*key1*_{0} * 0x08088405) that we haven’t guessed
yet.

Given
a stream byte *s*_{i+1}, we can find sixty four values for bits
2..15 of *key2*_{i}.
It’s easy to see why: fourteen bits of *key2*_{i} produce
eight bits of *s*_{i+1}, so there are six left over. We can create a table of 256 x 64 bytes
such that given *s*_{i+1} and bits 10..15 of
*key2*_{i}, we can look up bits 2..9 of *key2*_{i}.
We call this the preimage
table.

We
guess bits 10..15 of *crc32(key2*_{0}, 0*)* and use
s_{2}, the preimage table, and
*crctab[MSB(key1*_{1}*)]* to find bits 2..9 of
*crc32(key2*_{0}, 0*)*.
We end up with 2^{23} key guesses.

To
find the next part of the internal state, we have to guess about the same
amount. This guess is not illustrated, but we basically guess about eight more
bits of information in each of the three keys. The only complicated part is separating
what we know about *key1* from what we don’t.

We
guess bits 8..15 of *crc32(key0*_{0}, 0*) *directly; the next
guess involving *key1* is a little more complicated:

MSB(key1_{2}) = MSB(
(key1_{1} + LSB(key0_{2})) * 0x08088405 + 1
)

= MSB(
LSB(key0_{2}) * 0x08088405 ) +

MSB(
key1_{1} * 0x08088405 ) + possible carry bit

= MSB(
LSB(key0_{2}) * 0x08088405 ) +

MSB(
(key1_{0} + LSB(key0_{1})) * 0xD4652819 ) +

possible carry
bit

(A) =
MSB( LSB(key0_{2}) * 0x08088405 ) +

(A) MSB(
LSB(key0_{1}) * 0xD4652819 ) +

(B) MSB( key1_{0} *
0xD4652819 ) + possible carry bit.

Again,
(A) is known and we have to guess (B) nine bits, including a possible carry
bit. The carry bit establishes an
upper or lower bound on (*key1*_{0} * 0xD4652819). We end this filter by guessing bits
16..23 and bits 0..1 of *crc32(key2*_{0}, 0*)* and calculating
a stream byte. We have guessed 27
more bits, but the output byte has to match *s*_{3}, so we expect
2^{23+27-8} = 2^{42} key guesses to pass this
filter.

At
this point, we have guessed 24 bits of *crc32(key2*_{0}, 0*)*
and we know *s*_{1}.
From this we can calculate, on average, one full value of
*key2*_{0}. There are
also only around 2^{13} possibilities for key1_{0} due to the
restrictions from the carry bits.
So the third stage consists of guessing bits 16..23 of
*crc32(key0*_{0}, 0*)* and running through the 2^{13}
possible values for *key1*_{0}. We expect 2^{42+13+8-8} =
2^{55} key pieces to pass this filter.

Finally,
we guess the last eight bits of *key0*_{0} and we have a complete
internal state. We will have
2^{63} complete keys to filter with other bytes, whether they are in the
archived file or in checksum bytes in other files. The cost is approximately the same as
encrypting 2^{63} bytes under the stream cipher. The plaintext requirement is four bytes
total; at least one of these may come from the file’s own check
byte(s).

This
is 128 times faster than guessing three stream bytes and using
[BK94].

**4 Random Number
Generation**

InfoZIP
is a cross-platform freeware zipper distribution. Because the C source code is readily
available and is free, it forms the basis of most non-PKZIP zippers, including
the very popular WinZip and NetZip^{*}.

APPNOTE.TXT
does not specify how to generate the prepended random bytes; it only says that
they are used to scramble the internal state of the cipher and are discarded
after decryption. InfoZIP
implements it as follows:

srand(time(NULL)
^ getpid())

For
each file in the order they are stored,

Generate
ten random bytes by calling rand() ten times and discarding all but the high
eight bits of each return value.

Initialize
the cipher with the password.

Encrypt
the ten random bytes.

Append
the low two bytes of the checksum.

Reinitialize
the cipher with the password and encrypt the twelve-byte header and the
compressed file.

* *

*rand()*
is usually implemented as a truncated linear congruential generator. WinZip and NetZip use Microsoft Visual
C++’s implementation, which has a 31-bit seed:

unsigned long
seed;

void srand( unsigned long s ) { seed = s;
}

unsigned short
rand()

{

seed =
0x343FD * seed + 0x269EC3;

return ( (
seed >> 16) & 0x7FFF );

}

Let
*r*_{i, j} be the *j*th random byte in the *i*th archived
file; *i*,* j* = 1, 2, 3, ... Note that the internal state of the
cipher is the same both times *r*_{i, 1} is encrypted. Since XOR is its own inverse,
*r*_{i, 1} is *decrypted* for all *i*. Also, every *r*_{1, j}
reveals the high eight bits of the internal state of the random number
generator.

Since
*rand()* is linear, we can compute two new constants for a generator such
that it outputs every tenth output of the original. We know the upper eight bits of the
generator, so we guess the low 23 bits and start generating every tenth output
and comparing them to the leaked bytes.
Four archived files suffice to uniquely determine the seed that was used
in the random number generator, and therefore every
*r*_{i,j}.

Let
us emphasize that we do *not* have known plaintext at this point, in the
sense that [BK94] requires, because the plaintext was encrypted twice, and we do
not know the actual values of the stream bytes. What we *can* derive is the XOR of
the stream bytes in the first and second encryption.

**5 Parallel Divide and
Conquer**

We
can adapt the divide-and-conquer algorithm from section 3 to use this
information. Once we know the
“random” headers, we can exploit the fact that the internal state was the same
at the beginning of each embedded file and filter guesses with multiple known
plaintext bytes in parallel, instead of being restricted to one byte as in
section 3.

Let
*s*_{i,j,k} be the *j*th stream byte of the *k*th
encryption of the bytes in the *i*th archived file; *i*, *j* = 1,
2, 3, ...; *k* = 1, 2. We
guess the same 23 bits as in section 3, but since we don’t know the actual value
of *s*_{1,2,1}, we have to guess it, too. It is equivalent, and more convenient,
to guess bits 2..9 of *crc32(key2*_{0}, 0*)*. Now we have a prediction for
*s*_{1,2,1}, and can derive *s*_{1,2,2}. We don’t have any information at all
about *s*_{i,1,1}, since it’s the same as *s*_{i,1,2}
and cancels out. We guess it, and
check to see that the second encryption spits out *s*_{1,2,2}. We have to guess a carry bit for the
second encryption, too, so of the 2^{23+8+8+1} = 2^{40} key
guesses, we expect 2^{40-8} = 2^{32} key pieces to pass this
filter on this file.

We
want to filter out all but the correct guess at this stage; fortunately, we know
that the state we are trying to guess was the same at the start of each
encryption. We have an eight-bit
value to filter with in each file, *s*_{i,2,1} XOR
*s*_{i,2,2}, but we also guess two carry bits, so with four more
files in the archive, we can reduce the number of false positives to around
2^{32 - 6*4} = 256. Note
that we now have *ten* carry bits putting restrictions on
*key1*_{0} instead of just one.

We
continue to the next byte of each file.
This time we guess the same 26 bits as in section 3 plus two carry bits,
one for each encryption. With five
files, we have 30 bits to filter with.
We expect that 2^{8+26+2-30} = 2^{6} = 64 key guesses
survive the second stage. Total
work for this stage is 2^{8+26+2} = 2^{36} byte
encryptions.

At
this point we can derive *key2*_{0} as before. Due to all the carry bit restrictions,
we only have on the order of 2^{8} possible
*key1*_{0}’s. We guess
eight more bits of *crc32(key1*_{0}, 0*)* and run through all
the remaining *key1*_{0}’s.
Since we aren’t guessing carry bits any more, we have 40 bits to filter
with. 2^{6+16-40} < 1,
and we expect that only the correct guess survives. Finally, we guess the last eight bits of
*crc32(key1*_{0}, 0*)* and only the correct guess
survives.

Experimentally,
we have found that a key guess passes the second stage only if our guess for
*s*_{i,1,1} is correct.
This usually occurs about one quarter of the way through the first 40-bit
keyspace. After that, we only try
one value for *s*_{i,1,1} instead of 256 and the rest of the attack
takes at most a few minutes.

The
work done in the first stage dwarfs the rest of the work needed. The total work is therefore about the
same as encrypting 2^{39} bytes.
Cracking a file created with this kind of weak PRNG usually takes about
two hours on a 500 MHz Pentium II.
One can then take the three keys and use [BK94]’s second algorithm to
derive a password, if one desires, although the three keys suffice to decrypt
the files.

** 6
Conclusion**

The
PKZIP stream cipher is very weak.
The *deflate* algorithm makes it harder to get plaintext, but in
most cases we can reduce the plaintext requirement to the point where one can
guess enough plaintext based on file type and size alone. The most popular zippers on the internet
are also susceptible to an attack that runs in two hours on a single PC based on
known plaintext provided by the application and independent of the archived
files themselves.

**Bibliography**

[BK94]
Biham, Eli and Paul Kocher. “A Known Plaintext Attack on the PKZIP Stream
Cipher.” Fast Software Encryption 2, Proceedings of the Leuven Workshop, LNCS
1008, December 1994.

[DL] http://download.cnet.com/downloads/0,10151,0-10097-

106-0-1-5,00.html?tag=st.dl.10097_106_1.lst.lst&

[IZ]
ftp://ftp.freesoftware.com/pub/infozip/

[K92]
Kocher, Paul. *ZIPCRACK 2.00 Documentation.* 1992.

http://www.bokler.com/bokler/zipcrack.txt

[PGP98]
*User’s Guide, Version 6.0.*
Network Associates, Inc., 1998.
p.145.

http://www.nai.com

[WZ]
http://www.winzip.com