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.

Brute force is by no means the only attack against a cipher; there are many other techniques under the general heading of cryptanalysis. Also, the system may be weak in various ways that have little to do with the cipher itself — easily guessed passwords, poorly chosen keys, poorly designed protocols, implementation bugs, and so on.

In general, cryptanalytic attacks depend on the specifics of the cipher design. Many of them involve sophisticated mathematics or subtle insights into the cipher's workings. However, brute force is a simple technique that is guaranteed to succeed (eventually!) against any cipher. It requires no subtlety or insights; all the attacker has to do is run test encryptions until he finds the key or gives up. The cost is easily evaluated since it depends only on the size of the key and the cost of test encryptions.

Brute force is therefore used as a sort of benchmark in evaluating any other attack. An attack that is more expensive than brute force is of little interest to the theorist, or to the cryptanalyst trying to crack a cipher, since he already knows a cheaper attack. Any attack significantly better than brute force, however, indicates a weakness in the cipher that is certainly of interest to the theorist and may be to the cryptanalyst.

For an ideal cipher, there is no attack better than brute force. If the key size is enough to make brute force impractical, then all attacks on such a cipher will be impractical. In practice, the requirement is often reduced to "no known attack significantly better than brute force".

In the simplest brute force attack, the attacker has some known plaintext so that he can tell which is the correct key: it encrypts that plaintext to the intercepted ciphertext or decrypts the ciphertext to the plaintext. However, there are variants of the attack based on more limited knowledge of text properties. For example, the attacker might know the plaintext is in the ASCII character set. The top bit of every ASCII byte is zero; only one of 2⁸ keys will give that result, so in attacking a block cipher the attacker can immediately eliminate most candidate keys by testing with a single block. If he has N known blocks, he can reduce the key space by 2^8*N by testing keys against additional blocks. If he also knows that it is English text, additional simple rules can be used to reject possible keys. Some ASCII characters do not appear in English text, so a result containing them can be rejected at once. More heuristic rejection rules can use character frequency or word recognition. It would be quite difficult to get a computer to recognise intelligible English with 100% reliability, but it is quite feasible to get it to reduce the possibilities far enough that a human can easily do the rest.

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 Electronic Frontier Foundation (EFF)'s DES Cracker (a $200,000 machine specifically designed and built to speed up brute force against the Data Encryption Standard) 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. The protected data is then obviously secure against brute force attacks. Even if an estimate of the attacker's speed is off by a factor of a million, it still takes the attacker over 500,000 years to crack a message.

This is why single DES with its 56-bit key is now considered dangerously insecure, most of the post-DES generation of block ciphers used a 128-bit or longer key, and Advanced Encryption Standard (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 minimum values as of 1996: 75 bits for existing ciphers to be considered secure and 90 bits for any new ciphers deployed. 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. At that rate, we should stop deploying new 128-bits ciphers around 2050. The US government already requires [1] 192 or 256-bit AES keys for top secret data, though 128-bit keys may be used with lower classifications.

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 Rivest-Shamir-Adelman (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 often need to be larger than symmetric keys for the same security levels. For example, RSA keys of 1024 bits or more are commonly used.

Choosing key sizes

Resisting brute force is the first consideration in choosing the key size for a cipher, but far from the only one.

Inadequate key length always indicates a weak cipher but adequate key length 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 (see cryptanalysis), and even a strong cipher will not provide security unless it is used correctly.

In a famous historical example, the allied ULTRA project read many German ciphers throughout World War II. The Germans wrongly believed their Enigma machine was unbreakable, largely because it involved too many combinations for a brute force attack. They were correct about brute force; the machine was in fact invulnerable to that in an era without computers. However, Enigma fell to a sophisticated mathematical attack, much aided by various procedural errors by German cipher clerks.

Once you have adequate key length, 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 576 bits and RC4 up to 2048 — but beyond 100-odd bits it makes no difference to practical security.

That said, one might choose to use longer keys, say 256 bits rather than 128, on the principle that this offers some protection against a cryptanalytic attack that might weaken the cipher without completely breaking it. Suppose an attacker discovers a bit of cleverness that reduces the effective key length to half the actual key length. He can break the 128-bit cipher with the cleverness plus a brute force search of the reduced 64-bit key space, clearly feasible for an attacker with large resources. Against a 256-bit key, however he is stymied; even after the cleverness he has a 128-bit space to search and this is thoroughly infeasible.

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.

Two other attacks — an algebraic attack and a code book attack — are similar to brute force in that they can, in theory, break any symmetric cipher but in practice they are wildly impractical against any reasonable cipher.