Understanding Password Storage

Over 20 years ago cryptographers figured out how to properly store passwords. They do so in a Hash table. A hashing function takes whatever you enter, regardless of length, and runs it through a formula that produces a fixed length set of characters that appear random. It is impossible to take that hash and reverse the process to find the password.

Hash Tables and salt

Think of it like putting fresh roasted coffee beans into a coffee grinder. You turn the crank (or push a button) and the beans are chopped into many tiny particles. There is no way to put the particles back together and end up with the original beans.

When passwords are hashed properly, they not only use your password, but mix in some other variable like your username as well. This is called, salting the hash. This prevents people from compiling a huge table of passwords and their hashed equivalents, and then doing a reverse lookup on the hash if they manage to steal the hashed passwords.

Hashing algorithms are so well designed, that a small change in the input, produces an entirely different output. So, if you enter:

Enter the Sha1 Hex hash

password =	5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8
Password =	8be3c943b1609fffbfc51aad666d0a04adf83c9d

Notice that we get an entirely different hash by just capitalizing the P in password.

The other thing to notice about hash tables, is that it doesn't matter what you put in. The algorithm just grinds it up and outputs a fixed length seemingly random set of characters. If the hash produces a 40 character hex hash like the one above, and I put in a single letter, I'll get a 40 character hash. If I put in a file with the entire works of Shakespeare, I'll get a 40 character hash.

Clues revealing incompetence

Since it doesn't matter what you put in because everything just gets ground up and turned into a fixed length hash, a website has no reason to restrict your passwords. They may decide on some limit for convenience. For example Google limits passwords to 200 characters, but it will be VERY large. They should not restrict characters.

If a website does not let you enter a long password using any set of characters you'd like, they must have a reason for forcing you to be much less secure than you'd like to be. Why would they force you to have insecure passwords?

For example, Outlook.com restricts you to 16 characters and does not allow symbols! The only reason I can imagine is that they are not hashing your password, but just storing it, and they have a tiny fixed length field in their database. If you come across a site like this, particularly if it is for something significant, like medical records or credit card information, complain. These people are 20 years behind the curve.

Repetitions

The current best practices is to use an excellent hashing algorithm, mix in salt, and then do repetitions. So, if they used 9,000 repetitions, they would take your password, add some salt, and send it through the algorithm 9000 times and then store the result. When you enter your password, they add the salt, and send it through the algorithm 9,000 times and then compare the result. If it is the same, then you put in the right password. With today's computers, you would not even notice the delay 9,000 repetitions produces.

Now, let's imagine someone breaks into the website and steals the password table. Then they begin testing passwords against the table. Imagine that they can test millions of possible passwords every second. Suppose it would take them an hour to break your password without repetitions. With 9,000 repetitions, it would take over a year (1 year is 8,760 hours). If it would have taken them a day, now it is over 24 years! Repetitions are very useful.

Conclusion

Proper password storage takes your password, mixes in some salt, sends it through a hashing algorithm and repeats the process many times, finally storing the result. You cannot reverse the process and run the results through an algorithm to obtain the password. If you are entering a site that should be secure, and they limit your password length to less than 50 characters, or restrict the character set to just numerals and letters, then they are significantly reducing your security. If they understood security, they would not limit your security for no reason. If there is a reason, then they are storing your password insecurely. Either way, they are incompetent.

Date: October 2012

This article is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.