Basic Principles - Everyday Cryptography - page 35

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 they select a new decryption key
from the keyspace and repeat 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 is tested then the
attacker stops the search as soon as it is 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.
IDENTIFYING CANDIDATE DECRYPTION KEYS
In order to decrypt a target ciphertext 'correctly', an attacker conducting an
exhaustive key search needs to be able to recognise when they have found
candidates for the correct decryption key. The attacker thus needs some
information that can be used to identify candidate decryption keys. This type
of information could be:
Some known plaintext/ciphertext pairs : the attacker could then apply each
decryption key to the known ciphertexts to see if that decryption key
successfully decrypts the known ciphertexts into the corresponding known
plaintexts.
Knowledge of the plaintext language : if the plaintext is in a known language,
such as English, then the attacker will be able to use the statistical properties of
the language to recognise candidate plaintexts, and hence candidate decryption
keys.
Contextual information : the attackermay have other information concerning the
plaintext that allows candidate decryption keys to be identified (for example,
perhaps the plaintext has a specific format or begins with a particular known
string of characters).
DETERMINING THE CORRECT DECRYPTION KEY
Suppose now that an attacker is not able to immediately identify the correct
decryption key and thus generates a list of candidate decryption keys. If only one
candidate decryption key is found then the attacker can of course reasonably
deduce that this is the correct decryption key. If more than one candidate
decryption key is found then the attacker will not necessarily be able to identify the
correct decryption key from this list, unless they obtain some extra information
(such as another valid plaintext/ciphertext pair).
However, it should be noted that the list of candidate decryption keys is likely to
be very small. For example, suppose that a highly regarded encryption algorithm