Randolph West has some ideas about how to remove some of the pain of changing your hashing algorithm for passwords:
Let’s assume that you have inherited a database which stores passwords in cleartext in a column called
Password. This is not a good scenario. For one thing, it is a temptation to access information we wouldn’t normally have access to, by using that person’s credentials. For another, due to a human trait called “using a computer,” people reuse passwords all the time. I do it myself and I’m writing a post about security (out of 1,089 items in my 1Password vault, 82 items contain reused passwords).
Randolph has a few ideas, but there’s one which I put into place a long time ago: automatic migration. A system was MD5 (it was a while ago) and I changed it to a better password-hashing algorithm. If the existing user record had a binary the length of an MD5 hash, I’d perform the lookup (to ensure that this was the correct user) and then re-hash using my new algorithm, which had a longer binary length. Over time, people migrated to the new system without any issue. Eventually, when the set of remaining users was small enough, we took more active measures. It wasn’t quite as good as the ideal of forcing resets on everyone, but that was deemed as going overboard for our user base.