Cryptography Reference
In-Depth Information
The original method for time-memory tradeoffs was proposed by Martin Hellman
in 1980 in order to break DES (see Ref. [88]). We assume that we are looking for a
key
K
for which we know a plaintext-ciphertext pair (
x
y
)withafixed
x
. This fixed
x
is necessary to prepare the precomputed table. In practice this attack assumption
makes sense when the adversary performs a chosen plaintext attack (in order to get
y
from
x
) or when the encryption protocol requires that the sender starts by encrypting
this fixed message
x
. We further assume that for all
k
the bitstrings
C
k
(
x
) have the same
size which is larger than the key length so that it is likely that values of
k
for which
y
,
=
C
k
(
x
) reduce to the unique solution
k
=
K
.
One first selects an arbitrary “reduction function”
R
which reduces a bitstring of
the size of
y
to a key candidate
R
(
y
). This leads to the definition of a function
f
f
(
k
)
=
R
(
C
k
(
x
))
which maps a key candidate to another key candidate so that we can iterate it. The
precomputation consists of making a table of
m
pairs (
k
i
,
0
,
k
i
,
t
) where all
k
i
,
0
are
randomly selected and
k
i
,
t
is the
t
-th term of a sequence
k
i
,
j
defined by
k
i
,
j
=
f
(
k
i
,
j
−
1
)
.
(See Fig. 2.36.) In order to look for
K
once we are given
y
, we can apply
R
to
y
and
repeatedly apply
f
until we find a value which matches one
k
i
,
t
in the table. If we find
one value
k
i
,
t
, we can get
k
i
,
0
from the table and apply
f
repeatedly until we find
R
(
y
)
again. Note that if the total number of
f
applications reaches
t
1 without success we
can give up and the attack fails. Otherwise we find a key
k
such that
f
(
k
)
−
=
R
(
y
). This
may be due to
C
k
(
x
)
=
y
, which leads to
K
=
k
. Otherwise the attack fails. Figs. 2.37
and 2.38 with
set to 1 illustrate this method.
f
1
→
f
1
→
f
1
→
f
1
→ ·
f
1
→
f
1
→
k
1
,
0
k
1
,
1
k
1
,
2
k
1
,
3
k
1
,
t
−
1
k
1
,
t
k
1
,
t
,
k
1
,
0
)
(
f
1
→
f
1
→
f
1
→
f
1
→ ·
f
1
→
f
1
→
k
2
,
0
k
2
,
1
k
2
,
2
k
2
,
3
k
2
,
t
−
1
k
2
,
t
k
2
,
t
,
k
2
,
0
)
(
f
1
→
f
1
→
f
1
→
f
1
→ ·
f
1
→
f
1
→
k
3
,
0
k
3
,
1
k
3
,
2
k
3
,
3
k
3
,
t
−
1
k
3
,
t
k
3
,
t
,
k
3
,
0
)
T
1
:
⇒
(
.
.
.
.
.
.
.
.
f
1
→
f
1
→
f
1
→
f
1
→ ·
f
1
→
f
1
→
k
m
,
0
k
m
,
1
k
m
,
2
k
m
,
3
k
3
,
t
−
1
k
m
,
t
k
m
,
t
,
k
m
,
0
)
(
.
f
f
f
f
f
f
k
1
,
0
→
k
1
,
1
→
k
1
,
2
→
k
1
,
3
→ ···
→
k
1
,
t
−
1
→
k
1
,
t
k
1
,
t
,
k
1
,
0
)
(
f
f
f
f
f
f
k
2
,
0
→
k
2
,
1
→
k
2
,
2
→
k
2
,
3
→ ···
→
k
2
,
t
−
1
→
k
2
,
t
k
2
,
t
,
k
2
,
0
)
(
f
f
f
f
f
f
k
3
,
0
→
k
3
,
1
→
k
3
,
2
→
k
3
,
3
→ ···
→
k
3
,
t
−
1
→
k
3
,
t
k
3
,
t
,
k
3
,
0
)
T
:
⇒
(
.
.
.
.
.
.
.
.
f
f
f
f
f
f
k
m
,
0
→
k
m
,
1
→
k
m
,
2
→
k
m
,
3
→ ·
→
k
3
,
t
−
1
→
k
m
,
t
k
m
,
t
,
k
m
,
0
)
(
Figure 2.36.
Table for Time-Memory tradeoff.
Search WWH ::
Custom Search