Cryptography Reference
In-Depth Information
Table 3.4:
Real time of computation for sample complexities
Complexity
n
10
n
30
n
50
=
=
=
n
0.00001s
0.00003s
0.00005s
n
3
0.001s
0.027s
0.125s
2
n
0.001s
17.9 minutes
37.7 years
3
n
0.059s
6.5 years
200 million centuries
LIMITATIONS OF COMPLEXITY
We have just seen that complexity theory is useful for giving some indication of
the time that certain computations will take. It can thus be used to estimate the
time that an attacker will take to successfully attack a cryptosystem using the best
known technique. We have already seen precisely how to do this if the best known
technique is exhaustive key search.
It is thus desirable to base the security of a cryptosystem on a computational
problemwhose complexity is beyond the realistic capabilities of computer systems
that are likely to be employed by an attacker. Determining what an attacker's
computational capability is likely to be, both now and at any time within the
cover time of the data to be protected, is part of risk management and is an aspect
of information security that is beyond the scope of our study.
Note that, as previously observed, decryption of a ciphertext without the key
should involve an exponential-time process. However, returning to our attempts
to define practical security, it must be noted that establishing the complexity of
any known attacks is important and useful, but brings no guarantees of practical
security. There are several reasons why this is the case:
There may be undiscovered theoretical attacks
. As mentioned earlier, we can
only be sure that known theoretical attacks have a complexity that is beyond
the realistic computing power of any attacker. There may be other attacks out
there waiting to be discovered that have lower complexity and are practical to
conduct.
Complexity only deals with the general case
. Complexity can be used to indicate
that
on average
an attack takes a certain time to conduct. This does not,
however, guarantee that a particular manifestation of that attack will not be
successful in less time. For example, there is always a chance (albeit a very small
one) that an exhaustive key search might result in the right key being found on
the very first decryption attempt.
Implementation issues
. Certain practices may compromise the notion of the
complexity of an attack. For example, suppose that an ill-informed organisation
decides to change key on a daily basis and employs the simple technique of
requesting the encryption of the plaintext 00
...
0 every morning in order to
