Cryptography Reference
In-Depth Information
(The reciprocal of 134 775 813 is formed modulo 2
32
.) Since the most significant
byte of
key1
i
−
1
is given and
LSB
(
key0
i
)
concerns only the eight lowest-order
bits on the left side (except for carryovers), the eight most significant bits on
the left side are given. Consequently, this equation limits the value reserve
for
key1
i
to about 2
24
/
2
8
2
16
. We can now compute
key1
i
−
1
, except for the
eight least significant bits, which are 'disturbed' by the least significant byte of
key0
i
, for each of these 2
16
values. Next, we write the last equation once for
i
−
1 and put in all 256 (2
8
)
possible values for
key1
i
−
1
there — this time on
the right-hand side. Only every 2
8
th value of
key1
i
−
1
will result in the given
most significant byte of
key1
i
−
2
on average. Again,
key1
i
is 'unambiguous on
average'. We thus obtain the least significant byte of
key0
i
. A nice ending,
don't you think?
Let's capture the intermediate state of affairs: we determined 2
22
=
possible
sequences for the values of
key2
, and about 2
16
sequences of
key1
values
are possible for each of these 2
22
sequences. Altogether, this results in approx-
imately 2
38
(or a quarter of a billion) possibilities.
Things get pretty fast from now onwards. We can determine the values of
key0
from (a), (6), and the least significant bytes of
key0
for four successive steps
using the solution of a linear equation system. We take this result to compute
the
key0
values and compare their least significant bytes with the values given
in 2
38
lists for additional steps. This is basically the solution.
We can now decrypt the ciphertext backwards without knowing the plaintext.
This is much easier than the approach above. We obtain the same initial values
for
key2, key1
, and
key0
, i.e., the internal representation of the key. With this,
we decrypt the entire archive.
About 12 or 13 coherent plaintext bytes, which don't necessarily have to be
at the beginning of the file, will suffice for the attack. The complexity of the
computation is around 2
38
, i.e., we have to trial-and-error test roughly one
quarter of a billion key lists. This complexity can be dramatically reduced if
more plaintext is known.
When computing
key2
i
−
1
from
key2
i
, we get double values. This reduces the
number of possible
key2
in every computation step. So, with 12 000 known
plaintext bytes, about 2000 lists instead of 2
22
(4 million) remain typically,
reducing the complexity of the entire computation from 2
38
(250 billion) to 2
27
(about 100 million) lists.
Biham and Kocher even found a way to reveal the unknown key. Remem-
ber that it was initially used as 'plaintext', while the 'ciphertext' created
