Brute force attack

related topics
{math, number, function}
{system, computer, user}
{war, force, army}
{math, energy, light}
{law, state, case}

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.

Brute-force attacks are an application of brute-force search, the general problem-solving 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 56-bit symmetric keys (e.g. Data Encryption Standard), these restrictions are no longer in place, so modern algorithms typically use computationally stronger 128- to 256-bit keys.

There is a physical argument that a 128-bit symmetric key is computationally 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.[3] 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 theoretically require 2128 − 1 bit flips on a conventional processor. If it is assumed that the calculation occurs near room temperature (~300 K) the Von Neumann-Landauer Limit can be applied to estimate the energy required as ~1018 joules, which is equivalent to consuming 30 gigawatts of power for one year (30×109 W×365×24×3600 s = 9.46×1017 J). The full actual computation—checking each key to see if you have found a solution—would consume many times this amount.

Full article ▸

related documents
Befunge
Finite state machine
Selection sort
Fundamental theorem of arithmetic
Tensor
Binomial theorem
Delaunay triangulation
Affine transformation
Pell's equation
Greatest common divisor
Polish notation
Grover's algorithm
NP (complexity)
Empty set
Direct product
Net (mathematics)
Knapsack problem
Naive Bayes classifier
Brouwer fixed point theorem
Sheffer stroke
Graph theory
Scientific notation
Curve
Ordered pair
Partially ordered set
Cyclic group
Shell sort
Integer (computer science)
MathML
Normal space