Cryptography Reference
In-Depth Information
Attack
Attack input
:
y
=
C
K
(
x
)
1:
for
i
=
t
down to 1
do
set
k
to
R
i
(
y
)
2:
for
j
=
i
to
t
do
3:
k
←
f
j
(
k
)
4:
end for
5:
if
T
contains one (
k
,.
) entry
then
6:
k
) entry from table
T
get the (
k
,
7:
for
s
=
1to
i
−
1
do
8:
k
←
f
s
(
k
)
9:
end for
10:
if
C
k
(
x
)
=
y
then
11:
12:
yield
k
13:
abort: the attack succeeded
14:
end if
15:
end if
16:
end for
17:
abort: the attack failed
Figure 2.41.
Time-Memory tradeoff with a rainbow table (Attack).
If
C
and
C
have key spaces of
N
and
N
keys respectively, the ultimate security
goal is to have a security related to a minimal complexity of
N
N
. This goal
is not achieved as shown by the following attack. The attack is called “meet-in-the-
middle attack” and was devised by Ralph Merkle and Martin Hellman in 1981 (see
Ref. [133]).
N
×
=
As illustrated in Fig. 2.42, let us consider a known plaintext attack: we know a
(
x
C
K
1
K
2
(
x
). The meet-in-the-middle attack consists of making a
table of all possible
C
K
1
(
x
) (which is of size
N
), and for all possible
K
2
, in computing
C
−
1
,
y
) pair such that
y
=
K
2
(
y
) and looking for the value in the table. This will suggest a list of possible
K
1
K
2
keys which can be tried with other known plaintexts (see Fig. 2.43). The complexity
is
N
+
N
instead of
N
. Therefore doubling the structure is not a good paradigm for
strengthening the security.
2.10
Exercises
Exercise 2.1.
Prove that
DES
K
(
x
)
=
DES
K
(
x
)
.
K
1
K
2
C
C
z
y
x
Figure 2.42.
Meet-in-the-Middle.
Search WWH ::
Custom Search