In cryptography, a brute force attack or exhaustive key search is a strategy that can in theory be used against any encrypted data^{[1]} by an attacker who is unable to take advantage of any weakness in an encryption system that would otherwise make his task easier. It involves systematically checking all possible keys until the correct key is found. In the worst case, this would involve traversing the entire search space.
The key length used in the encryption determines the practical feasibility of performing a brute force attack, with longer keys exponentially more difficult to crack than shorter ones. Brute force attacks can be made less effective by obfuscating the data to be encoded, something that makes it more difficult for an attacker to recognise when he has cracked the code. One of the measures of the strength of an encryption system is how long it would theoretically take an attacker to mount a successful brute force attack against it.
Bruteforce attacks are an application of bruteforce search, the general problemsolving technique of enumerating all candidates and checking each one.
Contents
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 US export regulations historically restricted key lengths to 56bit symmetric keys (e.g. Data Encryption Standard), these restrictions are no longer in place, so modern algorithms typically use computationally stronger 128 to 256bit keys.
There is a physical argument that a 128bit symmetric key is computationally secure against brute force attack. The socalled Von NeumannLandauer 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.^{[3]} Thus, in order to simply flip through the possible values for a 128bit symmetric key (ignoring doing the actual computing to check it) would theoretically require 2^{128} − 1 bit flips on a conventional processor. If it is assumed that the calculation occurs near room temperature (~300 K) the Von NeumannLandauer Limit can be applied to estimate the energy required as ~10^{18} joules, which is equivalent to consuming 30 gigawatts of power for one year (30×10^{9} W×365×24×3600 s = 9.46×10^{17} J). The full actual computation—checking each key to see if you have found a solution—would consume many times this amount.
Full article ▸
