Information Technology Reference
In-Depth Information
Following the above proposition, the probability distribution of
C
is obtained as
Pr
(
C
=
k
)=
A
k
n
n
,
(2)
1
n
)
n
which is approxi-
for
k
=1
,
2
,...,n
. The expected value of
C
is
n
−
n
(1
−
e
−
1
) and for large
n
, hence
C
mately
n
(1
−
≈
0
.
63
n
.
Iterative application of
f
to
x
0
∈
X
yields the sequence
{
x
0
,x
1
=
f
(
x
0
)
,x
2
=
f
(
x
1
)
,...,x
n
=
f
(
x
n−
1
)
}
.
(3)
In Fig. 1, the typical behavior of an iteration operation is given. Since the set
X
is finite, after some iterations, we will encounter a point that has occurred
before. Starting with a point
x
0
,let
x
m
be the point that the iteration enters a
loop to form a cycle. The path between
x
0
and
x
m
is called the
tail length
.The
sum of the tail length and cycle length is defined as the
ρ
-length
.
x
0
x
m
Fig. 1.
Graphical representation of an iteration
Proposition 2.
The probability distribution of the
ρ
-length for a random map-
ping of
n
elements is given as
k−
2
length
=
k
)=(
k −
1
n
(
n − i
n
Pr
(
ρ
−
)
)
,
for
k
≥
2
.
(4)
i
=1
3
Time Memory Tradeoff Attacks
TMTO attacks aim to speed up the exhaustive key search at the expense of
memory usage and the success rate depends on the time and memory allocated
for cryptanalysis. The attacks consist of
oine
(or pre-computation) and
online
phases. In the oine phase, a look up table based on the cipher is constructed.
In the online phase, a given target is searched using the previously constructed
table. In the attack,
-
N
is the size of the search space,
-
P
is the complexity reserved for pre-calculations,
-
M
is the amount of memory available,
-
T
is the online time complexity and
-
D
is the amount of data available.
