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