Cryptography Reference
In-Depth Information
Attack
:
1:
initialize 2
7
counters
n
u
,
v
to zero for all possibles 6-bit values
u
and
all possible bits
v
.
2:
collect
n
plaintext-ciphertext
(
x
,
y
)
pairs,
3:
for
each
(
x
,
y
)
pair
do
4:
set
u
to the 6 leading bits of the expansion
E
(
y
R
)
of
y
R
in the
round function
v
←
(
a
·
x
)
⊕
(
b
L
·
y
R
)
⊕
(
b
R
·
y
L
)
5:
6:
increment
n
u
,
v
7:
end for
8:
for
all possible κ
do
9:
compute
c
κ
=
n
−
u
,
v
n
u
,
v
⊕
(
b
R
·
(
P
(
S
1
(
u
⊕
κ
)
||
0000000
)))
10:
end for
11:
sort all possible κ in decreasing order of
|
c
κ
−
n
2
|
,
12:
do an exhaustive search by using the sorted list for κ.
Figure 4.9.
Linear cryptanalysis of eight-round DES.
Thus, in order to be the top candidate, it suffices to have
4
λ
log
B
N
=
2
.
2
6
bad candidates, so the right candidate for
Here we have roughly
B
=
κ
will be
13
.
86
λ
2
−
16
the top one in the sorted list of graded candidates for
N
=
. Since
λ
≈
we
2
20
is far enough.
deduce that
N
=
The complete algorithm is depicted in Fig. 4.9. In order to avoid computing
c
κ
with
a loop of
N
iterations for the 2
6
possible values of
κ
, we can first preprocess the
N
sam-
ples into some counters so that each
requires a little computation from these counters
in order to compute
c
κ
. As we can see, the complete algorithm includes several phases.
κ
1. A collecting phase of complexity
N
in which we preprocess the samples into
the counters.
2. An analysis phase of complexity 2
6
in which we grade each candidate
κ
.
3. A sorting phase of similar complexity in which we sort all candidates.
4. A searching phase in which we look for the key using the information obtained
from the analysis.
Here, the last phase requires a complexity of 2
50
when the right candidate is top-ranked.
This complexity can be substantially decreased by applying a similar analysis based on
another characteristic so that we recover some other bits of the key. For instance, once
we have recovered the key bits corresponding to
S
1
in the final round, we can look for
the key bits corresponding to
S
5
in the first round. Here the bias of the characteristic
is even larger since we cancel the (16
32)
2
factor. This leads to 6 additional bits on
the key so that only 44 are missing. Further improvements and experiments show that
using
N
/
2
21
=
we recover the full key within a few seconds of computations with a
Search WWH ::
Custom Search