Password cracking
|
|
Password cracking is the process of recovering secret passwords stored in a computer system. 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.
| Contents |
Background
Passwords to access computer systems are usually stored in an encrypted or hashed form in a central database, along with the user name and system wide security policies for a specific user (such as the user's home directory, initial configuration preferences, etc). Such databases often do not store the password in any form (encrypted or otherwise), but rather use it as (or to generate) a key used to encrypt some data (eg, a string of 10 0s).
Techniques
There are many ways of obtaining passwords illicitly, such as social engineering, wiretapping, keystroke logging, login spoofing, dumpster diving, phishing, shoulder surfing, timing attack, acoustic cryptanalysis and compromising host security (see password for details). However, these methods are usually not considered actual password cracking. The term is typically limited to recovery of one or more plaintext passwords from the encrypted or otherwise secured version stored on a computer. Password cracking requires that an attacker can gain access to the encrypted password, either by reading the password storage file somehow (e.g., via a Trojan Horse, virus program, or social engineering) or intercepting the encrypted password sent over an open network, or has some other way to rapidly and without limit test if a guessed password is correct.
Decryption
This is the most obvious method, and the only one that can be applied even to 'well-chosen' passwords which are stored in encrypted form. The attacker attempts to decrypt the password by exploiting some cryptographic weakness in the encryption algorithm. Decryption need not be a quick operation, conducted while 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" hashes, such as MD5 or SHA-1. These are thought to be impossible to invert in practice. (The procedure for authentication using them would be 'hash' the password again and check whether it matches the stored hash produced from the original password.) When quality implementations of good one-way 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:
- blank
- the word 'password'
- the user's name or login name
- the name of their significiant other or another relative
- their birthplace or date of birth
- a pet's name
- and so on, or
- a simple modification of one of the preceding, such as suffixing a digit or reversing the order of the letters.
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 usually had higher access privileges than a normal user account).
Such passwords are easily guessable by the determined cracker. Guessing is the most successful method of password cracking.
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, of several kinds:
- words in various languages
- names of people
- places
- commonly used passwords
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. Since 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 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, perhaps much 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 not by much. Too small depends on an attacker's resources (eg, available time, computing power, etc) and will increase as computers get faster. Passwords encrypted using the outdated DES cipher can be quickly broken in this way with specialized hardware (or, as of the EFF's successful attack, in several weeks using zero-cost idle time on a cluster of computers).
A brute force attack might be more effective against a poorly designed encryption algorithm. So, for example, if the algorithm uses a small "keyspace", such as by truncating the password to the first 6 characters to decrease response delays when changing passwords, it might be feasible to exhaust all possible passwords in a reasonable time on readily affordable hardware.
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.
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 are also required.
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 appalling, example of this is an unsophisticated user who leaves their password on a Post-It note stuck to their monitor because they had never been told not to do so.
Password cracking programs
Advanced topics
Salting
When the attacker has several encrypted passwords to crack rather than just one, it is possible to improve the efficiency of the dictionary attack. 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 one by one.
To reduce the chance of success, a technique known as salting is often used. When the user sets a password, a short string (usually two characters in length) 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 dictionary word: the encryption algorithm must be repeated for each user as well. Thus the amortization technique described above is of no use unless several thousand passwords are being cracked at once.
References
- Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off. (http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf) CRYPTO 2003: pp617–630