Brute force attack

Board300.jpg
In cryptanalysis, a brute force attack is a method of defeating a cryptographic scheme by trying a large number of possibilities; for example, exhaustively working through all possible keys in order to decrypt a message. In most schemes, the theoretical possibility of a brute force attack is recognised, but it is set up in such a way that it would be computationally infeasible to carry out. Accordingly, one definition of "breaking" a cryptographic scheme is to find a method faster than a brute force attack.
The selection of an appropriate key length depends on the practical feasibility of performing a brute force attack.
Contents 
Symmetric ciphers
For symmetrickey ciphers, a brute force attack typically means a bruteforce search of the key space; that is, testing all possible keys in order to recover the plaintext used to produce a particular ciphertext.
In a brute force attack, the expected number of trials before the correct key is found is equal to half the size of the key space. For example, if there are 2^{64} possible keys, a brute force attack would, on average, be expected to find a key after 2^{63} trials.
For each trial of a candidate key the attacker needs to be able to recognise when he has found the correct key. The most straightforward way is to obtain a few corresponding plaintext and ciphertext pairs, that is, a knownplaintext attack. Alternatively, a ciphertextonly attack is possible by decrypting ciphertext using each candidate key, and testing the result for similarity to plaintext language — for example, English encoded in ASCII.
In general, a symmetric key cipher is considered secure if there is no method less expensive (in time, memory requirements, 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.
Symmetric ciphers with keys of length up to 64 bits have been broken by brute force attacks. DES, a widelyused block cipher which uses 56bit keys, was broken by custom hardware in 1998 (see EFF DES cracker), and a message encrypted with RC5 using a 64bit key was broken more recently by Distributed.net. In addition, it is commonly speculated that government intelligence agencies (such as the US NSA) can successfully attack a symmetric key cipher with long key lengths, such as a 64bit 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 80bit designs be phased out by 2015.
If keys are generated in a weak way, for example, derived from a guessablepassword, it is be possible to exhaustively search over a much smaller set, for example, keys generated from passwords in a dictionary. See password cracking for more information.
Asymmetric algorithms
For asymmetric cryptography, a brute force attack usually involves tackling some difficult problem, such as large integer factorisation or calculating a discrete logarithm.
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.
Theoretical limits
It is relatively easy to demonstrate that a 128 bit key is secure against brute force attack. In order to merely step through all 2^{128} values, one must dissipate 128 bits of entropy at each step. This is a total of 2^{128} * 2^{7}= 2^{135} bits.
Using 2^{10} ≈ 10^3, this comes to about 10^{40} bits of entropy. Multiplying this by the Boltzmann constant (1.38 * 10^{23}) and by the natural log of 2 (0.69), one arrives at just about 10^{17} J/k . At room temperature (let's call it 300K), that's very roughly about 3*10^{19} Joules which must be dissipated as heat, simply to flick through the possible 2^128 combinations.
To accomplish this in 100 years  3*10^{9} seconds, one would have to dissipate it at a rate of 10^{10} watts.
In other words: to simply flip through the possible values for a 128bit key (never mind actually doing the computing to check it), one would need a device consuming at an absolute minimum 10 gigawatts running continuously for 100 years. An actual computation  checking each key to see if you have found a solution  would consume many multiples more.
For a 56bit key, the numbers are a trifle more sane  the total minimum amount of energy comes to about 1/100 Joules.
See also
 Cryptographic key length for a fuller discussion of recommended key sizes for symmetric and asymmetric algorithms.
 TWINKLE and TWIRL
 40bit encryption
 Distributed.net
 MD5CRK
 Unicity distance
 RSA numbers
 RSA Factoring Challenge
References
 Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis and Erik Winfree, On Applying Molecular Computation To The Data Encryption Standard, in Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton University, June 10–12, 1996.
 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
 Brute force attacks on cryptographic keys (http://www.cl.cam.ac.uk/users/rnc1/brute.html) — a survey by Richard Clayton
 DES cracking contest (http://www.distributed.net/des/)de:Brute force attack