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