Cryptography Reference
In-Depth Information
Input
: an encryption scheme
C
, a fixed message
x
Parameter
:
m
,
t
Preprocessing
1:
for
j
=
1to
t
do
pick a reduction function
R
j
at random and define
f
j
:
k
→
2:
R
j
(
C
k
(
x
))
3:
end for
4:
for
i
=
1to
m
do
repeat
5:
pick
k
at random
6:
k
k
←
7:
for
j
=
1to
t
do
8:
compute
k
←
f
j
(
k
)
9:
end for
10:
until
T
contains no (
k
,.
) entry
11:
k
) in table
T
insert (
k
,
12:
13:
end for
Figure 2.40.
Time-Memory tradeoff with a rainbow table (Preprocessing).
mt
2
n
e
−
≈
1
−
.
t
2
2
The time complexity of the attack is
T
=
encryptions and reductions in the worst
t
2
8
case, and
T
e
=
in the average case (for success only). The memory size is about
2
2
3
(log 2)2
3
2
3
we obtain
P
2
n
,
M
=
m
blocks. With
m
=
and
t
=
≈
0
.
693
×
≈
2
2
3
,
T
2
2
3
, and
p
1
M
≈
≈
0
.
240
×
≈
2
. This is a substantial improvement.
To summarize brute force generic attacks, we list in the following table the
essential
complexity of each part of the attack for a probability of success close to one.
Strategy
Preprocessing
Memory
Time
Exhaustive search
1
1
N
Dictionary attack
N
N
1
N
3
N
3
Tradeoffs
N
2.9.5 Meet-in-the-Middle Attack
In order to strengthen DES, people first tried to make a simple product with itself,
resulting in a double-DES (see Section 2.3.1). More generally, we have
C
K
2
C
K
1
(
X
)
.
C
K
1
K
2
(
X
)
=
Search WWH ::
Custom Search