Password cracking
Encyclopedia
Password cracking is the process of recovering password
s from data
that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password. The purpose of password cracking might be to help a user recover a forgotten password (though installing an entirely new password is less of a security risk, but involves system administration privileges), to gain unauthorized access to a system, or as a preventive measure by system administrators to check for easily crackable passwords. On a file-by-file basis, password cracking is utilized to gain access to digital evidence for which a judge has allowed access but the particular file's access is restricted.
); which is a measure of the password's information entropy. Most methods of password cracking require the computer to produce many candidate passwords, each of which is checked. Brute-force cracking, in which a computer tries every possible key or password until it succeeds, is the lowest common denominator of password cracking. 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 increases exponentially 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.
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 quite large. 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 example, one commercial product claims to test 103,000 WPA
PSK passwords per second.
Individual desktop computers can test anywhere between one million to fifteen million passwords per second against a password hash for weaker algorithms, such as DES or LanManager. See: John the Ripper benchmarks. A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST. 230 is only one billion permutations and would take an average of 16 minutes to crack. 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. Graphics processors can speed up password cracking by a factor of 50 to 100 over general purpose computers. As of 2011, commercial products are available that claim the ability to test up to 2,800,000,000 passwords a second on a standard desktop computer using a high-end graphics processor. Such a device can crack a 10 letter single-case password in one day. Note that the work can be distributed over many computers for an additional speedup proportional to the number of available computers with comparable GPUs.
Despite their capabilities, desktop CPUs are slower at cracking passwords than purpose-built password breaking machines. In 1998, the Electronic Frontier Foundation
(EFF) built a dedicated password cracker using FPGAs, as opposed to general purpose CPUs. Their machine, Deep Crack
, broke a DES 56-bit key in 56 hours, testing over 90 billion keys per second. In 2010, the Georgia Tech Research Institute
developed a method of using GPGPU
to crack passwords, coming up with a minimum secure password length of 12 characters.
In "The Memorability and Security of Passwords", 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 capitalises 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.
reported an incident where an attacker had found 186,126 encrypted passwords. By the time they were discovered, they had already cracked 47,642 passwords.
In December 2009, a major password breach of the Rockyou.com
website occurred that led to the release of 32 million passwords. The hacker 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 a SQL Injection vulnerability. The Imperva
Application Defense Center (ADC) did an analysis on the strength of the passwords.
In June 2011, NATO (North Atlantic Treaty Organization) experienced a security breach that led to the public release of first and last names, usernames, and passwords for more than 11,000 registered users of their e-Bookshop. The data was leaked as part of Operation AntiSec
, a movement that includes Anonymous
, LulzSec
, as well as other hacking groups and individuals. The aim of AntiSec is to expose personal, sensitive, and restricted information to the world, using any means necessary.
On July 11, 2011, Booz Allen Hamilton
, a large American Consulting firm that does a substantial amount of work for the Pentagon
, had their 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." These leaked passwords wound up being hashed in Sha1, and were later decrypted and analyzed by the ADC team at Imperva
, revealing that even military personnel look for shortcuts and ways around the password requirements.
On July 18, 2011, Microsoft Hotmail banned the password: "123456".
operating 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 file /etc/shadow, which is accessible only to programs running with enhanced privileges (ie, "system" privileges). This makes it harder for a malicious user to obtain the hashed passwords in the first instance. Unfortunately, many common network protocols transmit passwords in cleartext or use weak challenge/response schemes.
Modern Unix systems have replaced traditional DES-based password hashing with stronger methods based on MD5 and Blowfish. 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. 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.
Many hashes used for storing passwords, such as MD5
and the SHA
family, are designed for fast computation and efficient implementation in hardware. Using key stretching algorithms, such as PBKDF2
, to form password hashes can significantly reduce the rate at which passwords can be tested.
Solutions like a security token
give a formal proof
answer by constantly shifting password. Those solutions abruptly reduce the timeframe for brute forcing (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.
, John the Ripper
, Hydra and ElcomSoft
. Many litigation support software packages also include password cracking functionality. Most of these packages employ a mixture of cracking strategies, with brute force and dictionary attacks proving to be the most productive, however more successful software packages are usually private tools and are not published publicly.
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
s from data
Data (computing)
In computer science, data is information in a form suitable for use with a computer. Data is often distinguished from programs. A program is a sequence of instructions that detail a task for the computer to perform...
that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password. The purpose of password cracking might be to help a user recover a forgotten password (though installing an entirely new password is less of a security risk, but involves system administration privileges), to gain unauthorized access to a system, or as a preventive measure by system administrators to check for easily crackable passwords. On a file-by-file basis, password cracking is utilized to gain access to digital evidence for which a judge has allowed access but the particular file's access is restricted.
Time needed for password searches
The time to crack a password is related to bit strength (see password strengthPassword strength
Password strength is a measure of the effectiveness of a password in resisting guessing and 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...
); which is a measure of the password's information entropy. Most methods of password cracking require the computer to produce many candidate passwords, each of which is checked. Brute-force cracking, in which a computer tries every possible key or password until it succeeds, is the lowest common denominator of password cracking. More common methods of password cracking, such as dictionary attacks
Dictionary attack
In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.-Technique:...
, 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 increases exponentially 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.
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 quite large. If not, the rate depends on whether the authentication software limits how often a password can be tried, either by time delays, CAPTCHA
CAPTCHA
A CAPTCHA is a type of challenge-response test used in computing as an attempt to ensure that the response is generated by a person. The process usually involves one computer asking a user to complete a simple test which the computer is able to generate and grade...
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 example, one commercial product claims to test 103,000 WPA
WPA
- Agencies and organizations :*World Pool-Billiard Association*World Psychiatric Association- United States :*Washington Project for the Arts*Women's Prison Association...
PSK passwords per second.
Individual desktop computers can test anywhere between one million to fifteen million passwords per second against a password hash for weaker algorithms, such as DES or LanManager. See: John the Ripper benchmarks. A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST. 230 is only one billion permutations and would take an average of 16 minutes to crack. When ordinary desktop computers are combined in a cracking effort, as can be done with botnet
Botnet
A botnet is a collection of compromised computers connected to the Internet. Termed "bots," they are generally used for malicious purposes. When a computer becomes compromised, it becomes a part of a botnet...
s, the capabilities of password cracking are considerably extended. In 2002, distributed.net
Distributed.net
distributed.net is a worldwide distributed computing effort that is attempting to solve large scale problems using otherwise idle CPU or GPU time. It is officially recognized as a non-profit organization under U.S...
successfully found a 64-bit RC5
RC5
In cryptography, RC5 is a block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, RC stands for "Rivest Cipher", or alternatively, "Ron's Code"...
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. Graphics processors can speed up password cracking by a factor of 50 to 100 over general purpose computers. As of 2011, commercial products are available that claim the ability to test up to 2,800,000,000 passwords a second on a standard desktop computer using a high-end graphics processor. Such a device can crack a 10 letter single-case password in one day. Note that the work can be distributed over many computers for an additional speedup proportional to the number of available computers with comparable GPUs.
Despite their capabilities, desktop CPUs are slower at cracking passwords than purpose-built password breaking machines. In 1998, the Electronic Frontier Foundation
Electronic Frontier Foundation
The Electronic Frontier Foundation is an international non-profit digital rights advocacy and legal organization based in the United States...
(EFF) built a dedicated password cracker using FPGAs, as opposed to general purpose CPUs. Their machine, Deep Crack
EFF DES cracker
In cryptography, the EFF DES cracker is a machine built by the Electronic Frontier Foundation in 1998 to perform a brute force search of DES cipher's key space — that is, to decrypt an encrypted message by trying every possible key...
, broke a DES 56-bit key in 56 hours, testing over 90 billion keys per second. In 2010, the Georgia Tech Research Institute
Georgia Tech Research Institute
The Georgia Tech Research Institute is the nonprofit applied research arm of the Georgia Institute of Technology in Atlanta, Georgia, United States...
developed a method of using GPGPU
GPGPU
General-purpose computing on graphics processing units is the technique of using a GPU, which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the CPU...
to crack passwords, coming up with a minimum secure password length of 12 characters.
Easy to remember, hard to guess
The easier a password is for the owner to remember generally means it will be easier for an attacker to guess. Passwords which are difficult to remember will reduce the security of a system because (a) users might need to write down or electronically store the password, (b) users will need frequent password resets and (c) users are more likely to re-use the same password. Similarly, the more stringent 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.In "The Memorability and Security of Passwords", 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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
" 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 capitalises 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.
Incidents
On July 16, 1998, CERTCERT Coordination Center
The CERT Coordination Center was created by DARPA in November 1988 after the Morris worm struck. It is a major coordination center in dealing with Internet security problems....
reported an incident where an attacker had found 186,126 encrypted passwords. By the time they were discovered, they had already cracked 47,642 passwords.
In December 2009, a major password breach of the Rockyou.com
RockYou
RockYou is a developer of social games and advertising solutions for social media. RockYou is focused on the development of social game titles, including Gourmet Ranch and the Zoo World franchise...
website occurred that led to the release of 32 million passwords. The hacker 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 a SQL Injection vulnerability. The Imperva
Imperva
Imperva , is a data security company headquartered in the United States, which provides solutions for high-value business data protection and prevents sensitive data theft from hackers and malicious insiders by securing data across three main areas: databases, file systems, and web...
Application Defense Center (ADC) did an analysis on the strength of the passwords.
In June 2011, NATO (North Atlantic Treaty Organization) experienced a security breach that led to the public release of first and last names, usernames, and passwords for more than 11,000 registered users of their e-Bookshop. The data was leaked as part of Operation AntiSec
Operation AntiSec
Operation Anti-Security, also referred to as Operation AntiSec or #AntiSec, is a series of hacking attacks performed by members of hacking group LulzSec, the group Anonymous, and others inspired by the announcement of the operation. LulzSec performed the earliest attacks of the operation, with the...
, a movement that includes Anonymous
Anonymous (group)
Anonymous is an international hacking group, spread through the Internet, initiating active civil disobedience, while attempting to maintain anonymity. Originating in 2003 on the imageboard 4chan, the term refers to the concept of many online community users simultaneously existing as an anarchic,...
, LulzSec
LulzSec
Lulz Security, commonly abbreviated as LulzSec, is a computer hacker group that claims responsibility for several high profile attacks, including the compromise of user accounts from Sony Pictures in 2011. The group also claimed responsibility for taking the CIA website offline...
, as well as other hacking groups and individuals. The aim of AntiSec is to expose personal, sensitive, and restricted information to the world, using any means necessary.
On July 11, 2011, Booz Allen Hamilton
Booz Allen Hamilton
Booz Allen Hamilton Inc. , or more commonly Booz Allen, is an American public consulting firm headquartered in McLean, Fairfax County, Virginia, with 80 other offices throughout the United States. Ralph Shrader is its Chairman and Chief Executive Officer. The firm was founded by Edwin Booz in...
, a large American Consulting firm that does a substantial amount of work for the Pentagon
Pentagon
In geometry, a pentagon is any five-sided polygon. A pentagon may be simple or self-intersecting. The sum of the internal angles in a simple pentagon is 540°. A pentagram is an example of a self-intersecting pentagon.- Regular pentagons :In a regular pentagon, all sides are equal in length and...
, had their servers hacked by Anonymous
Anonymous (group)
Anonymous is an international hacking group, spread through the Internet, initiating active civil disobedience, while attempting to maintain anonymity. Originating in 2003 on the imageboard 4chan, the term refers to the concept of many online community users simultaneously existing as an anarchic,...
and leaked the same day. "The leak, dubbed 'Military Meltdown Monday,' includes 90,000 logins of military personnel—including personnel from USCENTCOM
United States Central Command
The United States Central Command is a theater-level Unified Combatant Command unit of the U.S. armed forces, established in 1983 under the operational control of the U.S. Secretary of Defense...
, SOCOM
SOCOM
SOCOM is an acronym which refers to United States Special Operations Command or one of these related topics:* Firearms for USSOCOM's Offensive Sidearm Weapon System trials:** Heckler & Koch Mark 23 Mod 0** Colt OHWS* Springfield Armory, Inc...
, the Marine Corps
United States Marine Corps
The United States Marine Corps is a branch of the United States Armed Forces responsible for providing power projection from the sea, using the mobility of the United States Navy to deliver combined-arms task forces rapidly. It is one of seven uniformed services of the United States...
, various Air Force
United States Air Force
The United States Air Force is the aerial warfare service branch of the United States Armed Forces and one of the American uniformed services. Initially part of the United States Army, the USAF was formed as a separate branch of the military on September 18, 1947 under the National Security Act of...
facilities, Homeland Security
Homeland security
Homeland security is an umbrella term for security efforts to protect states against terrorist activity. Specifically, is a concerted national effort to prevent terrorist attacks within the U.S., reduce America’s vulnerability to terrorism, and minimize the damage and recover from attacks that do...
, State Department staff, and what looks like private sector contractors." These leaked passwords wound up being hashed in Sha1, and were later decrypted and analyzed by the ADC team at Imperva
Imperva
Imperva , is a data security company headquartered in the United States, which provides solutions for high-value business data protection and prevents sensitive data theft from hackers and malicious insiders by securing data across three main areas: databases, file systems, and web...
, revealing that even military personnel look for shortcuts and ways around the password requirements.
On July 18, 2011, Microsoft Hotmail banned the password: "123456".
Prevention
The best method of preventing password cracking is to ensure that attackers cannot get access even to the hashed password. For example, on the UnixUnix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer 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 file /etc/shadow, which is accessible only to programs running with enhanced privileges (ie, "system" privileges). This makes it harder for a malicious user to obtain the hashed passwords in the first instance. Unfortunately, many common network protocols transmit passwords in cleartext or use weak challenge/response schemes.
Modern Unix systems have replaced traditional DES-based password hashing with stronger methods based on MD5 and Blowfish. Other systems have also begun to adopt these methods. For instance, the Cisco IOS originally used a reversible Vigenère cipher
Vigenère cipher
The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution....
to encrypt passwords, but now uses md5-crypt with a 24-bit salt when the "enable secret" command is used. 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.
Many hashes used for storing passwords, such as MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
and the SHA
Sha
For other uses, see Sha .Sha is a letter of the Cyrillic alphabet. It commonly represents the voiceless postalveolar fricative , like the pronunciation of ⟨sh⟩ in "sheep", or the somewhat similar voiceless retroflex fricative . It is used in every variation of the Cyrillic alphabet, for Slavic and...
family, are designed for fast computation and efficient implementation in hardware. Using key stretching algorithms, such as PBKDF2
PBKDF2
PBKDF2 is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force's RFC 2898...
, to form password hashes can significantly reduce the rate at which passwords can be tested.
Solutions like a security token
Security token
A security token may be a physical device that an authorized user of computer services is given to ease authentication...
give a formal proof
Formal proof
A formal proof or derivation is a finite sequence of sentences each of which is an axiom or follows from the preceding sentences in the sequence by a rule of inference. The last sentence in the sequence is a theorem of a formal system...
answer by constantly shifting password. Those solutions abruptly reduce the timeframe for brute forcing (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.
Software
There are many password cracking software tools, but the most popular are Cain and AbelCain (software)
Cain and Abel is a password recovery tool for Microsoft Windows. It can 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 are done...
, John the Ripper
John the Ripper
John the Ripper is a free password cracking software tool. Initially developed for the UNIX operating system, it currently runs on fifteen different platforms...
, Hydra and ElcomSoft
ElcomSoft
ElcomSoft is a Russian computer software company specializing in computer security and data recovery applications. Popular products include their eBook processing and password recovery software supporting many of Microsoft's products. ElcomSoft is also a co-founder of the Independent Software...
. Many litigation support software packages also include password cracking functionality. Most of these packages employ a mixture of cracking strategies, with brute force and dictionary attacks proving to be the most productive, however more successful software packages are usually private tools and are not published publicly.