Password cracking is the process of recovering passwords 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.
Background
Passwords to access computer systems are usually stored, typically not in cleartext form, in a database so the system can perform password verification when users attempt to login. To preserve confidentiality of system passwords, the password verification data is typically generated by applying a one-way function to the password, possibly in combination with other data. For simplicity in this discussion, when the one-way function (which may be either an encryption function or cryptographic hash) does not incorporate a secret key, other than the password, we will refer to the one way function employed as a hash and its output as a hashed password.
Even though functions that create hashed passwords may be cryptographically secure, possession of a hashed password provides a quick way to test guesses for the password by applying the function to each guess, and comparing the result to the verification data. The most commonly used hash functions can be computed rapidly and the attacker can test guesses repeatedly with different guesses until one succeeds,meaning the plaintext password has been recovered.
The term password cracking is typically limited to recovery of one or more plaintext passwords from hashed passwords, but there are also many other ways of obtaining passwords illicitly; without the hashed version of a password, the attacker can still attempt access to the computer system in question with guessed passwords. However well designed systems limit the number of failed access attempts and can alert administrators to trace the source of the attack if that quota is exceeded. With the hashed password, the attacker can work undetected, and if the attacker has obtained several hashed passwords, the chances for cracking at least one is quite high.
Otherwise it is possible to try to obtain the passwords through other different methods, such as social engineering, wiretapping, keystroke logging, login spoofing, dumpster diving, phishing, shoulder surfing, timing attack, acoustic cryptanalysis, using a Trojan Horse or virus, identity management system attacks (such as abuse of Self-service password reset) and compromising host security (see password for details). However, cracking usually designates a guessing attack.
Cracking may be combined with other techniques. For example, use of a hash-based challenge-response authentication method for password verification may provide a hashed password to an eavesdropper, who can then crack the password. A number of stronger cryptographic protocols exist that do not expose hashed-passwords during verification over a network, either by protecting them in transmission using a high-grade key, or by using a zero-knowledge password proof.
Principal attack methods
Weak encryption
If a system uses a reversible function to obscure stored passwords, exploiting that weakness can recover even 'well-chosen' passwords. One example is the LM hash that Microsoft Windows uses by default to store user passwords that are less than 15 characters in length. LM hash converts the password into all uppercase letters then breaks the password into two 7-character fields which are then hashed separately, allowing each half to be attacked separately. Hash functions like SHA-512, SHA-1, and MD5 are considered impossible to invert when used correctly.
Guessing
See also: Password strength and Password policy
Many passwords can be guessed either by humans or by sophisticated cracking programs armed with dictionaries and the user's personal information.
Not surprisingly, many users choose weak passwords, usually one related to themselves in some way. Repeated research over some 40 years has demonstrated that around 40% of user-chosen passwords are readily guessable by programs.[1] Examples of insecure choices include:
* blank (none)
* the words "password", "passcode", "admin" and their derivatives
* the user's name or login name
* the name of their significant other or another person
* their birthplace or date of birth or a friend's, or a relative's
* a pet's name
* a dictionary word in any language
* a name of a celebrity they like
* automobile licence plate number
* a row of letters from a standard keyboard layout (eg, the qwerty keyboard -- qwerty itself, asdf, or qwertyuiop)
* a simple modification of one of the preceding, such as suffixing a digit or reversing the order of the letters.
and so on.
In one survey of MySpace passwords which had been phished, 3.8 percent of passwords were a single word found in a dictionary, and another 12 percent were a word plus a final digit; two-thirds of the time that digit was 1.[1]
Some users neglect to change the default password that came with their account on the computer system. And some administrators neglect to change default account passwords provided by the operating system vendor or hardware supplier. A famous example is the use of FieldService as a user name with Guest as the password. If not changed at system configuration time, anyone familiar with such systems will have 'cracked' an important password; such service accounts often have higher access privileges than a normal user account. Lists of default passwords are available on the Internet.[2]
Personal data about individuals are now available from various sources, many on-line, and can often be obtained by someone using social engineering techniques, such as posing as an opinion surveyor or a security control checker. Attackers who know the user may have information as well. For example, if a user chooses the password "19YaleLaw78" because he graduated from Yale Law School in 1978, a disgruntled business partner might be able to guess the password.
Cracking programs exist which accept personal information about the user being attacked and generate common variations for passwords suggested by that information.[3][4]
Brute force attack
A last resort is to try every possible password, known as a brute force attack. In theory, a brute force attack will always be successful since the rules for acceptable passwords must be publicly known, but as the length of the password increases, so does the number of possible passwords. This method is unlikely to be practical unless the password is relatively small. But, how small is too small? This depends heavily on whether the prospective attacker has access to the hash of the password, in which case the attack is called an offline attack (it can be done without connection to the protected resource), or not, in which case it is called an online attack. Offline attack is generally a lot easier, because testing a password is reduced to a quickly calculated mathematical computation; i.e., calculating the hash of the password to be tried and comparing it to the hash of the real password. In an online attack the attacker has to actually try to authenticate himself with all the possible passwords, where arbitrary rules and delays can be imposed by the system and the attempts can be logged. A common current length recommendation for cases where the attacker will not have access to the hash is 8 or more randomly chosen characters combining letters, numbers, and special (punctuation, etc) characters. Systems which limit passwords to numeric characters only, or upper case only, or, generally, which exclude possible password character choices make such attacks easier. Using longer passwords in such cases (if possible on a particular system) can compensate for a limited allowable character set. And, of course, even with an adequate range of character choice, users who ignore that range (using only upper case alphabetic characters, or digits alone, for instance) make brute force attacks much easier against those password choices.
Generic brute-force search techniques can be used to speed up the computation. But the real threat may be likely to be from smart brute-force techniques that exploit knowledge about how people tend to choose passwords. NIST SP 800-63 (2) provides further discussion of password quality, and suggests, for example, that an 8 character user-chosen password may provide somewhere between 18 and 30 bits of entropy, depending on how it is chosen. This amount of entropy is far less than what is generally considered safe for an encryption key.
How small is too small for offline attacks thus depends partly on an attacker's ingenuity and resources (e.g., available time, computing power, etc.), the latter of which will increase as computers get faster. Most commonly used hashes can be implemented using specialized hardware, allowing faster attacks. Large numbers of computers can be harnessed in parallel, each trying a separate portion of the search space. Unused overnight and weekend time on office computers can also be used for this purpose.
The distinction between guessing, dictionary and brute force attacks is not strict. They are similar in that an attacker goes through a list of candidate passwords one by one; the list may be explicitly enumerated or implicitly defined, may or may not incorporate knowledge about the victim, and may or may not be linguistically derived. Each of the three approaches, particularly 'dictionary attack', is frequently used as an umbrella term to denote all the three attacks and the spectrum of attacks encompassed by them.
Precomputation
Further information: Rainbow table
In its most basic form, precomputation involves hashing each word in the dictionary (or any search space of candidate passwords) and storing the
pairs in a way that enables lookup on the ciphertext field. This way, when a new encrypted password is obtained, password recovery is instantaneous. Precomputation can be very useful for a dictionary attack if salt is not used properly (see below), and the dramatic decrease in the cost of mass storage has made it practical for fairly large dictionaries.
Advanced precomputation methods exist that are even more effective. By applying a time-memory tradeoff, a middle ground can be reached - a search space of size N can be turned into an encrypted database of size O(N2/3) in which searching for an encrypted password takes time O(N2/3). The theory has recently been refined into a practical technique. Another example [2] cracks alphanumeric Windows LAN Manager passwords in a few seconds. This is much faster than brute force attacks on the obsolete LAN Manager, which uses a particularly weak method of hashing the password. Current Windows systems still compute and store a LAN Manager hash by default for backwards compatibility. [3])
A technique similar to precomputation, known generically as memoization, can be used to crack multiple passwords at the cost of cracking just one. Since encrypting a word takes much longer than comparing it with a stored word, a lot of effort is saved by encrypting each word only once and comparing it with each of the encrypted passwords using an efficient list search algorithm. The two approaches may of course be combined: the time-space tradeoff attack can be modified to crack multiple passwords simultaneously in a shorter time than cracking them one after the other.
Salting
Further information: Salt (cryptography)
The benefits of precomputation and memoization can be nullified by randomizing the hashing process. This is known as salting. When the user sets a password, a short, random string called the salt is suffixed to the password before encrypting it; the salt is stored along with the encrypted password so that it can be used during verification. Since the salt is usually different for each user, the attacker can no longer construct tables with a single encrypted version of each candidate password. Early Unix systems used a 12-bit salt. Attackers could still build tables with common passwords encrypted with all 4096 possible 12-bit salts. However, if the salt is long enough (e.g. 32 bits), there are too many possibilities and the attacker must repeat the encryption of every guess for each user.
Early Unix password vulnerability
Early Unix implementations used a 12-bit salt, which allowed for 4096 possibilities, and limited passwords to 8 characters. While 12 bits was good enough for most purposes in the 1970s (although some expressed doubts even then), by 2005 disk storage had become cheap enough that an attacker can precompute encryptions of millions of common passwords, including all 4096 possible salt variations for each password, and store the precomputed values on a single portable hard drive. An attacker with a larger budget can build a disk farm with all 6 character passwords and the most common 7 and 8 character passwords stored in encrypted form, for all 4096 possible salts. And when several thousand passwords are being cracked at once, memoization still offers some benefit. Since there is little downside to using a longer (say 32-, 64- or 128-bit) salt, and they render any precomputation or memoization hopeless, modern implementations choose to do so.
Prevention
The best method of preventing password cracking is to ensure that attackers cannot get access even to the encrypted password. For example, on the Unix operating system, encrypted 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 encrypted passwords in the first instance. Unfortunately, many common network protocols transmit the hashed passwords to allow remote authentication.
References
1. ^ ZDNet Report: Net users picking safer passwords
2. ^ Default Password List Pnenoelit.de Retrieved on 2007-05-07
3. ^ John the Ripper project, John the Ripper cracking modes
4. ^ Bruce Schneier, Choosing Secure Passwords
1. Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off. CRYPTO 2003: pp617–630
2. NIST Special Publication 800-63: Electronic Authentication Guideline
See also
* Cryptographic key length
* Password-authenticated key agreement
External links
* Password Cracking with Rainbowcrack and Rainbow Tables
Password Cracking Software
Ophcrack | Crack | Cain | John the Ripper | L0phtCrack | RainbowCrack | SAMInside
Password
In computing, a password is a word or string of characters, entered, often along with a user name, into a computer system to log in or to gain access to some resource. Passwords are a popular form of authentication.
..... Click the link for more information.
Data (computing)
In computer science, data is anything in a form suitable for use with a computer[1]. Data is often distinguished from programs.
..... Click the link for more information.
Computer
A computer is a machine that manipulates data according to a list of instructions.
The first devices that resemble modern computers date to the mid-20th century (around 1940 - 1945), although the computer concept and various machines
..... Click the link for more information.
Cleartext
In data communications, cleartext is the form of a message or data which is in a form that is immediately comprehensible to a human being without additional processing.
..... Click the link for more information.
One-way function
Unsolved problems in computer science: ''Do one-way functions exist?''
A one-way function is a function that is easy to compute but "hard to invert" (in the sense defined below).
..... Click the link for more information.
Cryptographic hash function
In cryptography, a cryptographic hash function is a transformation that takes an input and returns a fixed-size string, which is called the hash value.
..... Click the link for more information.
Plaintext
In cryptography, plaintext is the information which the sender wishes to transmit to the receiver(s). Before the computer era, plaintext simply meant text in the language of the communicating parties.
..... Click the link for more information.
Social engineering (security)
Social engineering is the art of manipulating people into performing actions or divulging confidential information.
..... Click the link for more information.
Telephone tapping
Wiretap redirects here. For the radio program, see WireTap (radio program)
Telephone tapping (or wire tapping/wiretapping
..... Click the link for more information.
Keystroke logging
Keystroke logging (often called keylogging) is a method of capturing and recording user keystrokes. Keylogging can be useful to determine sources of errors in computer systems, to study how users interact and access with
..... Click the link for more information.
Login spoofing
Login spoofing is a technique used to obtain a user's password. The user is presented with an ordinary looking login prompt for username and password, which is actually a malicious program, usually called a Trojan horse under the
..... Click the link for more information.
Dumpster diving
Dumpster diving is the practice of sifting through commercial or residential trash to find items that have been discarded by their owners, but which may be useful to the Dumpster diver.
..... Click the link for more information.
Phishing
In computing, phishing is an attempt to criminally and fraudulently acquire sensitive information, such as usernames, passwords and credit card details, by masquerading as a trustworthy entity in an electronic communication.
..... Click the link for more information.
Shoulder surfing (computer security)
In computer security, shoulder surfing refers to using direct observation techniques, such as looking over someone's shoulder, to get information.
..... Click the link for more information.
Timing attack
In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms.
..... Click the link for more information.
Acoustic cryptanalysis
Acoustic cryptanalysis is a side channel attack which exploits sounds, audible or not, produced during a computation or input-output operation by computer workstations, impact printers, or electromechanical cipher machines.
..... Click the link for more information.
Trojan horse (computing)
This article refers to a form of malware in computing terminology. For other meanings, see Trojan Horse (disambiguation)
In the context of computing and software, a Trojan horse, or simply
..... Click the link for more information.
Computer virus
A computer virus is a computer program that can copy itself and infect a computer without permission or knowledge of the user.
..... Click the link for more information.
Self-service password reset
Self-service password reset is defined as any process or technology that allows users who have either forgotten their password or triggered an intruder lockout to authenticate with an alternate factor, and repair their own
..... Click the link for more information.
Password
In computing, a password is a word or string of characters, entered, often along with a user name, into a computer system to log in or to gain access to some resource. Passwords are a popular form of authentication.
..... Click the link for more information.
Challenge-response authentication
In computer security, challenge-response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to
..... Click the link for more information.
Cryptographic protocol
A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.
..... Click the link for more information.
Zero-knowledge password proof
A zero-knowledge password proof (ZKPP) refers to a password-authenticated key agreement protocol that is secure against off-line dictionary attacks.
..... Click the link for more information.
LM hash
LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows versions previous to Windows Vista use to store user passwords that are fewer than 15 characters long.
..... Click the link for more information.
Hash function
A hash function is any well-defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array.
..... Click the link for more information.
SHA hash functions
The SHA hash functions are five cryptographic hash functions designed by the National Security Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm.
..... Click the link for more information.
SHA hash functions
The SHA hash functions are five cryptographic hash functions designed by the National Security Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm.
..... Click the link for more information.
MD5
MD5
General
Designers Ron Rivest
First published April 1992
Series MD, MD2, MD3, MD4, MD5
Detail
Digest sizes 128 bits
Rounds 4
In cryptography, MD5 (Message-Digest algorithm 5
..... Click the link for more information.
Password strength
Password strength is a measurement of the effectiveness of a password as an authentication credential. The strength of a password is a function of length, complexity, and randomness.
..... Click the link for more information.
Password policy
A password policy is a set of rules designed to enhance computer security by encouraging users to employ strong passwords and use them properly.
..... Click the link for more information.
This article is copied from an article on Wikipedia® - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the Wikipedia® encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
