Cryptography for Mere Mortals #8
An occasional feature, Cryptography for Mere Mortals attempts to provide clear, accessible answers to questions about cryptography for those who are not cryptographers or mathematicians.
Q: Follow-on to Cryptography for Mere Mortals #7: How can cryptographic hashes be used to protect passwords?
A: By cryptographically hashing the passwords when they’re stored, then hashing the user’s input when she tries to log on, and comparing that against the hash.
This is a typical use of cryptographic hashes: to create a reference to something as a reasonably short value. You can then expose this value without exposing the original data. Thus many operating systems store passwords as hashed values. When you enter your password, the value you type is hashed and compared against the stored hash. If they match, you’re validated. This avoids having to ever store un-hashed passwords, and the stored hashes are not immediately useful to an intruder.
Hashes are also not reversible—that is, you cannot directly convert a hash back into the original data. (This is obvious when you think about collisions—how would the algorithm decide which of the collisions to un-hash the value to?) Non-reversibility is one of the things that makes hashes particularly valuable for security usage.
So how can hashes be “cracked”, since a hashed value cannot be reversed to get the original text? Simple: by comparing a list of hashed values for common words against the hash. This is like looking for fingerprints gathered at the scene of a crime: if you have hash value x, you look through your table of known hashes. If you find x, you know that it must (or almost must, anyway, modulo a possible collision—remember that hash collisions are rare!) be a hash of the matching value in your table.
However, if the hashed value is “salted”—that is, further modified using another, related value (such as the username)—then the hash will no longer match the value in the table. Of course if the related value is known, a table of comparison hashes can be created and searched; but if, for example, the userid is the salt—user ABC’s hash value is salted using “ABC” and user XYZ’s hash value is salted using “XYZ”—then the attacker has to regenerate the lookup table for every username. This quickly becomes impractical as a way to attack a mass of hashed passwords, although for a serious attacker attempting to crack a single password, it might be feasible—assuming that the attacker knows that the salt is the username.
The above is why LinkedIn was pilloried for their June 2012 breach: because the passwords weren’t salted, any of the commonly available tables of hashed values could be used against the stolen hashes to find the actual values for those users using weak passwords. And this is why your IT department wants you to have a mixture of upper and lower case, a number, and a non-alphanumeric character in your password: to make it harder to crack in the event of a breach.
Salting a hash isn’t difficult, and has been standard practice for quite some time. LinkedIn should have known better!