Recently I’ve had some interesting conversations about passwords and password policies.
In general I despise password policies, or at least I despise the silly requirements made by most policies. As I wrote in TCS’s recent Better Passwords, Usable Security white paper, “Why do you require your users’ passwords to look as though somebody sneezed on their keyboard? … Is your organization really better protected if you require your users to memorize a new 14-character password every two months? I argue no!”
In the BPUS white paper — which is behind a paywall, and I understand how that means it’s unlikely you’ll ever read it — I argue for three counterintuitive points:
- Password policies should serve your users’ needs, not vice versa.
- Passwords shouldn’t be your sole means of protection.
- Simpler passwords can be better than complex ones.
Beyond these points, it is also important to implement good mechanisms for storing and checking passwords.
Storing passwords: In June of this year there was a flurry of news articles about password leaks, including leaks at LinkedIn, eHarmony, and Last.fm. The LinkedIn leak was especially bad because they didn’t “salt” their stored password hashes. Salting works as follows:
- An authentication system typically stores hashes of passwords, not cleartext passwords themselves. Storing the hash originally made it hard for someone who stole the “password file” to actually obtain the passwords.
- When you type in your password, the authentication system first takes a hash of what you typed in, then compares the hash with what’s stored in the password file. If your hash matches the stored hash, you get access.
- But attackers aren’t dumb. An attacker can create (or obtain) a “rainbow table” containing reverse mappings of hash value to password. For example, the SHA-1 hash of “Peter” is “64ca93f83bb29b51d8cbd6f3e6a8daff2e08d3ec”. A rainbow table would map “64ca93f83bb29b51d8cbd6f3e6a8daff2e08d3ec” back to “Peter”.
- Salt can foil this attack. Salt is random characters that are appended to a password before the hash is taken. So, using the salt “89h29348U#^^928h35″, your password “Peter” would be automatically extended to “Peter89h29348U#^^928h35”, which hashes to “b2d58c2785ada702df68d32744811b1cfccc5f2f”. For large truly-random salts, it is unlikely that a rainbow table already exists for that salt — taking the reverse-mapping option off the table for the attacker.
- Each user is assigned a different set of random characters for generating the salted hash, and these would be stored somewhere in your authentication system. Nathan’s set of random characters would be different from Aaron’s.
- A big win of salt is that it provides compromise independence. Even if an attacker has both the password/hash file and the list of salts for each user, the attacker still has to run a brute-force attack against every cleartext password he wants to obtain.
If you don’t salt your passwords, then anyone who can get access to the leaked file can likely reverse many of the passwords, very easily. This password recovery is especially a problem since many users reuse passwords across sites (I admit that I used to do this on certain sites until fairly recently).
Checking passwords: But it turns out that salt may no longer be solving the world’s password woes. A colleague sent me a link to a post-LeakedIn interview arguing that cryptographic hashes are passé. At first I felt that the interviewee was blowing smoke, and wrote the following observations to my colleague:
He confuses the notion of “strong salt” with “strong hash”.
(A) strong salt: you add a lot of random characters to your password before hashing…as a result the attacker has to run a brute force attack against the hash for a looooong time (many * small effort) in order to crack the password.
(B) strong hash: you use a computationally-intensive function to compute the hash…as a result the attacker has to run a brute force attack against the hash for a looooong time (few * large effort) in order to crack the password.
In both cases you get the desirable “looooong time” property. You can also combine 1 and 2 for an even looooonger time (and in general looooonger is better, though looooong is often long enough).
There can be some problems with approach #2 — the biggest is non-portability of the hash (SHA-1 is supported by pretty much everything; bcrypt isn’t necessarily), another could be remote denial of service attacks against the authentication system (it will have a much higher workload because of the stronger hash algorithm, and if you’re LinkedIn you have to process a lot of authentications per second).
Conclusion: The problem with LinkedIn was the lack of salted passwords.
But I kept thinking about that article, and related posts, and eventually had to eat some of my words (though not all of them). Looooong is often not long enough.
The best discussion I found on the topic was in the RISKS digest, especially this post and its two particularly interesting references.
My point (A) above may be becoming increasingly less valid due to the massive increases in cracking speed made possible by running crackers directly on GPUs. Basically, using a salt + password means that you should be using a large/strong enough salt to evade brute force attacks. So that raises the concern that some people aren’t using a large/strong enough salt.
Beyond salting there are always ways to increase the security of a password-based authentication system. Instead of a stronger hash, you could require users to type 20 character passwords, or you could require two passwords, etc.
But back to my original point, longer or complex passwords aren’t always the best choice. That is especially the case when you have two-factor authentication (or other protection mechanisms) — as long as you use the two factors everywhere. (For example, one company I recently talked with deployed a strong two-factor authentication system for VPN connections but mistakenly left single-factor password authentication enabled on their publicly-accessible webmail server.)