In cryptanalysis, a brute force attack on a cipher is a brute-force search of the key space; that is, testing all possible keys, in an attempt to recover the plaintext used to produce a particular ciphertext. One definition of "breaking" a cipher is to find a method of recovering the key or plaintext faster than a brute force attack.

In general, a cipher is considered secure if there is no method less expensive (in time, computational capacity, etc) than brute force; Claude Shannon used the term "work factor" for this. Nearly all ciphers lack a mathematical proof of security in this sense, although the one time pad has been proven to provide perfect secrecy.

If the keys were originally chosen randomly, or they are searched randomly, the plaintext will on average become available after half of all the possible keys are tried. An underlying assumption in a brute force attack is, of course, that the cipher algorithm is known. (Since Auguste Kerckhoffs first published it, a fundamental maxim of cryptography has been that security must reside only in the key.) It is also necessary to be able to recognise when the correct key has been found. This could be achieved, for example, by the use of a few known plaintexts, or, in a ciphertext-only attack, testing the candidate plaintexts for similarity to the plaintext language (for example, English language encoded in ASCII).

Symmetric algorithms

The EFF's US$250,000 DES cracking machine contained over 18,000 custom chips and could brute force a DES key in a matter of days — the photograph shows a DES Cracker circuit board fitted with several Deep Crack chips

Symmetric ciphers with keys 64 bits or less are vulnerable to brute force attacks. DES, a widely-used block cipher which uses 56-bit keys, was broken by an Electronic Frontier Foundation (EFF) project in 1998 (see EFF DES cracker), and an RC5 64-bit key message was broken more recently. Many people think that well-funded organisations, especially government SIGINT agencies such as US NSA, can successfully attack a symmetric key cipher with a 64-bit key using brute force. For applications requiring long term security, 128 bits is, as of 2004, currently thought a sufficient key length for new systems using symmetric key algorithms. NIST has recommended that 80-bit designs be phased out by 2015.

Even in situations were 128-bit or larger keys are used with well-designed ciphers like AES, a brute force attack may be possible if keys are not generated properly. Many commercial and shareware security products that proudly advertise "128-bit security" derive keys from a user-selected password or passphrase. Since users rarely employ passwords with anything close to 128 bits of entropy, such systems are often quite easy to break in practice. See: Password cracking. Some security products even limit the maximum number of characters the user can enter to a length that is too small for an adaquate passphrase. Here are some examples of passwords or passphrases generated by methods that provide 128-bit security:

• a random 28-letter password with all single-case letters: "sqrnf oikas ocmpe vflte krbqa jwf"
• a random 20 character password with mixed-case letters, numbers and special characters: "iTb. /&/-} it/P; ^+22q"
• a randomly-chosen 10-word Diceware passphrase: "serf bare gd jab weld hum jf sheet gallop neve"

Almost no one uses passwords this complex. One solution is to accept lower strength. 16 letters or 6 Diceware words will provide 75-bit security, enough to protect against all but the most powerful cryptanalytic agencies. Another partial solution is to use a key derivation function (KDF) or "key stretcher" that performs significant computational work in converting the password into a key, making the brute force attacker repeat this work for each trial key. In practice, this technique can add 10 to 20 bits of strength to a password, enough to allow a reasonably memorable passphrase to be used, but not enough to secure the short passwords most people employ. Unfortunately, few security products incorporate KDF technology.

Perhaps the best solution is to store randomly-generated full-strength keys in a tamper resistant security token, internally protected by a password or PIN.

Asymmetric algorithms

The situation with regard to asymmetric key algorithms is more complicated and depends on the individual encryption algorithm. Thus, the currently breakable key length for the RSA algorithm is at least 512 bits (i.e., it has been done publicly), and recent research developments suggest that 1024 bits might be breakable in the near to medium term future. For most elliptic curve asymmetric algorithms, the largest currently breakable key length is believed to be rather shorter, perhaps as little as 128 bits or so. A message encrypted with a 109 bit key by an elliptic curve encryption algorithm was publicly broken by brute force key search in early 2003. At this writing (as of 2004), 128 bit key lengths seem the minimum reasonable for elliptic curve algorithms, and 1024 bits for such asymmetric key algorithms as RSA.

See also

• Cryptographic key length for a fuller discussion of recommended key sizes for symmetric and asymmetric algorithms.
• 40-bit encryption
• Distributed.net
• MD5CRK
• Unicity distance
• RSA numbers
• RSA Factoring Challenge

References

• Cracking DES — Secrets of Encryption Research, Wiretap Politics & Chip Design by the Electronic Frontier Foundation (ISBN 1565925203).
• W. Diffie and M.E. Hellman, Exhaustive cryptanalysis of the NBS Data Encryption Standard, Computer 10 (1977), pp74–84.
• Michael J. Wiener, "Efficient DES Key Search", presented at the rump session of Crypto 93; reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp31–79 (1996).

External links

• DES cracking contest (http://www.distributed.net/des/)