Password Attacks and Countermeasures

As we indicated in the Authentication, Single Sign-On and Federation web page, passwords are the most widely used method of authentication because they are easy and inexpensive to implement compared to other methods. So, malicious individuals intent on breaking into systems have spent a lot of time devising ways to uncover the passwords associated with user accounts on the systems that they target. We know that many times passwords are exposed because of human error, such as responding with a valid ID and password to a phishing attempt, sharing passwords, writing them down and storing them in full view, giving away answers to security questions through social media sites, etc.

But what if a malicious individual wants to troll for passwords of total strangers on random systems across the Internet? He or she would probably use a variety of password cracking techniques that are described in this section.    

Manual brute force

One method of cracking someone's password would be to log in manually with a series of test passwords. To speed up the process, one could try to log in with a list of passwords using an automated login program but he or she still would only get to try no more than one password every few seconds. If a target system is configured to disable accounts after a certain number of failed login attempts, the success of such an approach is significantly diminished. But even if accounts are not disabled after a number of unsuccessful attempts, this approach can only be successful in cases where the computer account holder uses a fairly obvious password, a default password that comes with a specific product, a blank password or a password that someone knowing the individual could guess.

Uncovering passwords through their "hash" values

Passwords are not usually stored on systems is a readable, clear text form. Rather, the system stores a "hash" of each password that it creates by passing the password through an algorithm that creates a corresponding unique hash value. Because these hash values cannot be used by a reverse algorithm to restore its original value, these hashes are often referred to as "one-way hashes", but for brevity, we will stay with the shorter term "hash". When the user logs in with a readable, clear text password, the entered password is run through the same hashing function and is authenticated against the stored one-way hash for that user.

When manual brute force fails, determined attackers will attempt to break into a target system to download its user names and password hash values. To gain that level of access, a malicious individual would need to compromise the system either via malware or the knowledge of the password of an administrator on the target system. Once they have a file of the target system's user names and password hash values, they use a password cracking program that generally relies on one of the two techniques described below.   

Hackers' dictionaries

"Hackers' dictionaries" are collections of passwords that are common, equal to a single dictionary word or a minor variations of either, matched with their corresponding password hashes. The records in these files are normally sorted by password hash value. The idea is that, once a hash is found in the hackers' dictionary that matches the password hash you are trying to crack, the clear text password associated with the hash can be determined. Searching for a password hash in a hackers' dictionary sequentially from record one would take a great deal of time, since these dictionaries can hold millions of entries. So, to speed up the process, password cracking software typically uses a "binary search" technique that involves the repeated halving of the hackers' dictionary file until a matching password hash is found. Here is how a search would proceed:

1. The password hash value in the first record of the target system's user table is used as the "test value"
2. A work dictionary recordset is created containing all the records in the hackers' dictionary sorted by password hash value
3. The test value is compared to the hash value in the middle record of the work dictionary recordset
4. If the test value is equal to the hash value in the middle work dictionary record, then you have found the hash and its associated clear-text password, the password cracking software would save the clear-text password with its associated user name for later use.  Proceed to step 9
5. If there is only one record left in the work dictionary record set and the test value does not match the hash in the remaining work dictionary record, the user's password value does not exist in the hackers' dictionary so that user name is safe - it cannot be used to access the system.  Proceed to step 9
6. If the test value is higher than the hash in the middle work dictionary record, the middle work dictionary record and all records before it are eliminated from the work dictionary recordset
7. If the test value is lower than the hash in the middle work dictionary record, the middle work dictionary record and all records after it are eliminated from the work dictionary recordset
8. Proceed to step 3
9. The password hash in the next sequential record in the user table then becomes the test value and the process continues at step 2 until there are no more records in the user table

Rainbow tables

The hackers' dictionary approach is very effective in finding commonly used passwords, single dictionary word passwords and simple variations. However, they are not effective when one wants to crack any password of a certain length, for example, eight character passwords. A dictionary of all possible eight character passwords would require enormous amounts of storage. To address this, a technique emerged using a specialized file called a "rainbow table".  Each rainbow table record might look like a hackers' dictionary record - they both have a clear text password value and an associated password hash, but in actuality they are very different. Unlike a hackers' dictionary record where each record's password hash is stored with its associated clear text password, each record in a rainbow table represents a "chain" of potentially hundreds of thousands of passwords that will be referenced by the final hash value in the record during the search function. So, the size of the table is only a small fraction of the size of an equivalent hackers' dictionary file.

For example, let's assume that someone wants to use a rainbow table to uncover eight character passwords, and each row of our rainbow table can represent 100,000 passwords. The rainbow tables would typically be created in the following manner:

1. An initial clear text password value is selected
2. The clear text password is hashed
3. The hash value is "reduced", i.e., in this case, eight characters are extracted from the hash to create the next clear text password in the chain
4. Steps 2 and 3 are repeated until they have been performed 100,000 times
5. The last hash is the value that is stored in the record along with the initial clear text password

Once the rainbow table is available, finding the clear text password for a hash you are trying to crack ("test value") involves the following steps,

1. Search for the test value among the rainbow table's hashes
2. If it is not found:
1. If the initial clear text password has not been reduced and hashed 100,000 times, reduce the hash to create the next password in the chain and then hash it to create the next test value and proceed to step 1
2. Otherwise, the password associated with the hash you are trying to crack is not represented in the rainbow table
3. If it is found:
1. Take the clear text password value in the record that has the matching hash. We'll call that the chained password value.
2. Hash the chained password value
3. If the resulting hash matches the test value you are trying to crack, then the current chained password value is the password you are looking for
4. If not, reduce the resulting hash to obtain the next chained password value using the standard reduction function used when the rainbow table was created
5. Go back to step 3.2 until the matching hash values match

Building a rainbow table that can cover all possible password values is a very complex exercise, so while most of us would be challenged to create a comprehensive rainbow table, no one needs to. To our knowledge, rainbow tables currently exist for passwords of up to ten character passwords in length. Since each additional character that is added to the password length geometrically increases the complexity, storage and processing power requirements for rainbow table processing, generating tables for larger passwords will take some time, but we have no doubt that eventually some one or some organization with enough resources will increase rainbow table coverage.

Increasing our resistance to automated password cracking

The risk of falling victim to one of the above techniques can be reduced, but only if we all work together to do so by taking the following actions:

1. Remember that hackers' dictionaries and rainbow tables must recognize the hash of your password to successfully crack it. The hacking community does not have every possible password hashed, so the key to not falling prey to a dictionary or rainbow table attack is to ensure that you do not use passwords that would be common enough or short enough (10 characters or less) to end up in a hackers' dictionary or rainbow table. To stay ahead of the curve, having passwords of twelve characters or more in length will help to keep your password safe against these types of attacks.  
2. System administrators should configure systems to use "salt" in the hashing process. Applying a salt value to the password hashing process results in totally different hashes being generated. That would mean that any hackers' dictionary or rainbow table that is based on no salt or a different salt value would be rendered useless to someone trying to crack our passwords.
3. We must do all we can to prevent a malicious individual from downloading password hashes from our systems, i.e., strong anti-virus protection, timely software updates, strong passwords especially for administrator accounts, etc.
4. System designers should consider incorporating more than one factor to authenticate users, i.e., what you know (a password/PIN), what you have (a physical token), what you are (biometrics).

 Sadly, even today, the most common password is the word "password".  Please visit the Password Security page for tips on creating strong passwords.