Cryptography Reference
In-Depth Information
I certainly don't want to suggest that Roger Schlafly designed the algorithm
'arbitrarily'. (The use of an initialization vector and the inclusion of the plain-
text in the key stream generation show profound knowledge.) Gradually chang-
ing the
key
variables is also typical:
key0
changes
key1, key1
changes
key2
, and
K
is computed only from
key2
. But things will go as they went for Schlafly for
everybody who builds a 'wild' algorithm on the off-chance: his method will be
cracked, not only in theory.
pkzip
is instructive in this respect — cryptanalysts
would probably proceed in the same way with other insufficiently protected
ciphers, too.
In 1995, Biham and Kocher published a successful plaintext attack against the
pkzip
cipher [Bih.zip]. The article is available on the Internet. It is not easy
to read, so we should take time to do some basic thinking and look at the
results — they are interesting.
As usual with a plaintext attack, we assume that we know at least one byte of
the plaintext and the corresponding ciphertext byte. We can then compute byte
K
from the key byte sequence:
K=P
⊕
C
The first exploitable point is equation (e) above. The multiplication is a strongly
mixing operation, but we are not interested in it at all. We know from (d) that
the two least significant bits of the 16-bit variable
tmp
are equal to 1. So
tmp
can be represented as follows:
tmp = 256a + b + 3
where
a
and
b
denote bytes, and the last two bits of
b
are equal to 0. We can
thus write (e) alternatively as follows:
K = LSB((2b + 5)a) + MSB((b + 2)(b + 3))
where
LSB
stands for 'least significant byte', and
MSB
stands for 'most sig-
nificant byte'. We can use both to unambiguously determine the lower-order
byte of (2
b
5)
a
for given
b
and
K
. But we can also compute
a
now, since
the congruence
+
