NationMaster - Encyclopedia: Password cracking

Password cracking is the process of recovering secret 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. A password is a form of secret authentication data that is used to control access to a resource. ... In Computer Science, data is often distinguished from code, though both are represented in modern computers as binary strings. ... This article or section is in need of attention from an expert on the subject. ...

MIX RULES

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. In data communications, cleartext is the form of a message or data which is transferred or stored without cryptographic protection. ... 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 cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...

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. In cryptography, plaintext is information used as input to an encryption algorithm; the output is termed ciphertext. ...

The term password cracking is typically limited to recovery of one or more plaintext passwords from hashed passwords. Password cracking requires that an attacker can gain access to a hashed password, either by reading the password verification database (e.g., via a Trojan Horse, virus program, or social engineering) or intercepting a hashed password sent over an open network, or has some other way to rapidly and without limit test whether a guessed password is correct. In cryptography, plaintext is information used as input to an encryption algorithm; the output is termed ciphertext. ... The tone or style of this article or section may not be appropriate for Wikipedia. ... In computer security technology, a virus is a self-replicating program that spreads by inserting copies of itself into other executable code or documents (for a complete definition: see below). ...

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.

There are also many other ways of obtaining passwords illicitly, such as social engineering, wiretapping, keystroke logging, login spoofing, dumpster diving, phishing, shoulder surfing, timing attack, acoustic cryptanalysis, 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. Social engineering is the practice of obtaining confidential information by manipulation of legitimate users. ... It has been suggested that Voice logging be merged into this article or section. ... Keystroke logging (often called keylogging) is a diagnostic tool used in software development that captures the users keystrokes. ... Login spoofing is a technique used to obtain a users password. ... Dumpster diving is the practice of rummaging through trash, whether commercial or residential, to find items of use that have been discarded. ... This phishing attempt, disguised as an official email from a (fictional) bank, attempts to trick the banks members into giving away their account information by confirming it at the phishers linked website. ... In computer security, shoulder surfing refers to using direct observation techniques, such as looking over someones shoulder, to get information. ... In cryptography, a timing attack is a form of side channel attack where the attacker tries to break a cryptosystem by analyzing the time taken to execute cryptographic algorithms. ... Acoustic cryptanalysis is a side channel attack which exploits sounds, audible or not, produced during a computation or input-output operation. ... 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 problem, without calling the help desk. ... A password is a form of secret authentication data that is used to control access to a resource. ...

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. 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 be authenticated. ... A cryptographic protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods. ... In cryptography, a zero-knowledge password proof (ZKPP) is an interactive method for one party (the prover) to prove to another party (the verifier) that it knows a value of a password, without revealing anything other than the fact that it knows that password to the verifier. ...

Principal attack methods

Weak encryption

If a system uses a cryptographically weak function to hash or encrypt passwords, exploiting that weakness can recover even 'well-chosen' passwords. Decryption need not be a quick operation, and can be conducted while not connected to the target system. Any 'cracking' technique of this kind is considered successful if it can decrypt the password in fewer operations than would be required by a brute force attack (see below). The fewer operations required, the "weaker" the encryption is considered to be (for equivalently 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 breaks the password into two 7-character fields which are then hashed separately, allowing each half to be attacked separately. The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek ÎºÏÏ…Ï€Ï„ÏŒÏ‚ kryptÃ³s hidden, and the verb Î³ÏÎ¬Ï†Ï‰ grÃ¡fo write or Î»ÎµÎ³ÎµÎ¹Î½ legein to speak) is the study of message secrecy. ... The EFFs US$250,000 DES 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 several Deep Crack chips. ... LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows use to store Windows user passwords that are less than 15 characters long. ...

Progress in cryptography has made available functions which are believed to actually be "one way" hashes, such as MD5 or SHA-1. These are thought to be impossible to invert in practice. When quality implementations of good cryptographic hash functions are correctly used for authentication, password cracking through decryption can be considered infeasible. A one-way function is a function which is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. ... A hash function is a reproducible method of turning some kind of data into a (relatively) small number that may serve as a digital fingerprint of the data. ... In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. ... The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). ...

Guessing

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.^{[citation needed]} Examples of insecure choices include:

and so on. In computer security, logging (or signing) in and out is the process by which individual access to a computer system is controlled by identification of the user in order to obtain credentials to permit access. ... Significant other Significant Other is the second studio album by Limp Bizkit, released on June 22, 1999. ... A license plate, licence plate, number plate or registration plate (often referred to simply as a plate, or colloquially tag) is a small metal or plastic plate attached to a motor vehicle for official identification purposes. ... The QWERTY Layout QWERTY is the modern-day layout of letters on most English language computer and typewriter keyboards. ... This article is being considered for deletion in accordance with Wikipedias deletion policy. ... The QWERTY Layout QWERTY, (pronounced ) is the most common modern-day keyboard layout on English language computer and typewriter keyboards. ...

Some users even 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.

The determined cracker can easily develop a computer program that accepts personal information about the user being attacked and generates common variations for passwords suggested by that information.

Dictionary attack

A dictionary attack also exploits the tendency of people to choose weak passwords, and is related to the previous attack. Password cracking programs usually come equipped with "dictionaries", or word lists, with thousands or even millions of entries of several kinds, including: 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 a large number of possibilities. ...

The cracking program encrypts each word in the dictionary, and simple modifications of each word, and checks whether any match an encrypted password. This is feasible because the attack can be automated and, on inexpensive modern computers, several thousand possibilities can be tried per second.

Guessing, combined with dictionary attacks, have been repeatedly and consistently demonstrated for several decades to be sufficient to crack perhaps as many as 50% of all account passwords on production systems.

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. The EFFs US$250,000 DES 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 several Deep Crack chips. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...

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. In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... As a non-regulatory agency of the United States Department of Commerce’s Technology Administration, the National Institute of Standards (NIST) develops and promotes measurement, standards, and technology to enhance productivity, facilitate trade, and improve the quality of life. ...

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

In its most basic form, precomputation involves hashing each word in the dictionary (or any search space of candidate passwords) and storing the <plaintext, ciphertext> 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(N^2/3) in which searching for an encrypted password takes time O(N^2/3). The theory has recently been refined into a practical technique, and the online implementation at http://www.md5hashes.com/ achieves impressive results with a database of nearly 1,000,000,000 alphanumeric MD5 hashes. Another example [1] 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. [2]) In computer science, a space-time or time-memory trade-off is a situation where the programmer can reduce memory use at the cost of slower program execution, or can reduce computation time at the cost of increased memory use. ... In complexity theory, computer science, and mathematics the Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... To meet Wikipedias quality standards, the lead section of this article may need to be expanded. ... The LAN Manager was an advanced Network Operating System (NOS) from Microsoft developed in cooperation with 3COM. It is based on the Operating System/2 (OS/2) and NetBEUI protocol similar to its predecessors MS-NET for MS-DOS and Xenix-NET for MS-Xenix. ...

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. Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ... In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. ...

Salting

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. Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ... In cryptography, a salt consists of random bits used as one of the inputs to a key derivation function. ...

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 (sic) 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. Typical hard drives of the mid-1990s. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...

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. Filiation of Unix and Unix-like systems Unix (officially trademarked as UNIXÂ®) is a computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs including Ken Thompson, Dennis Ritchie and Douglas McIlroy. ... It has been suggested that Maintenance OS be merged into this article or section. ...

Even if the attacker has no access to the password database itself, every attacker should also be prevented from being able to use the system itself to check a large number of passwords in a relatively small amount of time. For this reason, many systems include a significant forced delay (a few seconds is generally sufficient) between the entry of the password and returning a result. Also, it is a good policy to (temporarily) lock out an account that has been subjected to 'too many' incorrect password guesses, although this could be exploited to launch a denial of service attack. Too many in this context is frequently taken to be something like more than 3 failed attempts in 90 seconds, or more than a dozen failed attempts in an hour. Another approach is to require a captcha entry to prevent automated attacks as is done by Wikipedia on user logon. A denial-of-service attack (also, DoS attack) is an attack on a computer system or network that causes a loss of service to users, typically the loss of network connectivity and services by consuming the bandwidth of the victim network or overloading the computational resources of the victim system. ... Early CAPTCHAs such as these, generated by the EZ-Gimpy program, were used on Yahoo. ...

It is also imperative to choose good passwords (see password for more information) and a good encryption or hash algorithm that has stood the test of time. AES, SHA-1, and MD5 are common choices. Good implementations, including adequate salt, are also required. Key derivation functions, such as PBKDF2, are hashes that consume relatively large amounts of computer time so as to slow down the rate at which an attacker can test guesses, even if the hashed password is available. This process is known as key strengthening. A password is a form of secret authentication data that is used to control access to a resource. ... In cryptography, the Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the U.S. government. ... The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). ... In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. ... A Key derivation function (or KDF) is a cryptographic hash function which derives one or more secret keys from secret values and/or other known information. ... PBKDF2 (Password-Based Key Derivation Function) is a key derivation function that is part of RSA Laboratories Public-Key Cryptography Standards (PKCS) series, specifically PKCS #5 v2. ... In cryptography, key strengthening or key stretching refer to techniques used to make a weak key such as a password or passphrase stronger, i. ...

However, no amount of effort put into preventing password cracking can be sufficient without a well-designed and well-implemented security policy. The canonical and all too common example of this is the user who leaves their password on a Post-it note stuck to their monitor or under their keyboard. A pad of fan-folded Post-it pop-up notes, shown still glued together A Post-it note (or simply Post-it), invented and manufactured by 3M, is a piece of stationery with a re-adherable strip of adhesive on the back, designed for temporarily attaching notes to documents, computer...

References

External links

Contents

MIX RULES

Background

Principal attack methods

Weak encryption

Guessing

Dictionary attack

Brute force attack

Precomputation

Salting

Early Unix password vulnerability

Prevention

References

External links

See also

Password cracking programs

Contents

MIX RULES GA_googleFillSlot("encyclopedia_square");

Background

Principal attack methods

Weak encryption

Guessing

Dictionary attack

Brute force attack

Precomputation

Salting

Early Unix password vulnerability

Prevention

References

External links

See also

Password cracking programs

MIX RULES