Conventional Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 52

Oracle

Yes/No

k

Key

Attack

Figure 2.33. Key recovery with a stop test oracle.

2.9.1 Exhaustive Search

Exhaustive search consists of trying all possible keys exhaustively until it is the correct
key. We can simplify the attack model by assuming that we have an oracle, which for
each key K answers if it is correct or not. The attack is thus a machine which plays with
the oracle in order to get some information out of it by sending queries (see Fig. 2.33).
Without any more formal notion of a “machine,” we can still define the complexity in
terms of number of oracle calls. 10 In a cipher with a key space of N possible keys which
are uniformly generated, we can prove that the best attack has a worst case complexity
of N oracle calls and an average complexity of (about) 2 oracle calls. Clearly, the best
attack can be assumed to be deterministic (otherwise, we just take the machine which
simulates the best deterministic behavior of the probabilistic machine), and does not
query the oracle with twice the same question. Therefore, the best attack can be defined
as an ordering of the candidates for the right key. The optimal ordering is defined by
the a priori distribution of the target key. 11

In practice we do not know the a priori distribution of the target. Thus, if we take a
fixed ordering in order to try key candidates, we may fall into the worst case complexity.
For this we randomize the ordering of the key candidates. Fig. 2.34 shows a program
draft for this attack. In the worst case, the right key is the last one which is sent to
the oracle. If the right key is the i -th candidate, the complexity is equal to i . Since the
permutation σ is randomly chosen, the probability that the right key is the i -th queried

1

one is

N . Thus the average complexity is

N

1
N =

N + 1

i .

2

i = 1

The ultimate security goal of a cipher with keys of n bits is to have a best attack
of complexity

(2 n ) with a “not-too-small” work factor. 12

10

In Chapter 8 we define a formal notion of machine and the notion of complexity of the computation.

11

See Exercise 2.9 on p. 62.

12

This notation means that there exists a constant c > 0 called work factor such that for any n , the
complexity is at least c 2 n elementary operations. The notion of complexity is formally defined in Chapter 8.