Cryptography Reference
In-Depth Information
the left-hand side. The right-hand side is the sum of the difference of the triple
bracketed expressions and the difference of the
B
s. To prevent us from getting
lost in multi-step indices, we define the following terms:
X
=
B
1
−
S
3
for the
B
1
of the first equation;
D
=
B
1
(2nd equation)
−
B
1
(1st equation);
P
=
A
1
(1st equation);
Q
=
A
1
(2nd equation);
K
=
k
1
(1st equation);
L
=
k
1
(2nd equation); and
R
B
(2nd equation).
The difference of the two equations will then look like this:
=
B
(1st equation)
−
⊕
P-((X+D)>>>L)
⊕
Q=R(4)
(X>>>K)
(where XOR
=
'
⊕
' is executed prior to the subtraction). All quantities except
X
are known in (4).
K>L
also holds based on our assumption. We set
n
=
K
−
L
.
We can use brute force on
n
bits to determine the value of
X
from equation (4)
(the reason why
n
should be as small as possible). That's the difficult part of
this cryptanalysis.
As a starter, we look at arbitrary values of the
n
bits
x
L
...x
K
−
1
of
X
. Using (4),
we can determine
n
bits
y
K
...y
K
+
n
−
1
of the 32-bit number (
X
D)
, where
y
32
should be equal to
y
0
,y
33
should be equal to
y
1
, and so on. From this,
in turn, we obtain
n
bits
x
K
...x
K
+
n
−
1
of
X
, but ambiguously — depending
on whether or not the addition of
X
and
D
produced a carryover in bit
L
.
Similarly, we compute the next
n
bits of
X
. This computation is unambiguous
since a carryover can be determined if there is one. After 32/
n
+
1 steps, we
can compute known bits and check whether or not things work out. If they
don't, we try our luck with the next
n
-bit combination,
x
L
...x
K
−
1
.
There has to be a solution for
X
. Perhaps only a few other solutions remain (the
smaller the difference,
n
,of
K
and
L
, the fewer solutions are possible). For each
X
+
S
3
found, we compute
S
3
(since
B
1
is known as a ciphertext half
block) from (2), then we compute
B
0
and from this
S
1
again. Consequently, we
=
B
1
−