Recovering passwords stored or transmitted by computer systems
In cryptanalysis and computer security, password cracking is the process of recovering passwords[1] from data that has been stored in or transmitted by a computer system in scrambled form. A common approach (brute-force attack) is to repeatedly try guesses for the password and to check them against an available cryptographic hash of the password.[2] Another type of approach is password spraying, which is often automated and occurs slowly over time in order to remain undetected, using a list of common passwords.[3]
The purpose of password cracking might be to help a user recover a forgotten password (due to the fact that installing an entirely new password would involve System Administration privileges), to gain unauthorized access to a system, or to act as a preventive measure whereby system administrators check for easily crackable passwords. On a file-by-file basis, password cracking is utilized to gain access to digital evidence to which a judge has allowed access, when a particular file's permissions restricted.
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, 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 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.[4] More common methods of password cracking, such as dictionary attacks, pattern checking, word list substitution, etc. attempt to reduce the number of trials required and will usually be attempted before brute force. 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.[5]
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, CAPTCHAs, 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[1][6][7](see John the Ripper benchmarks).[8] 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 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. 230 is only one billion permutations[9] 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 botnets, 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.[10]
Graphics processing units 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.[11] 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 DES, Triple DES, bcrypt, scrypt, and Argon2.
The emergence over the past decade[when?] of hardware acceleration in a 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 per second, allowing them to check password combinations in 5.5 hours. Using ocl-Hashcat Plus on a Virtual OpenCL cluster platform,[12] the Linux-based GPU cluster was used to "crack 90 percent of the 6.5 million password hashes belonging to users of LinkedIn".[13]
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 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, Deep Crack, broke a DES 56-bit key in 56 hours, testing over 90 billion keys per second.[14] 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.[15] Since 2019, John the Ripper supports password cracking for a limited number of hashing algorithms using FPGAs.[16] Commercial companies are now using FPGA-based setups for password cracking.[17]
Easy to remember, hard to guess
Passwords that are difficult to remember will reduce the security of a system because
users might need to write down or electronically store the password using an insecure method,
users will need frequent password resets, and
users are more likely to re-use the same password.
Similarly, the more stringent the requirements for password strength, e.g. "have a mix of uppercase and lowercase letters and digits" or "change it monthly", the greater the degree to which users will subvert the system.[18]
In "The Memorability and Security of Passwords",[19] Jeff Yan et al. examine the effect of advice given to users about a good choice of password. They found that passwords based on thinking of a phrase and taking the first letter of each word are just as memorable as naively selected passwords, and just as hard to crack as randomly generated passwords. Combining two unrelated words is another good method. Having a personally designed "algorithm" for generating obscure passwords is another good method.
However, asking users to remember a password consisting of a "mix of uppercase and lowercase characters" is similar to asking them to remember a sequence of bits: hard to remember, and only a little bit harder to crack (e.g. only 128 times harder to crack for 7-letter passwords, less if the user simply capitalizes one of the letters). Asking users to use "both letters and digits" will often lead to easy-to-guess substitutions such as 'E' → '3' and 'I' → '1': substitutions which are well known to attackers. Similarly, typing the password one keyboard row higher is a common trick known to attackers.
Research detailed in an April 2015 paper by several professors at Carnegie Mellon University shows that people's choices of password structure often follow several known patterns. For example, when password requirements require a long minimum length such as 16 characters, people tend to repeat characters or even entire words within their passwords.[20] As a result, passwords may be much more easily cracked than their mathematical probabilities would otherwise indicate. Passwords containing one digit, for example, disproportionately include it at the end of the password.[20]
Incidents
On July 16, 1998, CERT reported an incident where an attacker had found 186,126 encrypted passwords. By the time the breach was discovered, 47,642 passwords had already been cracked.[21]
In December 2009, a major password breach of Rockyou.com occurred that led to the release of 32 million passwords. The attacker then leaked the full list of the 32 million passwords (with no other identifiable information) to the internet. Passwords were stored in cleartext in the database and were extracted through an SQL injection vulnerability. The Imperva Application Defense Center (ADC) did an analysis on the strength of the passwords.[22] Some of the key findings were:
about 30% of users chose passwords whose length was below seven characters,
almost 60% of users chose their passwords from a limited set of alpha-numeric characters, and
nearly 50% of users used names, slang words, dictionary words, or trivial passwords that employed weak constructs such as consecutive digits and/or adjacent keyboard keys—case in point, the most common password among RockYou account owners was simply “123456”.[23]
In June 2011, NATO (North Atlantic Treaty Organization) suffered a security breach that led to the public release of first and last names, usernames, and passwords of more than 11,000 registered users of their e-bookshop. The data were leaked as part of Operation AntiSec, a movement that includes Anonymous, LulzSec, and other hacking groups and individuals.[24]
On July 11, 2011, Booz Allen Hamilton, a large American consulting firm that does a substantial amount of work for the Pentagon, had its servers hacked by Anonymous and leaked the same day. "The leak, dubbed 'Military Meltdown Monday', includes 90,000 logins of military personnel—including personnel from USCENTCOM, SOCOM, the Marine Corps, various Air Force facilities, Homeland Security, State Department staff, and what looks like private-sector contractors."[25] These leaked passwords were found to be hashed with unsaltedSHA-1, and were later analyzed by the ADC team at Imperva, revealing that even some military personnel used passwords as weak as "1234".[26]
On July 18, 2011, Microsoft Hotmail banned the password: "123456".[27]
In July 2015, a group calling itself "The Impact Team" stole the user data of Ashley Madison.[28] Many passwords were hashed using both the relatively strong bcrypt algorithm and the weaker MD5 hash. Attacking the latter algorithm allowed some 11 million plaintext passwords to be recovered by password cracking group CynoSure Prime.[29]
Prevention
One method of preventing a password from being cracked is to ensure that attackers cannot get access even to the hashed password. For example, on the Unixoperating system, hashed passwords were originally stored in a publicly accessible file /etc/passwd. On modern Unix (and similar) systems, on the other hand, they are stored in the shadow password file /etc/shadow, which is accessible only to programs running with enhanced privileges (i.e., "system" privileges). This makes it harder for a malicious user to obtain the hashed passwords in the first instance, however many collections of password hashes have been stolen despite such protection. And some common network protocols transmit passwords in cleartext or use weak challenge/response schemes.[30][31]
Another approach is to combine a site-specific secret key with the password hash, which prevents plaintext password recovery even if the hashed values are purloined. However privilege escalation attacks that can steal protected hash files may also expose the site secret. A third approach is to use key derivation functions that reduce the rate at which passwords can be guessed.[32]:5.1.1.2
Another protection measure is the use of salt, a random value unique to each password that is incorporated in the hashing. Salt prevents multiple hashes from being attacked simultaneously and also prevents the creation of pre-computed dictionaries such as rainbow tables.
Modern Unix Systems have replaced the traditional DES-based password hashing function crypt() with stronger methods such as crypt-SHA, bcrypt, and scrypt.[33] Other systems have also begun to adopt these methods. For instance, the Cisco IOS originally used a reversible Vigenère cipher to encrypt passwords, but now uses md5-crypt with a 24-bit salt when the "enable secret" command is used.[34] These newer methods use large salt values which prevent attackers from efficiently mounting offline attacks against multiple user accounts simultaneously. The algorithms are also much slower to execute which drastically increases the time required to mount a successful offline attack.[35]
Many hashes used for storing passwords, such as MD5 and the SHA family, are designed for fast computation with low memory requirements and efficient implementation in hardware. Multiple instances of these algorithms can be run in parallel on graphics processing units (GPUs), speeding cracking. As a result, fast hashes are ineffective in preventing password cracking, even with salt. Some key stretching algorithms, such as PBKDF2 and crypt-SHA iteratively calculate password hashes and can significantly reduce the rate at which passwords can be tested, if the iteration count is high enough. Other algorithms, such as scrypt are memory-hard, meaning they require relatively large amounts of memory in addition to time-consuming computation and are thus more difficult to crack using GPUs and custom integrated circuits.
In 2013 a long-term Password Hashing Competition was announced to choose a new, standard algorithm for password hashing,[36] with Argon2 chosen as the winner in 2015. Another algorithm, Balloon, is recommended by NIST.[37] Both algorithms are memory-hard.
Solutions like a security token give a formal proof answer by constantly shifting password. Those solutions abruptly reduce the timeframe available for brute forcing (the attacker needs to break and use the password within a single shift) and they reduce the value of the stolen passwords because of its short time validity.
The increased availability of computing power and beginner friendly automated password cracking software for a number of protection schemes has allowed the activity to be taken up by script kiddies.[40]
A password, sometimes called a passcode, is secret data, typically a string of characters, usually used to confirm a user's identity. Traditionally, passwords were expected to be memorized, but the large number of password-protected services that a typical individual accesses can make memorization of unique passwords for each service impractical. Using the terminology of the NIST Digital Identity Guidelines, the secret is held by a party called the claimant while the party verifying the identity of the claimant is called the verifier. When the claimant successfully demonstrates knowledge of the password to the verifier through an established authentication protocol, the verifier is able to infer the claimant's identity.
In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.
In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key which is typically created from the password using a key derivation function. This is known as an exhaustive key search. This approach doesn't depend on intellectual tactics; rather, it relies on making several attempts.
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. It is similar to a password in usage, but a passphrase is generally longer for added security. Passphrases are often used to control both access to, and the operation of, cryptographic programs and systems, especially those that derive an encryption key from a passphrase. The origin of the term is by analogy with password. The modern concept of passphrases is believed to have been invented by Sigmund N. Porter in 1982.
John the Ripper is a free password cracking software tool. Originally developed for the Unix operating system, it can run on fifteen different platforms. It is among the most frequently used password testing and breaking programs as it combines a number of password crackers into one package, autodetects password hash types, and includes a customizable cracker. It can be run against various encrypted password formats including several crypt password hash types most commonly found on various Unix versions, Kerberos AFS, and Windows NT/2000/XP/2003 LM hash. Additional modules have extended its ability to include MD4-based password hashes and passwords stored in LDAP, MySQL, and others.
A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:
In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.
The Security Account Manager (SAM) is a database file in Windows XP, Windows Vista, Windows 7, 8.1, 10 and 11 that stores users' passwords. It can be used to authenticate local and remote users. Beginning with Windows 2000 SP4, Active Directory authenticates remote users. SAM uses cryptographic measures to prevent unauthenticated users accessing the system.
In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.
LAN Manager is a discontinued network operating system (NOS) available from multiple vendors and developed by Microsoft in cooperation with 3Com Corporation. It was designed to succeed 3Com's 3+Share network server software which ran atop a heavily modified version of MS-DOS.
A rainbow table is a precomputed table for caching the outputs of a cryptographic hash function, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of an attacker, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a key derivation function that adds a "salt" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash.
In a Windows network, NT LAN Manager (NTLM) is a suite of Microsoft security protocols intended to provide authentication, integrity, and confidentiality to users. NTLM is the successor to the authentication protocol in Microsoft LAN Manager (LANMAN), an older Microsoft product. The NTLM protocol suite is implemented in a Security Support Provider, which combines the LAN Manager authentication protocol, NTLMv1, NTLMv2 and NTLM2 Session protocols in a single package. Whether these protocols are used or can be used on a system which is governed by Group Policy settings, for which different versions of Windows have different default settings.
Cain and Abel was a password recovery tool for Microsoft Windows. It could recover many kinds of passwords using methods such as network packet sniffing, cracking various password hashes by using methods such as dictionary attacks, brute force and cryptanalysis attacks. Cryptanalysis attacks were done via rainbow tables which could be generated with the winrtgen.exe program provided with Cain and Abel. Cain and Abel was maintained by Massimiliano Montoro and Sean Babcock.
In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.
Password strength is a measure of the effectiveness of a password against guessing or brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly. The strength of a password is a function of length, complexity, and unpredictability.
bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.
In cryptography, scrypt is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.
crypt is a POSIX C library function. It is typically used to compute the hash of user account passwords. The function outputs a text string which also encodes the salt, and identifies the hash algorithm used. This output string forms a password record, which is usually stored in a text file.
Hashcat is a password recovery tool. It had a proprietary code base until 2015, but was then released as open source software. Versions are available for Linux, macOS, and Windows. Examples of hashcat-supported hashing algorithms are LM hashes, MD4, MD5, SHA-family and Unix Crypt formats as well as algorithms used in MySQL and Cisco PIX.
In cryptography, a pepper is a secret added to an input such as a password during hashing with a cryptographic hash function. This value differs from a salt in that it is not stored alongside a password hash, but rather the pepper is kept separate in some other medium, such as a Hardware Security Module. Note that the National Institute of Standards and Technology refers to this value as a secret key rather than a pepper. A pepper is similar in concept to a salt or an encryption key. It is like a salt in that it is a randomized value that is added to a password hash, and it is similar to an encryption key in that it should be kept secret.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
