Cryptography Reference
In-Depth Information
Input
: an encryption scheme
C
, a fixed message
x
Preprocessing
1:
for
M
different candidates
K
do
2:
compute
C
K
(
x
)
insert (
C
K
(
x
)
,
K
) in a dictionary
3:
4:
end for
5:
output the dictionary
Attack
Attack input
:
T
many values
y
i
=
C
K
i
(
x
), a dictionary
6:
for
i
=
1to
T
do
look at
y
i
in the dictionary
7:
for
all (
C
K
(
x
)
,
K
) with
C
K
(
x
)
=
y
i
do
8:
yield
i
,
K
9:
10:
end for
11:
end for
Figure 2.35.
Multitarget dictionary attack.
one. (Fig. 2.35 illustrates the program structure.) Let
p
be the probability of success.
Assuming that the target
K
values are independent and uniformly distributed, we have
1
N
)
T
. Hence
−
p
=
(1
−
M
/
e
−
MT
/
N
p
≈
1
−
.
≈
√
N
. Of course the probability of
success increases substantially when the targets are not uniformly distributed and we
focus on most likely candidates.
This becomes quite interesting when
M
≈
T
2.9.3 Codebook Attack
Yet another brute force attack is the codebook attack. . It consists of, first, collect-
ing all (
C
K
(
x
)
x
) pairs, then, upon reception of a
y
to decrypt, look for the entry
in the collection for which
y
,
=
C
K
(
x
). The whole collection of pairs is called the
codebook.
2.9.4
Time-Memory Tradeoffs
An optimized way to perform exhaustive search is to use a large precomputed table
and to make a compromise between time complexity and memory requirements. Here
we must consider four parameters: the time to perform the precomputation, the size of
the precomputed table, the probability of success when looking for a key, and the time
complexity for looking for a key. For the latter parameter, we can also distinguish worst
case complexity and average case complexity.
Search WWH ::
Custom Search