Question 57. 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 55) 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 64) was designed, it was generally considered secure against exhaustive key search without a vast financial investment in hardware [DH77]. Over the years, this line of attack will become increasingly attractive to a potential adversary [Wie94].

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 Skipjack's 80-bit key (see Question 80) can be expected to offer the same level of protection against exhaustive key search in 18 years time as DES does today [BDK93].