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 recognized, 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. By obfuscating the data to be encoded, brute force attacks are made less effective as it is more difficult to determine when one has succeeded in breaking the code.

Symmetric ciphers

For symmetric-key ciphers, a brute force attack typically means a brute-force 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⁶⁴ possible keys, a brute force attack would, on average, be expected to find a key after 2⁶³ trials.

For each trial of a candidate key the attacker needs to be able to recognize when he has found the correct key. The most straightforward way is to obtain a few corresponding plaintext and ciphertext pairs, that is, a known-plaintext attack. Alternatively, a ciphertext-only 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.



Symmetric ciphers with keys of length up to 64 bits have been broken by brute force attacks. DES, a widely-used block cipher which uses 56-bit keys, was broken by custom hardware in 1998 (see EFF DES cracker), and a message encrypted with RC5 using a 64-bit key was broken more recently by Distributed.net. More recently, the COPACOBANA (Cost-Optimized Parallel COde Breaker) was built, which is a reconfigurable code breaker that is suited for key searching of many different algorithms, including DES. In addition, it is commonly speculated that government intelligence agencies (such as the U.S. NSA) can successfully attack a symmetric key cipher with long key lengths, such as 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.

If keys are generated in a weak way, for example, derived from a guessable-password, it is possible to exhaustively search over a much smaller set, for example, keys generated from passwords in a dictionary. See password cracking and passphrase for more information.

Ciphers with proven perfect secrecy, such as the one-time pad, cannot be broken by a brute force attack.

Theoretical limits

The resources required for a brute force attack scale exponentially with increasing key size, not linearly. Doubling key size does not double the required number of operations, but rather squares the number of required operations. Thus, although 56 bit keys, such as those used by the obsolete Data Encryption Standard (DES) are now quite practical to attack by brute force, this is not true of much longer keys, such as those used by the more modern Advanced Encryption Standard (AES), which uses keys of at least 128 bits in length.

There is a physical argument that a 128 bit key is secure against brute force attack. The so-called Von Neumann-Landauer Limit implied by the laws of physics sets a lower limit on the energy required to perform a computation of per bit erased in a computation, where T is the temperature of the computing device in kelvin, k is the Boltzmann constant, and the natural logarithm of 2 is about .693. No irreversible computing device can use less energy than this, even in principle.

The amount of time required to break a 128 bit key is also daunting. Each of the possibilities must be checked. This is an enormous number, 340,282,366,920,938,463,463,374,607,431,768,211,456 in decimal. If a device could be built that could check a billion billion keys () per second, 10,790,283,070,806 (~) years would still be required to exhaust the key space. By way of comparison, the age of the universe is only about 13,000,000,000 () years.

(Although on average an attacker will find the key after searching only half the possible keys, this makes no practical difference given the time scales involved.)

AES permits the use of 256 bit keys. A 256 bit key requires not merely twice as long to crack as a 128 bit key, but rather times as long. If a device could be built that could check a billion billion () AES keys per second, it would require a staggering 3,671,743,063,080,802,746,815,416,825,491,118,336,290,905,145,409,708 () years to exhaust the 256 bit key space.

It should therefore be clear that, generally speaking, 128 bit keys are impractical to attack by brute force methods using current technology and resources, and that 256 bit keys are not likely to be broken by brute force methods using any obvious future technology.

Unbreakable codes

Certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is one-time pad cryptography, where every bit has a corresponding key bit. A brute force attack would eventually reveal the correct decoding, but also every other possible combination of bits, and would have no way of distinguishing one from the other.

For example, a small 100 byte one-time pad encoded string subjected to a brute force attack would eventually reveal every 100 byte string possible, including the correct answer, but mostly nonsense. Of all the answers given, there is no way of knowing which is the correct one.

Sample of breaking time

Here are some sample times of brute force code breaking, assuming the attacker can try 100000 keys per second, the key is not case sensitive, and all letters of the English alphabet and numerals are used.

Length	Possibilities	Time needed to break
1	36	0.0004 seconds
2	1296	0.01 seconds
3	46656	0.5 seconds
4	1679616	17 seconds
5	60466176	10 minutes
6	2176782336	6 hours
7	78364164096	9 days
8	2.8211099×1012	10 months
9	1.0155995×1014	32 years
10	3.6561584×1015	1,161 years
11	1.3162170×1017	41,822 years
12	4.7383813×1018	1,505,614 years

(information gets by Hacking Time Analizer)

See also

• Cryptographic key length for a fuller discussion of recommended key sizes for symmetric and asymmetric algorithms.
• TWINKLE and TWIRL
• 40-bit encryption
• Distributed.net
• MD5CRK
• Unicity distance
• 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 1-56592-520-3).
• 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 — a survey by Richard Clayton
• DES cracking contest
• www.keylength.com: An online keylength calculator
• The COPACOBANA (Cost-Optimized Parallel COde Breaker) reconfigurable code breaker
• phrel: A Linux utility to help prevent brute force attacks on FTP, DNS and other protocols.

Cryptographic hash functions and Message authentication codes (MACs)  •  • [ e]
Hash algorithms: Gost-Hash | HAS-160 | HAS-V | HAVAL | MDC-2 | MD2 | MD4 | MD5 | N-Hash | RadioGatn | RIPEMD | SHA family | Snefru | Tiger | VEST | WHIRLPOOL | crypt(3) DES
MAC algorithms: DAA | CBC-MAC | HMAC | OMAC/CMAC | PMAC | UMAC | Poly1305-AES | VEST
Authenticated encryption modes: CCM | CWC | EAX | GCM | OCB | VEST
Attacks: Hash collision | Birthday attack | Preimage attack | Rainbow table | Brute force attack
Standardization: CRYPTREC | NESSIE
Misc: Avalanche effect | Hash collision | Merkle-Damgrd construction
Cryptography  •  • [ e]
History of cryptography | Cryptanalysis | | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers

xxxx