Password Koolaid Part I

A lot of time and effort is spent on making sure an organization has a strong password policy. This is usually so that if an attacker gains access to the encrypted hashes of a password, that the password will no longer be valid by the time he or she cracks the hash.

I would like to explain password hashes because this is where the password is stored, though not in a recoverable way. On modern computing systems, if my password is P@ssword! it is not stored on the system as P@ssw0rd!, but something like 8a24367a1f46c141048752f2d5bbd14b. The "hash" is the outcome of a mathematical operation on data. In this case the hash above is the MD5 sum of P@ssw0rd!. The advantage of MD5 for storing passwords is that it is easy to change P@ssw0rd! into 8a24367a1f46c141048752f2d5bbd14b, but almost mathematically infeasible to get P@ssw0rd! from the hash. This is called "a one way hash". The advantage of storing passwords in hashes is that the actual password is not available for viewing on the system--when the system receives the password from a login attempt, it merely runs the hash algorithm and sees if the output matches. If it matches access is granted.

Even a very similar password will be hashed to a completely different output. Here is the output for P@ssword! (I replaced the "0" with the letter "o"):

32e0db0d97366631d8f1203e1ec94ccf

Let's compare the two:

P@ssw0rd!: 8a24367a1f46c141048752f2d5bbd14b
P@ssword!: 32e0db0d97366631d8f1203e1ec94ccf

Only two characters occur in the same position; there is no pattern which an attacker can use to make his guessing easier! Because of this, the only practical way to get the password from a hash is to try every combination of characters until the hashes come out the same. This can take a lot of time, especially if the password is long. The length of time to "crack" a password hash is related to the possible combinations of characters. That in turn is based on the number of possible characters raised to power of the length of the password in characters. For example, an ATM card typically has a four digit PIN. Each of the spaces can contain a number between 0 and 9, which gives 10,000 possible combinations (10*10*10*10). That is not very large though, a modern computer system could guess the PIN on seconds if the hashes were available. But what if we allow upper and lower case letter along with spaces? That would provide for 53 (2*26+space) to the power of the length of a password. So an 8 character password would mean there are 62,259,690,411,361, or over 62 trillion combinations. If we add in characters the possibilities increase, well, exponentially.

This is why password policies usually include a minimum length for the password, what characters are required for the password and for how long the password will be valid. The first and second parameters are to make the password more difficult to guess by increasing the possible combinations of characters, and the last--when the password expires--is so that before the attacker can feasibly guess the password, it is already invalid and useless for gaining access.

While all these are useful and do make a password theoretically more difficult to guess, many individual users comply with the policy but in effect defeat the purpose of the policy and make passwords much easier to guess. For instance, the password above--P@ssw0rd! can be strictly in compliance yet insecure because it is guessable even if the password is periodically changed. The following passwords are also valid and related to the original password:

p@ssword!
passw0Rd!
Pa55w0rd!
P@ssw0rd@

etc. etc.

What is happening is this; our user does not want to remember long, complex passwords because he has other things to do. So he creates a compliant password and when he is forced to change the password he makes a trivial change instead of a completely new compliant password. The problem is all the passwords are based on the English word "password", so if our attacker is minimally competent his password cracking software will try all these combinations when his word list reaches "password"--actually one of the first guesses. If his password was something like JhshI((77636jj, (hash=fbea20ddb6ec43e691bef34eb5d6325f) he will probably write it down on a piece of paper on his desk. And if we assume that the password is forced to change every 90 days, we have basically the same password for almost a full year. This is much more "doable" from a password cracking point of view.

So, we have a lot of audits and policies to make sure our passwords are hard to guess, but how much security does that actually buy us? It is my contention that much of the effort in making passwords complex consumes resources better used to make the actual information which interests attackers harder to obtain. The password complexity policies can take us only so far, and in fact they can be bypassed in most situations. So what should we do for passwords?

That is for Part II