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.)