RSA Laboratories

2.4.3 What is exhaustive key search?

Exhaustive key search, or brute-force search, is the basic technique of trying every possible key in turn until the correct key is identified. To identify the correct key it may be necessary to possess a plaintext and its corresponding ciphertext, or if the plaintext has some recognizable characteristic, ciphertext alone might suffice. Exhaustive key search can be mounted on any cipher and sometimes a weakness in the key schedule (see Question 2.1.4) of the cipher can help improve the efficiency of an exhaustive key search attack.

Advances in technology and computing performance will always make exhaustive key search an increasingly practical attack against keys of a fixed length. When DES (see Section 3.2) was designed, it was generally considered secure against exhaustive key search without a vast financial investment in hardware [DH77]. Over the years, however, this line of attack will become increasingly attractive to a potential adversary [Wie94]. A useful article on exhaustive key search can be found in the Winter 1997 issue of CryptoBytes [CR97].

Exhaustive key search may also be performed in software running on standard desktop workstations and personal computers. While exhaustive search of DES's 56-bit key space would take tens or hundreds of years on the fastest general purpose computer available today, the growth of the Internet has made it possible to utilize thousands of machines in a distributed search by partitioning the key space and distributing small portions to each of a large number of computers. In this manner and using a specially designed supercomputer, a DES key was indeed broken in 22 hours in January 1999 (see Question 2.4.4).

The current rate of increase in computing power is such that an 80-bit key should offer an acceptable level of security for another 10 or 15 years (consider the conservative estimates in [LV00]). In the mid-20s, however, an 80-bit key will be as vulnerable to exhaustive search as a 64-bit key is today, assuming a halved cost of processing power every 18 months. Absent a major breakthrough in quantum computing (see Question 7.17), it is unlikely that 128-bit keys, such as those used in IDEA (see Question 3.6.7) and the forthcoming AES (see Section 3.3), will be broken by exhaustive search in the foreseeable future.

Top of the page