security - How to phase out a password hashing algorithm in an existing web application? -

Many people are about password in web applications, but I am facing a different problem. I know that on which I am currently working, is not safely enough (just sha1 without salt or anything), but all this change it It is difficult to suddenly.

I have to find a way to implement a new algorithm for all (± 50.000) users. I was thinking about some solutions, but none of them speaks right.

1) Adding a second column to the user table with a new password Every time when the user is authenticated, I store the password with my new hash and throw the old one. In this exercise this will mean that it will take years before sha1 steps.

1.1), but encourage users to log back into our system for a security update, but in reality it seems that accepting a (former) security vulnerability This is not for my management choice.

2) Re-authenticate all users and throw all passwords. It is very harsh, and there is also a pain for the users behind.

How do you cope with this problem?

You can extend your existing solution as the input to your new Advanced hash implementation sha1 hashes By using, where you can add salt etc. The new solution will also include shadow phase + whatever may be improved.

In this way you can calculate that you already have a new one from hash, but also improve the solution.