Exhaustive Key Searches

What is an exhaustive key search?

There is one important method that can be used to break almost all known encryption algorithms. This attack is so important that it provides a security benchmark against which the effectiveness of other attacks can be measured.

Conducting an exhaustive key search

An exhaustive key search can be conducted by an attacker who is in possession of a target ciphertext that has been encrypted using a known encryption algorithm. The attacker follows these steps:

1. They select a decryption key from the keyspace of the cryptosystem.

2. They decrypt the target ciphertext using that decryption key.

3. They check to see if the resulting plaintext makes sense.

4. If the plaintext does make sense, then the attacker labels the decryption key as a candidate decryption key.

5. If the attacker can confirm that this decryption key is the correct decryption key, then the attacker stops the search. Otherwise, the attacker selects a new decryption key from the keyspace and repeats the process.

In other words, an exhaustive key search involves decrypting the ciphertext with different decryption keys until candidates for the correct decryption key are found. If the correct decryption key can be identified as soon as it’s tested, then the attacker stops the search as soon as it’s found. If it cannot be identified, then the attacker searches all possible decryption keys until the list of candidate decryption keys is complete. This type of attack is sometimes also referred to as a brute-force attack since, in its simplest form, it involves no sophisticated knowledge of the cryptosystem other than the encryption algorithm used. The above steps have been visualized below for better understanding: