Basic Principles - Everyday Cryptography - page 37

to test one decryption key. We can then use this estimate to assess how long an
exhaustive key searchmight take.We first need one piece of statistical information.
Namely, if the size of the keyspace of an encryption algorithm is 2 k then the laws
of probability imply that, on average, an attacker can expect to find the correct
decryption key in 2 k − 1 decryption attempts.
This is quite an intuitive statement. It says that an attacker can, on average,
expect to find the correct decryption key about halfway through an exhaustive key
search. It might be the first key that they try (lucky!) and it might be the last key
that they try (unlucky!) but, on average, they will find it halfway through.
We can use this information to estimate how large a keyspace needs to be
in order to reasonably withstand an exhaustive key search that takes one year.
There are approximately 3 × 10 7 seconds in one year, which is approximately
2 25 seconds (see the Mathematics Appendix for an explanation). For a number of
assumed computational strengths of an attacker, Table 1.4 shows the approximate
length of decryption key that is needed in order to protect against an exhaustive
key search lasting one year.
To see where the figures in Table 1.4 come from, consider the third row. Note
that one thousand is approximately 2 10 and that one million is approximately 2 20 .
Thus in one year, one thousand processors testing one million keys per second
will be able to test an approximate total of
2 25

2 10 2 20 2 55 × × =

keys. This means that a keyspace of 2 56 should suffice to make it likely that an
exhaustive key search will, on average, take a full year. In other words, if we
estimate that an attacker has one thousand processors that can each test one
million keys per second then, if we want security for one year, the minimum key
length that we should consider is 56 bits. In practice we would be wise to use keys
longer than this, just to be on the safe side.
Note that, somewhat ironically, the threat of an exhaustive key search
presents a case (at least in theory) for slowing down the speed of a decryption
algorithm. While slowing down decryption makes the cryptosystem slightly more

Table 1.4: Key lengths needed to protect against an exhaustive key search that takes
one year

Strength of attack Key length

Human effort of one key per second 26 bits

One processor testing one million keys per second 46 bits

1000 processors testing one million keys per second 56 bits

One million processors testing one million keys per second 66 bits