General Cryptanalytic Methods - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 121

5.1 Brute-Force
Although the majority of the time I will be discussing techniques to find the key in the shortest time possible,
we must have a reference point for our work.
Typically,thestandardknown-ciphertextorknown-plaintextattackissimplya brute-forceattack :sonamed
because no highly developed mathematics or simplifications are necessary — we simply try all possible keys
and see which ones give us the correct plaintext-ciphertext pair.
The only real optimization that can be made to brute-force (at least, while still calling it brute-force) is to
split up the key space into chunks and divvy them up between multiple processors or computers. For example,
all keys with the first three bits 000 could go to one computer, while 001 would go to another computer, and so
on.
For ciphers with small key sizes (say, a 40-bit key or less, depending on how computationally intensive the
cryptographic algorithm is), brute-force is not a terrible way to find the key. If we wanted to break a 40-bit key
in about a day, this gives us 24 × 60 × 60 = 86,400 seconds to work with, and 2 40 = 1,099,511,627,776 keys to
try. Therefore, we would like to try about 12,725,829 keys a second. A quick experiment shows that a single
fairly fast processor 1 can do at least 4,000,000 AES encryptions a second. Therefore, only about three or so
processors could break through a 40-bit key space in a day fairly easily. Considering the growing popularity
of multi-core processors, coming up with three or more processors shouldn't pose much of a problem. Further-
more, Moore's Law of transistor growth says that we can break a key with length increased by an additional bit
every two years (since computing power doubles every other year, and an additional bit doubles the amount of
work to be done) [8]. This means DES's 56-bit key will be breakable on a desktop PC in a day around the year
2043.
Brute-Force has one key advantage — it is always guaranteed to find the correct key after some length of
time; this is not always true of other cryptanalytic techniques, especially those based on statistical methods to
find keys. Another advantage is ease of implementation, which gains several additional benefits, such as ease
of optimization.
5.2 Time-Space Trade-offs
In computer science, there is almost always a trade-off that must be made between running time and space re-
quirements. Generally, it is possible to take less time to do certain computational tasks at the cost of increasing
the space requirements. For example, to solve a discrete logarithm problem faster, it is conceivable to build vast
tables of the powers of generators in various finite fields. However, there are an infinite number of finite fields
and a potentially large number of generators; the particular field and generator used for a given problem may
not even be knownuntil a message is actually sent. Both ofthese prevent the discrete logarithm from benefitting
from such a time-space trade-off.
A similar argument could easily be applied to most cryptographic systems: The key, plaintext, and even
ciphertext may be unknown until a message is sent, rendering pre-computation useless. However, there are a
few tricks that can be used to perform pre-computation for any key-based cryptographic algorithm.
The following sections show some of these techniques to trade space for time.