Cryptography Reference
In-Depth Information
ROUNDS
COMPLEXITY OF ATTACK
2
43
12
2
44
13
2
51
14
2
52
15
2
58
16 (full DES)
To start off, I'll show how to break the three-round DES, and then extrapolate the process further.
For our plaintext differential, we will always have the right (least significant) 32 bits be all zeros, with the
left (most significant) being a particular pattern.
Recall from Chapter 4 that DES's main round function looks as follows:
1.
R
i
+1
=
L
i
⊕
f
(
R
i
,
K
i
+1
).
2.
L
i
+1
=
R
i
.
Expanding this out to three rounds (values in bold are known values):
1.
R
0
= 0.
2.
L
0
(arbitrary, random).
3.
R
1
=
L
0
⊕
f
(0,
K
1
).
4.
L
1
=
R
0
= 0.
5.
R
2
=
L
1
⊕
f
(
R
1
,
K
2
) =
f
(
R
1
,
K
2
).
6.
L
2
=
R
1
.
7.
R
3
=
L
2
⊕
f
(
R
2
,
K
3
) =
R
1
⊕
f
(
R
2
,
K
3
).
8.
L
3
=
R
2
=
f
(
R
1
,
K
2
).
Now, if we have a second plaintext-ciphertext pair (say, ), with the new plaintext having a
known differential to the previous plaintext (Ω), then we have the following derivation:
Here, we have underlined where the differential propagates.
From the last steps of the two previous lists, since we know the values of
L
3
and , we can calculate Δ,
the difference in the ciphertexts. We also can perform a differential analysis of the S-boxes of DES, so that the
effect of the differential Ω would be known, and we can choose Ω to exploit this for each S-box (since DES has
several distinct S-boxes).
Once we know some good characteristics of the round function, we can then set up the three-round cipher to
use the plaintext differential on the left to create differences in the plaintext. After measuring enough of these,
we will be able to make good guesses at the key bits.
In general, we can easily see that if the right-half XOR is 0, and the left half has an arbitrary differential (
say,
L
), we can construct a characteristic for a round of DES.
Search WWH ::
Custom Search