Brute force attack

The EFF's US$250,000 DES cracking machine contained over 1,800 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.

In cryptography, a brute force attack is a strategy used to break the encryption of data. It involves traversing the search space of possible keys until the correct key is found.

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.

Theoretical limits

The resources required for a brute force attack scale exponentially with increasing key size, not linearly. As a result, doubling the key size for an algorithm does not simply double the required number of operations, but rather squares them. Although there are algorithms which use 56-bit symmetric keys (e.g. Data Encryption Standard), usually 128- to 256-bit keys are standard.

There is a physical argument that a 128-bit symmetric 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 ln(2)kT per bit erased in a computation, where T is the temperature of the computing device in kelvins, k is the Boltzmann constant, and the natural logarithm of 2 is about 0.693. No irreversible computing device can use less energy than this, even in principle.^[1]

Thus, in order to simply flip through the possible values for a 128-bit symmetric key (ignoring doing the actual computing to check it) would require 2¹²⁸ − 1 bit flips. If we assume that the calculation occurs near room temperature (~300 K) we can apply the Von Neumann-Landauer Limit to estimate the energy required as ~10¹⁸ joules, which is equivalent to consuming 30 gigawatts of power for one year (30×10⁹ W×365×24×3600 s = 9.46×10¹⁷ J). The full actual computation—checking each key to see if you have found a solution—would consume many times this amount.

However, this argument assumes that the register values are changed using conventional set and clear operations which inevitably generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction (see reversible computing), though no such computers are known to have been constructed.

The amount of time required to break a 128-bit key is also daunting. Each of the 2¹²⁸ (340,282,366,920,938,463,463,374,607,431,768,211,456) possibilities must be checked. A device that could check a billion billion keys (10¹⁸) per second would still require about 10¹³ years to exhaust the key space. This is a thousand times longer than the age of the universe, which is about 13,000,000,000 (1.3×10¹⁰) years.

AES permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2¹²⁸ times more computational power than a 128-bit key. A device that could check a billion billion (10¹⁸) AES keys per second would require about 3×10⁵¹ years to exhaust the 256-bit key space.

An underlying assumption of this analysis is that the complete keyspace is used to generate keys, something that relies on an effective random number generator. For example, a number of systems that were originally thought to be impossible to crack by brute force have nevertheless been cracked in this way because the key space to search through was found to be much smaller than originally thought, due to a lack of entropy in their pseudorandom number generators. These include Netscape's implementation of SSL (famously cracked by Ian Goldberg and David Wagner in 1995^[2]) and a Debian edition of OpenSSL discovered in 2008 to be flawed.^[3]

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 cleartext bit has a corresponding key bit. One-time pads rely on the ability to generate a truly random sequence of key bits. 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. 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. Nevertheless, the system can be defeated if not implemented correctly, for example if one-time pads are re-used.^[4]

See also

• Side-channel attack
• 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
• Custom hardware attack
• Dictionary attack

References

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations where appropriate. (November 2008)

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.
• WASC Threat Classification - Brute Force
• Hardware brute-force Oracle RDBMS password/hashes solver