 Bruteforce attack

In cryptography, a bruteforce attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data.^{[1]} 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 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 bruteforce attack, with longer keys exponentially more difficult to crack than shorter ones. Bruteforce 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/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 bruteforce 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 bruteforce attack grow 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 symmetric algorithms typically use computationally stronger 128 to 256bit keys. The table below illustrates how much more complex a 128bit key is than a 56bit key. If a device existed that could bruteforce a 56bit encryption key in one second, it would take that device 149.7 trillion years to bruteforce a 128bit encryption key.
Symmetric key length vs bruteforce combinations Key size in bits^{[2]} Permutations Bruteforce time for a device checking 2^{56} permutations per second 8 2^{8} 0 milliseconds 40 2^{40} 0.015 milliseconds 56 2^{56} 1 second 64 2^{64} 4 minutes 16 seconds 128 2^{128} 149,745,258,842,898 years 256 2^{256} 50,955,671,114,250,072,156,962,268,275,658,377,807,020,642,877,435,085 years There is also a physical argument that a 128bit symmetric key is computationally secure against bruteforce 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.
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]}
As commercial available successors of governmental ASICs Solution also known as custom hardware attack, today two emerging technologies have proven their capability in the bruteforce attack of certain ciphers. One is modern graphics processing unit (GPU) technology,^{[4]} the other is the fieldprogrammable gate array (FPGA) technology. GPUs benefit from their wide availability and priceperformance benefit, FPGAs from their energy efficiency per cryptographic operation. Both technologies try to transport the benefits of parallel processing to bruteforce 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 for certain algorithms. A number of firms provide hardwarebased 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 bruteforce attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs^{[5]}^{[6]} and some hundred in case of FPGAs.
AES permits the use of 256bit keys. Breaking a symmetric 256bit key by brute force requires 2^{128} times more computational power than a 128bit key. A device that could check a billion billion (10^{18}) AES keys per second (if such a device could ever be made) would in theory require about 3×10^{51} years to exhaust the 256bit key space. Quantum computers are needed to crack such complicated encryptions in a more practical length of time.
An underlying assumption of a bruteforce 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^{[7]}) and a Debian/Ubuntu edition of OpenSSL discovered in 2008 to be flawed.^{[8]} A similar lack of implemented entropy lead to the breaking of Enigma's code.^{[9]}^{[10]}
Credential recycling
Credential recycling refers to the hacking practice to reuse username and password combinations gathered in previous bruteforce attacks. A special form of credential recycling is Pass the hash.^{[11]}
Unbreakable codes
Certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is onetime pad cryptography, where every cleartext bit has a corresponding key bit. Onetime pads rely on the ability to generate a truly random sequence of key bits. A bruteforce 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, 100byte, onetimepad–encoded string subjected to a bruteforce attack would eventually reveal every 100byte 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 onetime pads are reused or intercepted.^{[12]}
A similar argument can apply when a *single* plaintext is encrypted by any method where the text is shorter than the key. For example, if the text is a single byte, then (for most types of encryption with large key sizes such as 128 bits) all bytes from "00""FF" will appear, with equal probability, as possible plaintexts corresponding to guessed keys.
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.^{[13]} Website administrators may prevent a particular IP address from trying more than a predetermined number of password attempts against any account on the site.^{[14]}
See also
 Cryptographic key length for a fuller discussion of recommended key sizes for symmetric and asymmetric algorithms.
 Distributed.net
 MD5CRK
 Metasploit Express for bruteforcing SMB, Postgres, DB2, MySQL, MSSQL, HTTP, SSH, Telnet & Tomcat
 Sidechannel attack
 TWINKLE and TWIRL
 Unicity distance
 RSA Factoring Challenge
 Bitcoin mining
References
 ^ Christof Paar, Jan Pelzl, Bart Preneel (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. p. 7. ISBN 3642041000. http://www.cryptotextbook.com.
 ^ Calculating Bit Strength
 ^ Rolf Landauer, "Irreversibility and heat generation in the computing process," IBM Journal of Research and Development, vol. 5, pp. 183191, 1961.
 ^ Robert David Grahamd (22 June 2011). "Password cracking, mining, and GPUs". erratasec.com. http://erratasec.blogspot.com/2011/06/passwordcrackingminingandgpus.html. Retrieved 17 August 2011.
 ^ Adrian KingsleyHughes (20081012). "ElcomSoft uses NVIDIA GPUs to Speed up WPA/WPA2 Bruteforce Attack". ZDNet. http://www.zdnet.com/blog/hardware/elcomsoftusesnvidiagpustospeedupwpawpa2bruteforceattack/2724.
 ^ Erik Kamerling (20071112). "Elcomsoft Debuts Graphics Processing Unit (GPU) Password Recovery Advancement". Symantec. http://www.symantec.com/connect/blogs/elcomsoftdebutsgraphicsprocessingunitgpupasswordrecoveryadvancement.
 ^ John Viega, Matt Messier, Pravir Chandra (2002). Network Security with OpenSSL. O'Reilly. p. 18. ISBN 059600270X. http://books.google.com/?id=FBYHEBTrZUwC. Retrieved 20081125.
 ^ "Technical Cyber Security Alert TA08137A: Debian/Ubuntu OpenSSL Random Number Generator Vulnerability". United States Computer Emergency Readiness Team. 20080516. http://www.uscert.gov/cas/techalerts/TA08137A.html. Retrieved 20080810.
 ^ Exploring the Enigma http://plus.maths.org/content/exploringenigma
 ^ NSA's How Mathematicians Helped Win WWII http://www.nsa.gov/about/cryptologic_heritage/center_crypt_history/publications/how_math_helped_win.shtml
 ^ Metasploit Express user guide
 ^ Robert Reynard (1997). Secret Code Breaker II: A Cryptanalyst's Handbook. Jacksonville, FL: Smith & Daniel Marketing. p. 86. ISBN 1889668060. http://books.google.com/?id=3nTmBW0ONEEC&pg=PA86. Retrieved 20080921.
 ^ Mark Burnett, James C. Foster (2004). Hacking the Code: ASP.NET Web Application Security. Syngress. ISBN 1932266658. http://books.google.com/books?id=WShG0uezvEC.
 ^ Ivan Ristic (2010). Modsecurity Handbook. Feisty Duck. p. 136. ISBN 1907117024. http://books.google.com/books?id=HnQl5OVtOYgC.
 Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis and Erik Winfree, On Applying Molecular Computation To The Data Encryption Standard, in Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton University, June 10–12, 1996.
 Cracking DES — Secrets of Encryption Research, Wiretap Politics & Chip Design by the Electronic Frontier Foundation (ISBN 1565925203).
 W. Diffie and M.E. Hellman, Exhaustive cryptanalysis of the NBS Data Encryption Standard, Computer 10 (1977), pp 74–84.
 Michael J. Wiener, "Efficient DES Key Search", presented at the rump session of Crypto 93; reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp 31–79 (1996).
External links
 How to Brute Force Attack and How to Prevent From it?
 Bruteforce attacks on cryptographic keys — a survey by Richard Clayton
 DES cracking contest
 www.keylength.com: An online keylength calculator
 The COPACOBANA (CostOptimized Parallel COde Breaker) reconfigurable code breaker
 phrel: A Linux utility to help prevent bruteforce attacks on FTP, DNS and other protocols.
 WASC Threat Classification  Brute Force
 What is Brute force attack
 How We Cracked the Code Book Ciphers  Essay by the winning team of the challenge in The Code Book
Cryptography Categories: Cryptographic attacks
Wikimedia Foundation. 2010.