Editing Brute-force attack

{{Short description|Cryptanalytic method for unauthorized users to access data}}
{{Use mdy dates|date = March 2019}}
{{About|the cryptanalytic method|similarly named methods in other disciplines|Brute force (disambiguation){{!}}Brute force}}
In [[cryptography]], a '''brute-force attack''' or '''exhaustive key search''' is a [[cryptanalytic attack]] that consists of an attacker submitting many possible [[Key (cryptography)|key]]s or [[password]]s with the hope of eventually guessing correctly. This strategy can theoretically be used to break any form of encryption that is not [[information-theoretically secure]].{{sfn|Paar|Pelzl|Preneel|2010|p=7}}  However, in a properly designed cryptosystem the chance of successfully guessing the key is negligible.

When [[Password cracking|cracking passwords]], 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 due to diversity of characters.<ref>{{Cite news|last=Urbina|first=Ian|date=2014|title=The Secret Life of Passwords. The New Times.|newspaper=The New York Times|url=https://www.nytimes.com/2014/11/19/magazine/the-secret-life-of-passwords.html|access-date=|website=}}</ref>

Brute-force attacks can be made less effective by [[Obfuscation (software)|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.<ref>{{Citation|last1=Schrittwieser|first1=Sebastian|title=Code Obfuscation against Static and Dynamic Reverse Engineering|date=2011|url=http://dx.doi.org/10.1007/978-3-642-24178-9_19|work=Information Hiding|pages=270–284|place=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|access-date=2021-09-05|last2=Katzenbeisser|first2=Stefan|series=Lecture Notes in Computer Science|volume=6958|doi=10.1007/978-3-642-24178-9_19|isbn=978-3-642-24177-2|url-access=subscription}}</ref>

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,<ref>{{cite web |title=Secure your site from Brute force attacks using Sebsoft's Anti Hammering Authentication Plugin #MoodlePlugins #MoodleSecurity |url=https://www.elearnmagazine.com/technology/secure-your-site-from-brute-force-attacks-using-sebsofts-anti-hammering-authentication-plugin-moodleplugins-moodlesecurity/ |website=elearnmagazine.com |date=January 16, 2016 |publisher=e Learn Magazine |access-date=27 October 2022}}</ref> with 'anti-hammering' for countermeasures.<ref>{{cite web |title=Configure Serv-U to protect against brute force attacks |url=https://support.solarwinds.com/SuccessCenter/s/article/Configure-Serv-U-to-protect-against-brute-force-attacks?language=en_US |website=solarwinds.com |publisher=Solar Winds |access-date=27 October 2022}}</ref>

==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.<ref>{{Cite web|date=2020-10-20|title=Brute Force Attack: Definition and Examples|url=https://www.kaspersky.com/resource-center/definitions/brute-force-attack|access-date=2020-11-08|website=www.kaspersky.com|language=en}}</ref>

==Theoretical limits==
[[File:Board300.jpg|thumb|The 1998 [[Electronic Frontier Foundation]]'s US$250,000 [[Data Encryption Standard|DES]] [[EFF DES cracker|cracking machine]] contained over 1,800 custom chips and could brute-force a DES key in a matter of days. The photograph shows a DES Cracker circuit board fitted with 64 Deep Crack chips using both sides.|252x252px]]The resources required for a brute-force attack grow [[exponential growth|exponentially]] with increasing [[key size]], not linearly. Although U.S. export regulations historically restricted key lengths to 56-bit [[symmetric key]]s (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 [[Landauer limit]] implied by the laws of physics sets a lower limit on the energy required to perform a computation of {{math|''kT'' {{middot}} ln 2}} per bit erased in a computation, where ''T'' is the temperature of the computing device in [[kelvin]]s, ''k'' is the [[Boltzmann constant]], and the [[natural logarithm]] of 2 is about 0.693 (0.6931471805599453). No irreversible computing device can use less energy than this, even in principle.{{sfn|Landauer|1961|p=183-191}}  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<sup>128</sup> − 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<sup>18</sup> [[joule]]s, which is equivalent to consuming 30 [[Orders of magnitude (power)#gigawatt (109 watts)|gigawatts]] of power for one year. This is equal to 30×10<sup>9</sup> W×365×24×3600 s = 9.46×10<sup>17</sup> J or 262.7 TWh (about 0.1% of the [[World energy supply and consumption|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]]).{{Citation needed|date=September 2010}}

However, this argument assumes that the register values are changed using conventional set and clear operations, which inevitably generate [[Entropy (computing)|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|date=September 2010}}

[[File:ATI Radeon HD 5770 Graphics Card-oblique view.jpg|thumb|left|Modern [[Graphics processing unit|GPUs]] are well-suited to the repetitive tasks associated with hardware-based password cracking.]] 
As commercial successors of governmental [[ASIC]] solutions have become available, also known as [[custom hardware attack]]s,  two emerging technologies have proven their capability in the brute-force attack of certain ciphers. One is modern [[graphics processing unit]] (GPU) technology,{{sfn|Graham|2011|p=}}{{page needed|date=March 2012}} the other is the [[field-programmable gate array]] (FPGA) technology.  GPUs benefit from their wide availability and price-performance benefit, FPGAs from their [[Efficient energy use|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. For instance in 2022, 8 [[GeForce 40 series| Nvidia RTX 4090]] GPU were linked together to test password strength by using the software [[Hashcat]] with results that showed 200 billion eight-character [[NTLM]] password combinations could be cycled through in 48 minutes.<ref name=BFA_2>{{cite web| title=Password-cracking With High-Performance GPUs: Is There a Way to Prevent It?| author=Rudisail, B.| url=https://www.spiceworks.com/it-security/identity-access-management/articles/tackling-gpu-enabled-password-cracking| publisher=Spiceworks| date=17 November 2022| access-date=24 December 2023}}</ref><ref name=BFA_3>{{cite web| title=Eight RTX 4090s Can Break Passwords in Under an Hour| author=Pires, F.| url=https://www.tomshardware.com/news/eight-rtx-4090s-can-break-passwords-in-under-an-hour| publisher=Future Publishing| date=18 October 2022| access-date=25 December 2023}}</ref>

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&nbsp;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|date=November 2010}}  [[Wi-Fi Protected Access|WPA]] and [[WPA2]] encryption have successfully been brute-force attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs{{sfn|Kingsley-Hughes|2008}}{{sfn|Kamerling|2007}} and some hundred in case of FPGAs.
[[File:COPACOBANA FPGA BOARD.jpg|thumb|A single COPACOBANA board boasting 6 Xilinx Spartans – a cluster is made up of 20 of these.]]

[[Advanced Encryption Standard]] (AES) permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute-force requires 2<sup>128</sup> 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 trillion (10<sup>14</sup>) AES keys per second (assuming 1000 operations per check), but would still require 3.67×10<sup>55</sup> years to exhaust the 256-bit key space.<ref>{{Cite web|title=November 2019 {{!}} TOP500 Supercomputer Sites|url=https://www.top500.org/lists/2019/11/|website=www.top500.org|access-date=2020-05-15|archive-url=https://web.archive.org/web/20191119085945/https://www.top500.org/lists/2019/11/|archive-date=November 19, 2019|url-status=dead}}</ref> 

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 generation|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 [[Random number generator attack|cracked]] because the [[key space (cryptography)|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]]s. These include [[Netscape]]'s implementation of [[Secure Sockets Layer]] (SSL) (cracked by [[Ian Goldberg]] and [[David A. Wagner|David Wagner]] in 1995) and a [[Debian]]/[[Ubuntu (operating system)|Ubuntu]] edition of [[OpenSSL]] discovered in 2008 to be flawed.{{sfn|Viega|Messier|Chandra|2002|p=18}}{{sfn|CERT-2008}}  A similar lack of implemented entropy led to the breaking of [[Enigma machine|Enigma's]] code.{{sfn|Ellis|2005}}{{sfn|NSA-2009}}

==Credential recycling==
Credential recycling is the [[Hacker (computer security)|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 [[Salt (cryptography)|unsalted]] hashed credentials are stolen and re-used without first being brute-forced.<ref name="n580">{{cite web | title=What is a Pass-the-Hash Attack (PtH)? | website=BeyondTrust | date=2023-08-04 | url=https://www.beyondtrust.com/resources/glossary/pass-the-hash-pth-attack | access-date=2024-06-23 | archiveurl = https://web.archive.org/web/20240515111754/https://www.beyondtrust.com/resources/glossary/pass-the-hash-pth-attack | archivedate = 2024-05-15 | url-status = live}}</ref>

==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, such as the key pads not being truly random, intercepted keypads, or operators making mistakes.{{sfn|Reynard|1997|p=86}}

==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]]), and/or locking accounts out after unsuccessful login attempts.{{sfn|Burnett|Foster|2004|p=}}{{page needed|date=March 2012}}  Website administrators may prevent a particular IP address from trying more than a predetermined number of password attempts against any account on the site.{{sfn|Ristic|2010|p=136}} Additionally, the MITRE D3FEND framework provides structured recommendations for defending against brute-force attacks by implementing strategies such as network traffic filtering, deploying decoy credentials, and invalidating authentication caches.<ref>{{Cite web |title=Implementing MITRE D3FEND for ATT&CK Technique T1110: Brute Force
 |url=https://d3security.com/blog/implementing-mitre-d3fend-for-attck-technique-t1110-brute-force/ |access-date=2024-06-19 |website=D3 Security |date=August 25, 2023 |language=en}}</ref>

==Reverse brute-force attack==
In a reverse brute-force attack (also called password spraying), a single (usually common) password is tested against multiple usernames or encrypted files.<ref>{{cite web|url=http://www.infosecpro.com/applicationsecurity/a11.htm|title=InfoSecPro.com - Computer, network, application and physical security consultants.|website=www.infosecpro.com|access-date=8 May 2018|url-status=live|archive-url=https://web.archive.org/web/20170404153951/http://www.infosecpro.com/applicationsecurity/a11.htm|archive-date=4 April 2017}}</ref> 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]]
* [[Hail Mary Cloud]]
* [[Key derivation function]]
* [[MD5CRK]]
* [[Metasploit Project|Metasploit Express]]
* [[Side-channel attack]]
* [[TWINKLE]] and [[TWIRL]]
* [[Unicity distance]]
* [[RSA Factoring Challenge]]
* [[Secure Shell]]

==Notes==
{{Reflist}}

==References==
{{Refbegin}}
* {{cite conference|last1=Adleman|first1=Leonard M.|author-link=Leonard M. Adleman |last2=Rothemund|first2=Paul W.K.|author-link2=Paul W. K. Rothemund|last3=Roweis|first3=Sam|author-link3=Sam Roweis|last4=Winfree|first4=Erik|author-link4=Erik Winfree|title=On Applying Molecular Computation To The Data Encryption Standard|journal=Proceedings of the Second Annual Meeting on DNA Based Computers|publisher=[[Princeton University]]|date=June 10–12, 1996}}
* {{cite book|title=Cracking DES – Secrets of Encryption Research, Wiretap Politics & Chip Design|year=1998|publisher=[[Electronic Frontier Foundation]]|isbn=1-56592-520-3|url-access=registration|url=https://archive.org/details/crackingdes00elec}}
*{{cite book|last1=Burnett|first1=Mark|first2=James C.|last2=Foster|url=https://books.google.com/books?id=-WShG0uezvEC|title=Hacking the Code: ASP.NET Web Application Security|publisher=Syngress|year=2004|isbn=1-932266-65-8}}
* {{cite journal|last1=Diffie|first1=W.|last2=Hellman|first2=M.E.|title=Exhaustive Cryptanalysis of the NBS Data Encryption Standard|journal=Computer|volume=10|year=1977|doi=10.1109/c-m.1977.217750|pages=74–84|s2cid=2412454}}
*{{cite web|last=Graham|first=Robert David|title=Password cracking, mining, and GPUs|date=22 June 2011|access-date=17 August 2011|publisher=erratasec.com|url=http://erratasec.blogspot.com/2011/06/password-cracking-mining-and-gpus.html}}
*{{cite web|last=Ellis|first=Claire|title=Exploring the Enigma|date=March 2005|url=http://plus.maths.org/content/exploring-enigma|publisher=Plus Magazine}}
*{{cite web|last=Kamerling|first=Erik|url=https://community.broadcom.com/symantecenterprise/communities/community-home/librarydocuments/viewdocument?DocumentKey=84d57a16-74eb-4907-85a9-582e169affbc&CommunityKey=1ecf5f55-9545-44d6-b0f4-4e4a7f5f5e68&tab=librarydocuments|title=Elcomsoft Debuts Graphics Processing Unit (GPU) Password Recovery Advancement|date=2007-11-12|publisher=[[NortonLifeLock|Symantec]]}}
*{{cite news|last=Kingsley-Hughes|first=Adrian|url=http://www.zdnet.com/blog/hardware/elcomsoft-uses-nvidia-gpus-to-speed-up-wpawpa2-brute-force-attack/2724|archive-url=https://web.archive.org/web/20100626235736/http://www.zdnet.com/blog/hardware/elcomsoft-uses-nvidia-gpus-to-speed-up-wpawpa2-brute-force-attack/2724|url-status=dead|archive-date=June 26, 2010|title=ElcomSoft uses NVIDIA GPUs to Speed up WPA/WPA2 Brute-force Attack|work=[[ZDNet]]|date=2008-10-12}}
* {{cite journal|last=Landauer|first=L|url=http://domino.research.ibm.com/tchjr/journalindex.nsf/c469af92ea9eceac85256bd50048567c/8a9d4b4e96887b8385256bfa0067fba2?OpenDocument|title=Irreversibility and Heat Generation in the Computing Process|journal=IBM Journal of Research and Development|volume=5|year=1961|issue=3|pages=183–191|doi= 10.1147/rd.53.0183|archive-url=https://web.archive.org/web/20160303181021/http://domino.research.ibm.com/tchjr/journalindex.nsf/c469af92ea9eceac85256bd50048567c/8a9d4b4e96887b8385256bfa0067fba2?OpenDocument|archive-date=March 3, 2016 |url-access=subscription}}
* {{cite book|last1=Paar|first1=Christof|first2=Jan|last2=Pelzl|first3=Bart|last3=Preneel|url=http://www.crypto-textbook.com|title=Understanding Cryptography: A Textbook for Students and Practitioners|publisher=Springer|year=2010|isbn=978-3-642-04100-6}}
*{{cite book|last=Reynard|first=Robert|url=https://books.google.com/books?id=3nTmBW0ONEEC&pg=PA86|title=Secret Code Breaker II: A Cryptanalyst's Handbook|isbn=1-889668-06-0|year=1997|access-date=2008-09-21|publisher=Smith & Daniel Marketing|location=Jacksonville, FL}}
*{{cite book|last=Ristic|first=Ivan|url=https://books.google.com/books?id=HnQl5OVtOYgC|title=Modsecurity Handbook|publisher=Feisty Duck|year=2010 |isbn=978-1-907117-02-2}}
*{{cite book|last1=Viega|first1=John|author-link=John Viega|url=https://books.google.com/books?id=FBYHEBTrZUwC|first2=Matt|last2=Messier|first3=Pravir|last3=Chandra|access-date=2008-11-25|year=2002|isbn=0-596-00270-X|title=Network Security with OpenSSL|publisher=O'Reilly}}
* {{cite journal|last=Wiener|first=Michael J.|title=Efficient DES Key Search |journal= Practical Cryptography for Data Internetworks|publisher=W. Stallings, editor, IEEE Computer Society Press|year=1996}}
*{{cite web|url=http://www.us-cert.gov/cas/techalerts/TA08-137A.html|title=Technical Cyber Security Alert TA08-137A: Debian/Ubuntu OpenSSL Random Number Generator Vulnerability|date=2008-05-16|access-date=2008-08-10|publisher=[[United States Computer Emergency Readiness Team]] (CERT)|ref={{harvid|CERT-2008}}|archive-url=https://web.archive.org/web/20080916083758/http://www.us-cert.gov/cas/techalerts/TA08-137A.html|archive-date=September 16, 2008}}
* {{cite web|title=NSA's How Mathematicians Helped Win WWII|url=http://www.nsa.gov/about/cryptologic_heritage/center_crypt_history/publications/how_math_helped_win.shtml|date=15 Jan 2009|publisher=[[National Security Agency]]|ref={{harvid|NSA-2009}}|archive-url=https://web.archive.org/web/20090307080155/http://www.nsa.gov/about/cryptologic_heritage/center_crypt_history/publications/how_math_helped_win.shtml|archive-date=March 7, 2009}}
{{Refend}}

==External links==
*[http://www.distributed.net/DES RSA-sponsored DES-III cracking contest]
*[https://www.youtube.com/watch?v=IXglwbyMydM Demonstration of a brute-force device] designed to guess the passcode of locked [[iPhone]]s running [[iOS 10|iOS 10.3.3]]
*{{usurped|1=[https://web.archive.org/web/20030914091116/http://codebook.org/codebook_solution.pdf How We Cracked the Code Book Ciphers]}} – Essay by the winning team of the challenge in [[The Code Book]]

{{Cryptography navbox | block | hash}}

{{DEFAULTSORT:Brute-force attack}}
[[Category:Cryptographic attacks]]