That's really the sad part... technically it's a superior solution to bcrypt/scrypt but the reason why LinkedIn got pwned was because they MD5'd their passwords instead of bcrypt/scrypt.

If I remember correctly they were also not using a salt. They stated that "members whose passwords have not been compromised benefit from the enhanced security we just recently put in place, which includes hashing and salting of our current password databases."[1]

[1] http://blog.linkedin.com/2012/06/06/linkedin-member-password...

It blows me away that nobody at LinkedIn had heard of rainbow tables, or that they didn't think it was THAT important.

You might be surprised how little many companies actually care about security when the fallout is largely externalised (for example users having their gmail compromised because they used the same password for linkedin).

The real question from linkedin's point of view is how many profitable people stopped using the service because they stored the passwords in MD5?

Based on some of the systems I have seen over the years I will say that there is a very strong chance that some company you have bought something from at some point has a copy of your credit card number + CCV2 stored in plaintext in a mysql database somewhere.

The problem is that when you make this mistake early, it's not easy to fix, since you don't have the passwords yourself. Though I guess they could have rainbow-table'd their own password database and migrated everything over to a better scheme, rather than waiting for users to successfully log in.

It's not really that difficult. Let's say you've got a column called 'insecure_pass' that is storing a simple md5 hash of users' passwords.

Four simple steps:

1) You add a new password column to your DB (secure_pass) and modify your account creation / password change code to store bcrypt(md5(password)) in that column in parallel with just md5(password) in the old insecure_pass column.

2) You run a job that migrates insecure_pass to secure_pass by calculating bcrypt(insecure_pass) and storing that in secure_pass.

3) You turn on "dark reads" for secure_pass on login and log if there are any cases where validation against secure_pass failed when validation against insecure_pass succeeded. If a log message shows up, you did something wrong.

4) You move over to "light reads" for secure_pass and stop updating/validating insecure_pass. Once that's deployed, you drop the insecure_pass column from your DB.

That's a really good idea. If you can't protect the passwords, you can at least protect the hashes, with almost no loss of speed or security.

I'm surprised common auth systems don't handle this more elegantly. It's possible to maintain a history of crypt methods and store that with the password data. The system can then keep track of which user records were created with older algorithms, and automatically update them when the user logs in, but not requiring an across-the-board password update. The process is completely transparent to the user.

I believe there are some systems that don't store the crypt methods with the password data, but instead just run through each password method to try to find one that works, then transparently upgrade to the newest.

That may be vulnerable to a timing attack, however.

You could definitely use a timing attack to isolate accounts still using the weak crypto, but the mitigation against that is the same as any time attack mitigation strategy: you configure your auth solution with a return time floor.

I don't see this scenario presenting any more risk from a timing attack vector than a bare implementation using weak crypto, and it offers a balance between having no option to upgrade your crypto algorithm, and an option that involves some trade off.

Possibly. I'm no expert, but it seems like if you were using an incorrect password, you would be running through every old system every time, regardless of if the person had upgraded. The only time you would short-circuit any of the methods would be if you used the right password.

I actually think the originally described system is more vulnerable to a timing attack, since you could determine which crypto system a user's password is using based on the timing.

Alternatively, rehash the passwords on login with the new, safer system.

That's the standard, but all those unused accounts still have vulnerable passwords, which is sub-optimal. (This might not matter for discussion forums or something like that, but consider something like your state's online tax site; something people only view once a year, but something that's very important to keep secure.)

No one bothers with rainbow tables anymore... Why bother with terabytes of storage when you can make billions of guesses per second, on extremely cheap commodity hardware?

That's simply not true. Rainbow tables are still the first choice of many people trying to crack passwords, with brute force or hybrid attacks as a follow up after the common passwords have been found.

It doesn't hurt that there are a lot of rainbow tables available to access for free on the Internet.

Well, I guess our experiences differ. Personally, I find it impractical to push many-terabyte files around, when, for a few bucks, I can effectively regenerate them in a matter of minutes.