Editing Password cracking (section)

==Time needed for password searches==
The time to crack a password is related to bit strength, which is a measure of the password's [[entropy (information theory)|entropy]], and the details of how the password is stored. Most methods of password cracking require the computer to produce many candidate passwords, each of which is checked. One example is [[brute-force attack|brute-force]] cracking, in which a computer tries ''every'' possible key or password until it succeeds. With multiple processors, this time can be optimized through searching from the last possible group of symbols and the beginning at the same time, with other processors being placed to search through a designated selection of possible passwords.<ref>{{cite journal |last1=Bahadursingh |first1=Roman |title=A Distributed Algorithm for Brute Force Password Cracking on n Processors |date=January 19, 2020 |doi=10.5281/zenodo.3612276 |url=https://zenodo.org/record/3612276}}</ref> More common methods of password cracking, such as [[dictionary attack]]s, pattern checking, and variations of common words, aim to optimize the number of guesses and are usually attempted before brute-force attacks. Higher password bit strength exponentially increases the number of candidate passwords that must be checked, on average, to recover the password and reduces the likelihood that the password will be found in any cracking dictionary.<ref name="SS1">{{cite web |last=Lundin |first=Leigh |title=PINs and Passwords, Part 2 |website=SleuthSayers.org |location=Orlando |date=August 11, 2013 |url=https://www.sleuthsayers.org/2013/08/pins-and-passwords-part-2.html}}</ref>

The ability to crack passwords using computer programs is also a function of the number of possible passwords per second which can be checked. If a hash of the target password is available to the attacker, this number can be in the billions or trillions per second, since an ''offline attack'' is possible. If not, the rate depends on whether the authentication software limits how often a password can be tried, either by time delays, [[CAPTCHA]]s, or forced lockouts after some number of failed attempts. Another situation where quick guessing is possible is when the password is used to form a [[cryptographic key]]. In such cases, an attacker can quickly check to see if a guessed password successfully decodes encrypted data.

For some kinds of password hash, ordinary desktop computers can test over a hundred million passwords per second using password cracking tools running on a general purpose CPU and billions of passwords per second using GPU-based password cracking tools<ref name=":0">[http://hashcat.net/oclhashcat-lite/ oclHashcat-lite – advanced password recovery]. Hashcat.net. Retrieved on January 31, 2013.</ref><ref name="bugcharmer">Alexander, Steven. (June 20, 2012) [https://bugcharmer.blogspot.com/2012/06/how-long-should-passwords-be.html The Bug Charmer: How long should passwords be?]. Bugcharmer.blogspot.com. Retrieved on January 31, 2013.</ref><ref>[http://blog.cryptohaze.com/2012/07/154-billion-ntlmsec-on-10-hashes.html Cryptohaze Blog: 154 Billion NTLM/sec on 10 hashes]. Blog.cryptohaze.com (July 15, 2012). Retrieved on January 31, 2013.</ref> {{xref|(see [[John the Ripper]] benchmarks)}}.<ref>[http://openwall.info/wiki/john/benchmarks John the Ripper benchmarks]. openwall.info (March 30, 2010). Retrieved on January 31, 2013.</ref> The rate of password guessing depends heavily on the cryptographic function used by the system to generate password hashes. A suitable password hashing function, such as [[bcrypt]], is many orders of magnitude better than a naive function like simple [[MD5]] or [[Secure Hash Algorithm|SHA]]. A user-selected eight-character password with numbers, mixed case, and symbols, with commonly selected passwords and other dictionary matches filtered out, reaches an estimated 30-bit strength, according to NIST. 2<sup>30</sup> is only one billion permutations<ref>{{Cite report |url=https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-63ver1.0.2.pdf |title=Electronic authentication guideline |last=Burr |first=W E |last2=Dodson |first2=D F |date=2006 |publisher=National Institute of Standards and Technology |issue=NIST SP 800-63v1.0.2 |doi=10.6028/nist.sp.800-63v1.0.2 |location=Gaithersburg, MD |language=en |last3=Polk |first3=W T}}</ref> and would be cracked in seconds if the hashing function were naive. When ordinary desktop computers are combined in a cracking effort, as can be done with [[botnet]]s, the capabilities of password cracking are considerably extended. In 2002, [[distributed.net]] successfully found a 64-bit [[RC5]] key in four years, in an effort which included over 300,000 different computers at various times, and which generated an average of over 12 billion keys per second.<ref name=distributed>{{cite web |title=64-bit key project status |publisher=Distributed.net |access-date=March 27, 2008 |url=https://stats.distributed.net/projects.php?project_id=5 |url-status=dead |archive-url=https://web.archive.org/web/20130910051812/http://stats.distributed.net/projects.php?project_id=5 |archive-date=September 10, 2013}}</ref>

[[Graphics processing unit]]s can speed up password cracking by a factor of 50 to 100 over general purpose computers for specific hashing algorithms. As an example, in 2011, available commercial products claimed the ability to test up to 2,800,000,000 [[NTLM]] passwords a second on a standard desktop computer using a high-end graphics processor.<ref name=elcomsoft>{{cite web |url=http://www.elcomsoft.com/eprb.html#gpu |title=Password Recovery Speed table |publisher=[[ElcomSoft]] |accessdate=February 1, 2011 |archive-url=https://web.archive.org/web/20110221191727/http://www.elcomsoft.com/eprb.html#gpu |archive-date=2011-02-21}}</ref> Such a device can crack a 10-letter single-case password in one day. The work can be distributed over many computers for an additional speedup proportional to the number of available computers with comparable GPUs. However some algorithms run slowly, or even are specifically designed to run slowly, on GPUs. Examples are [[Data Encryption Standard|DES]], [[Triple DES]], [[bcrypt]], [[scrypt]], and [[Argon2]].

Hardware acceleration in a [[graphics processing unit|GPU]] has enabled resources to be used to increase the efficiency and speed of a brute force attack for most hashing algorithms. In 2012, Stricture Consulting Group unveiled a 25-GPU cluster that achieved a brute force attack speed of 350 billion guesses of NTLM passwords per second, allowing them to check <math display="inline">95^8</math>password combinations in 5.5 hours, enough to crack all 8-character alpha-numeric-special-character passwords commonly used in enterprise settings. Using ocl-[[Hashcat]] Plus on a Virtual [[OpenCL]] cluster platform,<ref>{{cite web |url=https://mosix.cs.huji.ac.il/txt_vcl.html/ |title=VCL Cluster Platform |website=mosix.cs.huji.ac.il}}</ref> the Linux-based [[GPU cluster]] was used to "crack 90 percent of the 6.5 million password hashes belonging to users of LinkedIn".<ref>{{cite web |url=https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/ |title=25-GPU cluster cracks every standard Windows password in <6 hours |year=2012}}</ref>

For some specific hashing algorithms, CPUs and GPUs are not a good match. Purpose-made hardware is required to run at high speeds. Custom hardware can be made using [[FPGA]] or [[application-specific integrated circuit|ASIC]] technology. Development for both technologies is complex and (very) expensive. In general, FPGAs are favorable in small quantities, ASICs are favorable in (very) large quantities, more energy efficient, and faster. In 1998, the [[Electronic Frontier Foundation]] (EFF) built a dedicated password cracker using ASICs. Their machine, [[EFF DES cracker|Deep Crack]], broke a DES 56-bit key in 56 hours, testing over 90 billion keys per second.<ref name=EFF-deep-crack>{{cite web |title=EFF DES Cracker machine brings honesty to crypto debate |publisher=EFF |url=http://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/HTML/19980716_eff_descracker_pressrel.html |access-date=June 7, 2020 |url-status=dead |archive-url=https://web.archive.org/web/20100101001853/http://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/HTML/19980716_eff_descracker_pressrel.html |archive-date=January 1, 2010}}</ref> In 2017, leaked documents showed that ASICs were used for a military project that had a potential to code-break many parts of the Internet communications with weaker encryption.<ref>{{cite web |title=NYU Accidentally Exposed Military Code-breaking Computer Project to Entire Internet |last1=Biddle |first1=Sam |date=May 11, 2017 |website=The Intercept |url=https://theintercept.com/2017/05/11/nyu-accidentally-exposed-military-code-breaking-computer-project-to-entire-internet/}}</ref> Since 2019, John the Ripper supports password cracking for a limited number of hashing algorithms using FPGAs.<ref>{{cite web |url=https://www.openwall.com/lists/announce/2019/05/14/1 |title=announce - [openwall-announce] John the Ripper 1.9.0-jumbo-1 |website=openwall.com}}</ref> Commercial companies are now using FPGA-based setups for password cracking.<ref>{{cite web |url=https://scatteredsecrets.medium.com/bcrypt-password-cracking-extremely-slow-not-if-you-are-using-hundreds-of-fpgas-7ae42e3272f6 |title=Bcrypt password cracking extremely slow? Not if you are using
|website=Medium|date=September 8, 2020
}}</ref>