Cryptography Reference
In-Depth Information
(2b + 5)a = c mod 256
is solvable toward
a
for known
b
and
c
, because 2
b
+
5 is relatively prime to
256 (see Section 4.5.3).
Byte
b
can accept 2
6
=
64 values at most. Knowing key stream byte
K,a
results from
b
unambiguously. So, there are only 64 possible values for
tmp
as well as for the 14 bits 2
,...,
15 of
key2
! The 16 higher-order bits of
key2
are undetermined for the time being; a total of 2
22
(approximately 4 million)
values can be considered for the 30 most significant bits (2
,...,
31) of
key2
with given
K
.
That's all we can get out of (d) and (e); the two least significant bits of
key2
play no role in these equations. We can recover values of
key2
that belong to
successive plaintext bytes from equation (c). The same applies to (a) and (b).
So we need several successive plaintext - ciphertext pairs, i.e., the values of
K
in successive steps. Now things get far more complicated.
Equation (c) won't help us further in the form stated, since we can see in
(5) that the two least significant bits of
key2
play an important role. But the
reversion of
crc32()
described in (6) shows us how to proceed: we represent
key2
i
(the value of
key2
for the
i
th step) as a function of
key2
i
+
1
by means of
(c) and (6), and compare the right and left sides bitwise: if
key2
i
+
1
is known,
then bits 10
,...,
31 are given on the right-hand side, and the left-hand side
can accept only 64 (2
6
)
values in the 14 bits 2
,...,
15 of
key2
i
anyway. Since
the right and left sides have to coincide in the six bits, 10
,...,
15, the 14 bits
2
,...,
15 of
key2
i
are given 'unambiguously on average'. Under this prerequi-
site, we can continue comparing the right and left sides to gradually determine
all 30 bits of
key2
i
and eventually all bits of
key2
i
+
1
. What remains are 2
22
possible values for the entire sequence,
key2
i
+
1
,
key2
i
,...,
key2
1
. This is a
clever attack in my opinion.
However, we haven't reached our goal yet; we don't know the values of
key1
and
key0
. We can use the values for
key2
and the
crc32
reversion (6) to
compute the most significant bytes of
key1
in successive steps. This would
yield us 2
24
(approximately 16 million) values for bytes 0,
...
,23 of
key1
.We
can now easily reverse equation (b):
key1
i
−
1
+ LSB(key0
i
) = (key1
i
−
1) * 134775813
−
1
mod 2
32
