How to upgrade a password storage scheme (change hashing-algorithm)

First, add a field to the DB to identify whether or not the password is using MD5 or the new algorithm.

For all passwords still using MD5:

-- In the login process, where you verify a user's entered password: temporarily store the user's submitted password in memory (no security issue here, as it is already in memory somewhere) and do the usual MD5 hash & compare with the stored hash;

-- If the correct password was given (matches the existing hash), run the temporarily stored password through the new algorithm, store that value, update the new field to identify that this password has been updated to the new algorithm.

(Of course you would just use the new algorithm for any new users/new passwords.)

I'm not entirely sure about this option, since I'm not an expert on cryptography. Please correct me if I'm wrong at some point here!

I think Dave P. has clearly the best option.

... but. There is an automagic solution - hash the older hashes themselves. That is, take the current hashes, and hash them again with a stronger algorithm. Notice that as far as I understand, you don't get any added security from hash length here, only the added cryptographical complexity of the new algorithm.

The problem is, of course, that checking a password would then have to go through both hashes. And you'd have to do the same for evey new password as well. Which is, well, pretty much silly. Unless you want to use a similar scheme like Dave P. explained to eventually graduate back to single-hashed passwords with the new hashing algorithm... in which case, why even bother with this? (Granted, you might use it in a flashy "Improved security for all passwords, applied immediately!"-way at a presentation to corporate suits, with a relatively straight face...)

Still, it's an option that can be applied immediately to all current passwords, without any gradual migration phase.

But boy, oh boy, is someone going to have a good laugh looking at that code later on! :)

Add passwordChange datetime field to the database.

All password set before day X, check using MD5

All passwords set after day X, check using BCrypt or whatever.