Password cracking |
Password cracking is the process of recovering secret passwords from data that has been stored in or transmitted by a computer system, typically, by repeatedly verifying 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), to gain unauthorized access to a system, or as a preventive measure by the system administrator to check for easily crackable passwords.
=Background=
Passwords to access computer systems are usually stored, in some form, in a database in order for the system to perform password verification. To enhance the privacy of passwords, the stored password verification data is generally produced by applying a one-way function to the password, possibly in combination with other available data. For simplicity of 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 verify 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 do this repeatedly with different guesses until a valid match is found, 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. 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 (computing), virus (computer) 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 if a guessed password is correct.
Without the hashed 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 exceed. 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 (computer security), wiretapping, keystroke logging, login spoofing, dumpster diving, Phishing, shoulder surfing, timing attack, acoustic cryptanalysis, identity management system attacks 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 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). However, it must be kept in mind that ciphers used for password protection should have been analyzed for weaknesses extremely thoroughly by cryptographic experts before adoption as a protective measure. Hence this method is unlikely to work if such an examination has been done correctly.
Progress in cryptography has made available functions which are believed to actually be one way function hash function, 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.
==Guessing==
Not surprisingly, many users choose weak passwords, usually one related to themselves in some way. It may be:
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, and 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:
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 up to some size, known as a brute force attack. As the number of possible passwords increases rapidly as the length of the password increases, this method is unlikely to be successful unless the password is relatively small. But how small is too small A common current recommendation 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.
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. Note: This number is far less than what is generally considered to be safe for an encryption key.
Too small thus depends 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 all similar in that the attacker goes through a list of candiate passwords one by one, which list may be explicity 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, 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 or 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.
There exist advanced precomputation methods that are even more effective. By applying a 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. [http://support.microsoft.com/default.aspxscid=KB;EN-US;q299656&])
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 Search_algorithm#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===
The benefits of precomputation and memoization can be nullified by the simple and canonical expedient of randomizing the hashing process. This is known as salt (cryptography). When the user sets a password, a short 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 different for each user, the attacker can no longer use a single encrypted version of each candidate password. If the salt is long enough, the attacker must repeat the encryption of every guess for each user, and this can only be done after obtaining the encrypted password record for that 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 has 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.
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.
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 excellent candidates. 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.
However, no amount of effort put into preventing password cracking can be sufficient without a well-designed and well-implemented security policy. The canonical, appalling, 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. Even sophisticated users who have been warned repeatedly are known to have such lapses.
=Password cracking programs=
=References=
= External links =
=See also=
|
|