In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
, a brute-force attack consists of an attacker submitting many
password
A password, sometimes called a passcode (for example in Apple devices), is secret data, typically a string of characters, usually used to confirm a user's identity. Traditionally, passwords were expected to be memorized, but the large number of ...
s or
passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the
key which is typically created from the password using a
key derivation function
In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function (which typically uses a cry ...
. This is known as an exhaustive key search.
A brute-force attack is a
cryptanalytic attack
Cryptanalysis (from the Greek language, Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach C ...
that can, in theory, be used to attempt to decrypt any encrypted data (except for data encrypted in an
information-theoretically secure manner). Such an attack might be used when it is not possible to take advantage of other weaknesses in an encryption system (if any exist) that would make the task easier.
When password-guessing, this method is very fast when used to check all short passwords, but for longer passwords other methods such as the
dictionary attack are used because a brute-force search takes too long. Longer passwords, passphrases and keys have more possible values, making them exponentially more difficult to crack than shorter ones.
Brute-force attacks can be made less effective by
obfuscating the data to be encoded making it more difficult for an attacker to recognize when the code has been cracked or by making the attacker do more work to test each guess. 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. The word 'hammering' is sometimes used to describe a brute-force attack, with 'anti-hammering' for countermeasures.
Basic concept
Brute-force attacks work by calculating every possible combination that could make up a password and testing it to see if it is the correct password. As the password's length increases, the amount of time, on average, to find the correct password increases exponentially.
Theoretical limits
The resources required for a brute-force attack grow
exponentially with increasing
key size, not linearly. Although U.S. export regulations historically restricted key lengths to 56-bit
symmetric keys (e.g.
Data Encryption Standard
The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cry ...
), these restrictions are no longer in place, so modern symmetric 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
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
The kelvin, symbol K, is the primary unit of temperature in the International System of Units (SI), used alongside its prefixed forms and the degree Celsius. It is named after the Belfast-born and University of Glasgow-based engineer and ...
s, ''k'' is the
Boltzmann constant
The Boltzmann constant ( or ) is the proportionality factor that relates the average relative kinetic energy of particles in a gas with the thermodynamic temperature of the gas. It occurs in the definitions of the kelvin and the gas constan ...
, and the
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
of 2 is about 0.693 (0.6931471805599453). No irreversible computing device can use less energy than this, even in principle. 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 ''2
128 − 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 ≈10
18 joule
The joule ( , ; symbol: J) is the unit of energy in the International System of Units (SI). It is equal to the amount of work done when a force of 1 newton displaces a mass through a distance of 1 metre in the direction of the force appli ...
s, which is equivalent to consuming 30
gigawatts of power for one year. This is equal to 30×10
9 W×365×24×3600 s = 9.46×10
17 J or 262.7 TWh (about 0.1% of the
yearly world energy production). The full actual computation – checking each key to see if a solution has been found – would consume many times this amount. Furthermore, this is simply the energy requirement for cycling through the key space; the actual time it takes to flip each bit is not considered, which is certainly greater than 0 (see
Bremermann's limit).
However, this argument assumes that the register values are changed using conventional set and clear operations which inevitably generate
entropy
Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodyna ...
. 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.
As commercial successors of governmental
ASIC
An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficie ...
solutions have become available, also known as
custom hardware attacks, two emerging technologies have proven their capability in the brute-force attack of certain ciphers. One is modern
graphics processing unit
A graphics processing unit (GPU) is a specialized electronic circuit designed to manipulate and alter memory to accelerate the creation of images in a frame buffer intended for output to a display device. GPUs are used in embedded systems, m ...
(GPU) technology, the other is the
field-programmable gate array
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term ''Field-programmability, field-programmable''. The FPGA configuration is generally specifi ...
(FPGA) technology. GPUs benefit from their wide availability and price-performance benefit, FPGAs from their energy efficiency per cryptographic operation. Both technologies try to transport the benefits of parallel processing to brute-force attacks. In case of GPUs some hundreds, in the case of FPGA some thousand processing units making them much better suited to cracking passwords than conventional processors.
Various publications in the fields of cryptographic analysis have proved the energy efficiency of today's FPGA technology, for example, th
COPACOBANAFPGA Cluster computer consumes the same energy as a single PC (600 W), but performs like 2,500 PCs for certain algorithms. A number of firms provide hardware-based FPGA cryptographic analysis solutions from a single FPGA
PCI Express
PCI Express (Peripheral Component Interconnect Express), officially abbreviated as PCIe or PCI-e, is a high-speed serial computer expansion bus standard, designed to replace the older PCI, PCI-X and AGP bus standards. It is the common ...
card up to dedicated FPGA computers.
WPA and
WPA2 encryption have successfully been brute-force attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs and some hundred in case of FPGAs.
Advanced Encryption Standard
The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
AES is a variant ...
(AES) permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2
128 times more computational power than a 128-bit key. One of the fastest supercomputers in 2019 has a speed of 100
petaFLOPS which could theoretically check 100 million million (10
14) AES keys per second (assuming 1000 operations per check), but would still require 3.67×10
55 years to exhaust the 256-bit key space.
An underlying assumption of a brute-force attack is that the complete key space was used to generate keys, something that relies on an effective
random number generator, and that there are no defects in the algorithm or its implementation. For example, a number of systems that were originally thought to be impossible to crack by brute force have nevertheless been
cracked
Cracked may refer to: Television
* ''Cracked'' (British TV series), a 2008 British comedy-drama television series that aired on STV
* ''Cracked'' (Canadian TV series), a 2013 Canadian crime drama series that aired on CBC
* "Cracked", a Season 8 ( ...
because the
key space to search through was found to be much smaller than originally thought, because of a lack of entropy in their
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
s. These include
Netscape
Netscape Communications Corporation (originally Mosaic Communications Corporation) was an American independent computer services company with headquarters in Mountain View, California and then Dulles, Virginia. Its Netscape web browser was on ...
's implementation of
SSL SSL may refer to:
Entertainment
* RoboCup Small Size League, robotics football competition
* ''Sesame Street Live'', a touring version of the children's television show
* StarCraft II StarLeague, a Korean league in the video game
Natural language ...
(famously cracked by
Ian Goldberg
Ian Avrum Goldberg (born March 31, 1973) is a cryptographer and cypherpunk. He is best known for breaking Netscape's implementation of SSL (with David Wagner),
and for his role as chief scientist of Radialpoint (formerly Zero Knowledge Syst ...
and
David Wagner in 1995) and a
Debian
Debian (), also known as Debian GNU/Linux, is a Linux distribution composed of free and open-source software, developed by the community-supported Debian Project, which was established by Ian Murdock on August 16, 1993. The first version of De ...
/
Ubuntu
Ubuntu ( ) is a Linux distribution based on Debian and composed mostly of free and open-source software. Ubuntu is officially released in three editions: '' Desktop'', ''Server'', and ''Core'' for Internet of things devices and robots. All ...
edition of
OpenSSL
OpenSSL is a software library for applications that provide secure communications over computer networks against eavesdropping or need to identify the party at the other end. It is widely used by Internet servers, including the majority of HT ...
discovered in 2008 to be flawed. A similar lack of implemented entropy led to the breaking of
Enigma's code.
Credential recycling
Credential recycling refers to the
hacking practice of re-using username and password combinations gathered in previous brute-force attacks. A special form of credential recycling is
pass the hash, where
unsalted hashed credentials are stolen and re-used without first being brute forced.
Unbreakable codes
Certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is
one-time pad
In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ra ...
cryptography, where every
cleartext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of co ...
bit has a corresponding key from a truly random sequence of key bits. A 140 character one-time-pad-encoded string subjected to a brute-force attack would eventually reveal every 140 character string possible, including the correct answer – but of all the answers given, there would be no way of knowing which was the correct one. Defeating such a system, as was done by the
Venona project
The Venona project was a United States counterintelligence program initiated during World War II by the United States Army's Signal Intelligence Service (later absorbed by the National Security Agency), which ran from February 1, 1943, until Oc ...
, generally relies not on pure cryptography, but upon mistakes in its implementation: the key pads not being truly random, intercepted keypads, operators making mistakes – or other errors.
Countermeasures
In case of an ''offline'' attack where the attacker has gained access to the encrypted material, one can try key combinations without the risk of discovery or interference. In case of ''online'' attacks, database and directory administrators can deploy countermeasures such as limiting the number of attempts that a password can be tried, introducing time delays between successive attempts, increasing the answer's complexity (e.g., requiring a
CAPTCHA answer or employing
multi-factor authentication
Multi-factor authentication (MFA; encompassing two-factor authentication, or 2FA, along with similar terms) is an electronic authentication method in which a user is granted access to a website or application only after successfully presenting ...
), and/or locking accounts out after unsuccessful login attempts. Website administrators may prevent a particular IP address from trying more than a predetermined number of password attempts against any account on the site.
Reverse brute-force attack
In a reverse brute-force attack, a single (usually common) password is tested against multiple usernames or encrypted files.
The process may be repeated for a select few passwords. In such a strategy, the attacker is not targeting a specific user.
See also
*
Bitcoin mining
*
Cryptographic key length
*
Distributed.net
*
Key derivation function
In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function (which typically uses a cry ...
*
MD5CRK
*
Metasploit Express
*
Side-channel attack
*
TWINKLE and
TWIRL
In cryptography and number theory, TWIRL (The Weizmann Institute Relation Locator) is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization algorithm. During the sieving step ...
*
Unicity distance
*
RSA Factoring Challenge
*
Secure Shell
The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH applications are based ...
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
RSA-sponsored DES-III cracking contestDemonstration of a brute-force devicedesigned to guess the passcode of locked
iPhones running
iOS 10.3.3How We Cracked the Code Book Ciphers– Essay by the winning team of the challenge in
The Code Book
''The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography'' is a book by Simon Singh, published in 1999 by Fourth Estate and Doubleday.
''The Code Book'' describes some illustrative highlights in the history of crypto ...
{{DEFAULTSORT:Brute-force attack
Cryptographic attacks