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

There is a trick in order to strengthen the security against exhaustive search: make
a key schedule complicated. In general, the key schedule is legitimately used only
once for many encryptions. Exhaustive search uses the key schedule many times. For
instance, BLOWFISH has a complicated key schedule.

Input : an oracle O , a set of possible keys K ={ k 1 ,..., k N }

Oracle interface : input is an element of K , output is Boolean

1: pick a random permutation

σ of { 1 ,..., N }

2: for all i

= 1to N do

O

( k σ ( i ) ) then
4: yield k σ ( i ) and stop
5: end if
6: end for
7: search failed

if

3:

Figure 2.34. Exhaustive search algorithm.

We can wonder now what the hypothesis about the availability of the oracle really
means in practice. We may only have some hints about the key. Namely, we can have
some equations that the key must satisfy. Typically, we can assume that we have a
plaintext-ciphertext pair so that the key must solve the equation which says that the
plaintext encrypts into the ciphertext. Another typical situation is when we intercept
a ciphertext and we know that the plaintext has some redundant information, e.g. the
plaintext is an English text. If the equations are characteristic enough for the key, the
unique solution is the right key candidate so that we can simulate the oracle by equation
solution checking.

2.9.2 Dictionary Attack

Another brute force attack is the dictionary attack. A dictionary is a huge table which
has been precomputed in order to speed up a key search. In practice, when one looks
for the definition of a word, it is too expensive to do it by exhaustive search! For this a
dictionary sorts all definitions by using an ordering on a key.

Here is a way to formalize a dictionary attack. We first precompute a list of many
( C K ( x )

K ) pairs for a fixed plaintext x . The first entry C K ( x ) is used as an index in
order to sort the list as in a dictionary, and the second entry K is the “definition.”
Then, if we obtain a C K ( x ) value (by chosen plaintext attack), we directly have a list
of suggested K values. Let M be the number of entries in the dictionary. If K is in a
set of N possible keys, and uniformly distributed, the probability of success, i.e. the
probability that it is in the dictionary, is M

,

N . When K is not uniformly distributed,
we can focus on a dictionary of the most likely K values. This is done in practice when
we try to crack passwords.

/

We now assume that we have T targets C K ( x ) instead of one: there are T secret
keys that we try to attack simultaneously and we are interested in getting at least