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 Question 3.2.1) was designed, it was generally considered secure against exhaustive key search without a vast financial investment in hardware [DH77]. To date, there is no public evidence that such hardware has been constructed. Over the years, however, this line of attack will become increasingly attractive to a potential adversary [Wie94]. Another useful article on exhaustive key search can be found in the Winter 1997 issue of CryptoBytes available online at the following URL: http://www.rsa.com/rsalabs/pubs/cryptobytes/html/article_index.html.
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 hundreds of years on the fastest general purpose computer available today, the growth of the Internet has made it possible to utilize thousands of such machines in a distributed search by partitioning the key space and distributing small portions to each of a large number of computers. Recently, a group called distributed.net solved RSA's DES Challenge II, using an estimated 50,000 processors to search 85% of the possible keys, in 39 days.
While the 56-bit key in DES now only offers a few hours of protection against exhaustive search by a modern dedicated machine [Wie94], the current rate of increase in computing power is such that an 80-bit key as used by Skipjack (see Question 3.6.7) can be expected to offer the same level of protection against exhaustive key search in 18 years time as DES does today [BDK93]. 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) or RC5-32/12/16 (see Question 3.6.4), will be broken by exhaustive search in the foreseeable future.