Cryptography Reference
In-Depth Information
Precomputation
:
1:
for
i
u
∈{
=
2
,
5
,
6
,
7
,
8,
u
,
0
,...,
63
}
and
v
∈{
0
,...,
15
}
initialize
a set SubCanditate
i
,
u
,
u
,
v
to the empty set
2:
for
i
u
,
=
2
,
5
,
6
,
7
,
8, for
u
,
k
∈{
0
,...,
63
}
, insert
k
in the set
SubCanditate
i
,
u
,
u
,
S
i
(
u
⊕
k
)
⊕
S
i
(
u
⊕
k
)
Attack
:
3:
collect
N
pairs
(
x
,
y
)
and
(
x
⊕
a
,
y
)
of plaintext-ciphertext pairs and
let
y
R
(resp.
y
L
) denote the right (resp. left) half of
y
, as well as for
y
4:
for
each pair
do
5:
and
u
=
E
(
y
R
)
and
v
=
P
−
1
(
y
L
⊕
y
L
⊕
compute
u
=
E
(
y
R
)
04000000
)
make the set product Candidate of all SubCanditate
u
i
,
u
i
,
v
i
for
i
=
2
,
5
,
6
,
7
,
8 where
u
i
(resp.
u
i
) denotes the
i
-th 6-bit packet
of
u
(resp.
u
) and
v
i
denotes the
i
-th 4-bit packet of
v
,
i.e.
suggest in Candidate all 30-bit subkeys
k
2
k
5
k
6
k
7
k
8
for which
k
i
∈
6:
SubCandidate
u
i
,
u
i
,
v
i
7:
for all
k
in Candidate, increment a counter
n
k
8:
end for
9:
sort all possible 30-bit subkeys
k
in decreasing order of
n
k
10:
for each possible 30-bit subkey
k
, exhaustively look at all the re-
maining 26 bits and try the corresponding key
Figure 4.3.
Differential cryptanalysis of eight-round DES.
After this attack we recover 30 out of the 48 bits of the eighth subkey. The missing
56
26 bits can be found with an exhaustive search, whose cost is negligible
against the cost of recovering these 30 bits. Therefore we have a chosen plaintext attack
against eight rounds of DES which enables the discovery of the full key after a number
of plaintext pairs with the order of magnitude of 2
13
.
4
. The complexity is essentially
in obtaining the corresponding ciphertexts and managing 2
30
counters. (This last cost
can be efficiently decreased by using further dedicated algorithmic tricks.)
−
30
=
The initial development of differential cryptanalysis techniques made possible to
break reduced versions of DES (as we have just shown) and some DES-like block
ciphers. Later, the cryptanalysis technique was improved and optimized. This led to an
attack on the full DES which requires 2
47
chosen plaintexts to be successful. Interest-
ingly, the attack is scalable in the sense that having fewer chosen plaintexts leads to
an attack with a reduced probability of success. Biham and Shamir have also shown
in 1991 that many slight modifications in the design of the
S
-boxes (even swapping
two existing
S
-boxes) lead to an impressive complexity breakdown (see Ref. [31]).
This suggests that the designers of DES indeed tried to make differential attacks as
hard as possible. Later, Don Coppersmith, one member of the original DES design
team at IBM, released in 1994 a technical report (Ref. [48]) explaining that DES was
made in order to optimally resist differential cryptanalysis attacks. This shows that the
research development of American standardization bodies was indeed 15 years ahead
of its time in the early seventies. However, because of the massive growth of industrial
Search WWH ::
Custom Search