Password Cracking Background Techniques Decryption

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).

2 Techniques

There are several ways of obtaining passwords illicitly, such as social engineering, wiretapping, keystroke logging, login spoofing, dumpster diving, phishing, shoulder surfing 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. This use of the term assumes an attacker already has access to the encrypted password, by for example reading the password storage file somehow (e.g., via a Trojan Horse or virus program, or some social engineering, etc.)

2.1 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 attackIn cryptanalysis, a brute force attack is a brute-force search of the 'key space' (i. all possible keys) in an attempt to recover the plaintext used to produce a particular ciphertext. Note that, in most cases, recovery of the plaintext in this way is not (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. ProprietarySomething proprietary is something exclusively owned by someone, often with connotations that it is exclusive and cannot be used by other parties without negotiations. It may specifically mean that something is covered by one or more patents, as in propri encryption algorithms which rely on obscurityIn cryptography and computer security, security through obscurity (sometimes security by obscurity is a controversial principle in security engineering, which attempts to use secrecy (of design, implementation, etc. to ensure security''. A system relying for security are much more likely to succumb to such attacks.

Progress in cryptography has made available functions which are believed to actually be " one wayA 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. The precise meanings of "easy" and "hard" can be specified mathematically. With rare exceptions, almo" hashesA hash function is a function that converts an input from a (typically) large domain into an output in a (typically) smaller range (the hash value often a subset of the integers). Hash functions vary in the domain of their inputs and the range of their ou, 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.

2.2 Guessing

Not surprisingly, many users choose weak passwords, usually one related to themselves in some way. It may be:

the user's name or login name
the name of their spouse 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.

2.3 Dictionary attack

This 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.

2.4 Brute force attack

A last resort is to try every possible password. 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.

3 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 (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.

4 Password cracking programs

5 Advanced topics

5.1 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.

6 References

Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off. CRYPTO 2003: pp617–630

7 See also

Cryptographic key length

Cryptographic attacks

<Hide>

Home > Password cracking

1 Background