Brute-force attack
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/Board300.jpg/260px-Board300.jpg)
In cryptography, a brute-force attack, or exhaustive key search, is a cryptanalytic attack that can, in theory, be used against any encrypted data[1] (except for data encrypted in an information-theoretically secure manner). Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system (if any exist) that would make the task easier. It consists of systematically checking all possible keys or passwords until the correct one is found. In the worst case, this would involve traversing the entire search space.
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 of the time a brute-force search takes.
When key guessing, the key length used in the cipher determines the practical feasibility of performing a brute-force attack, with longer keys exponentially more difficult to crack than shorter ones. A cipher with a key length of N bits can be broken in a worst-case time proportional to 2N and an average time of half that.
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 recognize when he/she 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.
Theoretical limits
The resources required for a brute-force attack grow exponentially with increasing key size, not linearly. 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 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 so-called Landauer limit implied by the laws of physics sets a lower limit on the energy required to perform a computation of kT · ln 2 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.[2] 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. This is equal to 30×109 W×365×24×3600 s = 9.46×1017 J or 262.7 TWh (more than 1/100th of the world energy production).[citation needed] 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.[citation needed]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/ATI_Radeon_HD_5770_Graphics_Card-oblique_view.jpg/220px-ATI_Radeon_HD_5770_Graphics_Card-oblique_view.jpg)
As commercial available successors of governmental ASICs Solution also known as custom hardware attack, today two emerging technologies have proven their capability in the brute-force attack of certain ciphers. One is modern graphics processing unit (GPU) technology,[3][page needed] the other is the field-programmable gate array (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, the COPACOBANA FPGA 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 card up to dedicated FPGA computers.[citation needed] WPA and WPA2 encryption have successfully been brute-force attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs[4][5] and some hundred in case of FPGAs.
![](http://upload.wikimedia.org/wikipedia/en/thumb/2/26/COPACOBANA_FPGA_BOARD.jpg/240px-COPACOBANA_FPGA_BOARD.jpg)
AES permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2128 times more computational power than a 128-bit key. 50 supercomputers that could check a billion billion (1018) AES keys per second (if such a device could ever be made) would, in theory, require about 3×1051 years to exhaust the 256-bit key space.
An underlying assumption of a brute-force attack is that the complete keyspace 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 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 generators. These include Netscape's implementation of SSL (famously cracked by Ian Goldberg and David Wagner in 1995[6]) and a Debian/Ubuntu edition of OpenSSL discovered in 2008 to be flawed.[7] A similar lack of implemented entropy led to the breaking of Enigma's code.[8][9]
Credential recycling
Credential recycling refers to the hacking practice to re-use 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 cryptography, where every cleartext 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, 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.[10]
Countermeasures
In case of an offline attack where the attacker has access to the encrypted material, he can try key combinations at his leisure without the risk of discovery or interference. However database and directory administrators can take countermeasures against online attacks, for example by limiting the number of attempts that a password can be tried, by introducing time delays between successive attempts, increasing the answer's complexity (e.g. requiring a CAPTCHA answer or verification code sent via cellphone), and/or locking accounts out after unsuccessful logon attempts.[11][page needed] Website administrators may prevent a particular IP address from trying more than a predetermined number of password attempts against any account on the site.[12]
Reverse brute-force attack
In a reverse brute-force attack, a single (usually common) password is tested against multiple usernames or encrypted files.[13] The process may be repeated for a select few passwords. In such a strategy, the attacker is generally not targeting a specific user. Reverse brute-force attacks can be mitigated by establishing a password policy that disallows common passwords.[citation needed]
See also
- Cryptographic key length for a fuller discussion of recommended key sizes for symmetric and asymmetric algorithms.
- Distributed.net
- MD5CRK
- Metasploit Express for brute-forcing SMB, Postgres, DB2, MySQL, MSSQL, HTTP, SSH, Telnet & Tomcat
- Side-channel attack
- TWINKLE and TWIRL
- Unicity distance
- RSA Factoring Challenge
- Bitcoin mining
Notes
- ^ Paar 2010, p. 7.
- ^ Landauer 1961, p. 183-191.
- ^ Graham 2011.
- ^ Kingsley-Hughes 2008.
- ^ Kamerling 2007.
- ^ Viega 2002, p. 18.
- ^ CERT-2008.
- ^ Ellis.
- ^ NSA-2009.
- ^ Reynard 1997, p. 86.
- ^ Burnett 2004.
- ^ Ristic 2010, p. 136.
- ^ http://www.infosecpro.com/applicationsecurity/a11.htm
References
- Adleman, Leonard M.; Rothemund, Paul W.K.; Roweis, Sam; Winfree, Erik (June 10–12). On Applying Molecular Computation To The Data Encryption Standard. Proceedings of the Second Annual Meeting on DNA Based Computers. Princeton University.
{{cite conference}}
: Check date values in:|date=
and|year=
/|date=
mismatch (help); Invalid|ref=harv
(help) - Cracking DES – Secrets of Encryption Research, Wiretap Politics & Chip Design. Electronic Frontier Foundation. ISBN 1-56592-520-3.
{{cite book}}
: Invalid|ref=harv
(help) - Burnett, Mark; Foster, James C. (2004). Hacking the Code: ASP.NET Web Application Security. Syngress. ISBN 1-932266-65-8.
{{cite book}}
: Invalid|ref=harv
(help) - Diffie, W.; Hellman, M.E. (1977). "Exhaustive Cryptanalysis of the NBS Data Encryption Standard". Computer. 10.
{{cite journal}}
: Invalid|ref=harv
(help) - Graham, Robert David (22 June 2011). "Password cracking, mining, and GPUs". erratasec.com. Retrieved 17 August 2011.
{{cite web}}
: Invalid|ref=harv
(help) - Ellis, Claire. "Exploring the Enigma". Plus Magazine.
{{cite web}}
: Invalid|ref=harv
(help) - Kamerling, Erik (2007-11-12). "Elcomsoft Debuts Graphics Processing Unit (GPU) Password Recovery Advancement". Symantec.
{{cite web}}
: Invalid|ref=harv
(help) - Kingsley-Hughes, Adrian (2008-10-12). "ElcomSoft uses NVIDIA GPUs to Speed up WPA/WPA2 Brute-force Attack". ZDNet.
{{cite news}}
: Invalid|ref=harv
(help) - Landauer, L (1961). "Irreversibility and Heat Generation in the Computing Process". IBM Journal of Research and Development. 5.
{{cite journal}}
: Invalid|ref=harv
(help) - Paar, Christof; Pelzl, Jan; Preneel, Bart (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. ISBN 3-642-04100-0.
{{cite book}}
: Invalid|ref=harv
(help) - Reynard, Robert (1997). Secret Code Breaker II: A Cryptanalyst's Handbook. Jacksonville, FL: Smith & Daniel Marketing. ISBN 1-889668-06-0. Retrieved 2008-09-21.
{{cite book}}
: Invalid|ref=harv
(help) - Ristic, Ivan (2010). Modsecurity Handbook. Feisty Duck. ISBN 1-907117-02-4.
{{cite book}}
: Invalid|ref=harv
(help) - Viega, John; Messier, Matt; Chandra, Pravir (2002). Network Security with OpenSSL. O'Reilly. ISBN 0-596-00270-X. Retrieved 2008-11-25.
{{cite book}}
: Invalid|ref=harv
(help) - Wiener, Michael J. (1996). "Crypto 93". Practical Cryptography for Data Internetworks. W. Stallings, editor, IEEE Computer Society Press.
{{cite journal}}
: Invalid|ref=harv
(help) - "Technical Cyber Security Alert TA08-137A: Debian/Ubuntu OpenSSL Random Number Generator Vulnerability". United States Computer Emergency Readiness Team (CERT). 2008-05-16. Retrieved 2008-08-10.
- "NSA's How Mathematicians Helped Win WWII". National Security Agency. 15 Jan 2009.
External links
- Basic idea on How Password Bruteforce Tool is Created
- RSA-sponsored DES-III cracking contest
- How We Cracked the Code Book Ciphers – Essay by the winning team of the challenge in The Code Book
- Why not use larger cipher keys?