Cryptography Reference
In-Depth Information
with a keyspace of size 2
128
is being used. If an attacker already knows one
plaintext/ciphertext pair then it can be shown that an exhaustive key search that
uses this known plaintext/ciphertext pair to identify candidate decryption keys
for a new target ciphertext will result in at most a handful of candidate decryption
keys. This is because the chances that a different decryption key to the correct
one also successfully decrypts the known ciphertext into the known plaintext is
extremely small. Use of the knowledge of a second plaintext/ciphertext pair will
almost always be sufficient to identify the correct decryption key.
However, even without determining precisely which of a short list of candidate
decryption keys is the correct decryption key, an attacker may still have enough
information to proceed. To see this, suppose that the plaintext is the launch date
for a new product and the attacker is a commercial rival. If the attacker has just
reduced 2
128
possible decryption keys to just three (say) candidate decryption keys
then this is a spectacularly significant achievement from a security perspective.
Even if all three candidate plaintexts are plausible (in this case they would all have
to be plausible launch dates), the attacker could:
• proceed to develop three separate courses of action, each based on a different
candidate launch date of the rival's product;
• simply guess which one is correct, since they have a one third chance of being
correct.
Thus in most cases it is normally assumed that an exhaustive key search results in
the attacker 'knowing' the correct decryption key and hence the correct plaintext,
even if in practice they are left with a small degree of doubt. Indeed, in some
cases it is probably reasonable to assume that an attacker can identify the correct
decryption key as soon as it is tested, hence they do not need to complete a search
of the entire keyspace.
PROTECTING AGAINST EXHAUSTIVE KEY SEARCHES
An exhaustive key search is indeed exhausting to conduct manually, but this is
precisely the type of process that computers can perform with ease. To withstand
an exhaustive key search there must be so many different decryption keys to try
out that the search becomes impossible to conduct in practice (it either takes too
much time or costs too much money). This is why most practical cryptosystems
must have a sufficiently large keyspace that an exhaustive key search is infeasible.
We now briefly consider how big 'sufficiently large' might be. We make the
assumptions that:
• All possible keys in the keyspace are available and equally likely to be selected.
If this is not the case then the keyspace is smaller than we think and the
subsequent analysis may be invalid.
• The attacker can identify the correct decryption key as soon as it is tested.
Estimating exactly how much time is needed to conduct an exhaustive key search
requires assumptions about the resources available to an attacker. A good place
to start is to try to estimate the amount of time that it might take an attacker
