Brute force attack

A brute force or exhaustive search attack is an attempt to break a cipher by trying all possible keys. This is always possible in theory (except against a one-time pad), but it becomes practical only if the key size is inadequate.

Symmetric ciphers

For a symmetric cipher longer keys protect against brute force attacks. Each extra bit in the key doubles the number of possible keys and therefore doubles the work a brute force attack must do. With an n-bit key, there are 2ⁿ possible keys. On average, a brute force attack must test half of them, performing 2^n-1 encryptions, to find the key. A large enough key makes any brute force attack wildly impractical.

For example, the EFF's DES Cracker searched a 56-bit key space in an average of a few days. Assume an attacker that can find a 64-bit key (256 times harder) by brute force search in a second (a few hundred thousand times faster). For a 96-bit key, that attacker needs 2³² seconds, about 135 years. Against a 128-bit key, he needs 2³² times that, over 500,000,000,000 years. Your data is then obviously secure against brute force attacks. Even if our estimate of the attacker's speed is off by a factor of a million, it still takes him over 500,000 years to crack a message.

This is why single DES with its 56-bit key is now considered dangerously insecure, all of the current generation of block ciphers use a 128-bit or longer key, and AES ciphers support key sizes 128, 192 and 256 bits.

The question of how large a key is "large enough" has been extensively studied. An analysis by a group of well-known people recommended a minimum of 90 bits for any new ciphers deployed as of 1996. Computers improve roughly in accord with Moore's Law, twice as fast every 18 months, so symmetric ciphers need about one extra bit of key every 18 months to keep up.

Public-key Systems

For public key systems the relation between key size and security is more complex. Here an attacker has the public key, and that is mathematically related to the private key. He need not try all possible keys, only solve a math problem. For example, to break a 256-bit RSA key, he has to factor a 256-bit number. This not easy, but it is far better for the attacker than a brute force search.

The question then is not how big the key needs to be to defeat brute force, but how big it needs to be to make the math problem hard enough for the security requirement. In general, the difficulty of such math problems does not increase exponentially — doubling for each extra key bit — as for symmetric ciphers, but more slowly. Asymmetric keys therefore need to be larger than symmetric keys for the same security levels. For example, RSA keys of 1024 bits or more are commonly used.

Cautions

Inadequate keylength always indicates a weak cipher but it is important to note that adequate keylength does not necessarily indicate a strong cipher. There are many attacks other than brute force, and adequate keylength only guarantees resistance to brute force. Any cipher, whatever its key size, will be weak if design or implementation flaws allow other attacks, and even a strong cipher will not provide security unless it is used correctly.

Also, once you have adequate keylength, adding more key bits make no practical difference , even against brute force. Consider our 128-bit example above that takes 500,000,000,000 years to break by brute force. We really don't care how many zeroes there are on the end of that, as long as the number remains ridiculously large. That is, we don't care exactly how large the key is as long as it is large enough.

There may be reasons of convenience in the design of the cipher to support larger keys. For example Blowfish allows up to 448 bits and RC4 up to 2048, but beyond 100-odd bits it makes no difference to practical security.

Related attacks

Sometimes brute force is used as the final stage of another attack. For example, in the original paper on differential cryptanalysis, the differential attack gives 48 bits of the 56-bit DES key and the remaining 8 are found by brute force.

Some ways of combining of ciphers are vulnerable to a meet-in-the-middle attack. Against double DES with two independent 56-bit keys, for example, the attacker need not search among the 2¹¹² possible key combinations; there is a meet-in-the middle attack with cost only 2⁵⁷ if you have enough memory, and not too much more if memory is constrained. This is why triple DES rather than double DES is used in practice; a meet-in-the-middle attack against it needs 2¹¹² operations.

In looking for collisions in hash functions, an attacker can use a birthday attack. This works a bit like meet-in-the-middle; instead of trying all possible inputs and looking for one particular result, you do a large number of hashes, store the results and then do more hashes looking for any match. In general, for a hash of 2ⁿ bits, only 2^n/2 trials are needed.

There is another attack similar to brute force in that it can, in theory, break any symmetric cipher but in practice it is wildly impractical against any reasonable cipher. This is an analytic crack. Express the cipher operations as a system of equations (in whatever algebraic system works best for the attacker), then plug in one or more known plaintext/ciphertext pairs for some of the variables, and solve for the key. For example, for DES we might create 64 boolean equations each expressing one input bit in terms of 64 input bits and 56 key bits. Put in known values for input and output bits and you have 64 equations in 56 variables, which is, at least in theory, soluble. For a cipher where key size exceeds the block size, you need more known pairs, but the same principle applies.

What makes this impractical is a combination of the sheer size of the system of equations used and non-linearity in the relations involved. In any algebra system, solving M linear equations in N variables is more-or-less straightforward, but non-linear systems are much harder. Non-linearity also makes a number of other attacks more difficult. One technique for introducing non-linearity is to mix operations from different algebraic systems, for example using both arithmetic and logical operations within the cipher so it cannot readily be described with linear equations in either normal or boolean algebra. Another is to use s-boxes, lookup tables containing non-linear data.