Editing Brute-force attack (section)

==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}}