One way to fix your rubbish password database

Suppose for a moment that you are running a web site that has a poorly implemented password database that stores password hashes using something like SHA1(password) or MD5(password) or versions of that with some salt.  (This is what LinkedIn, last.fm and eHarmony were all doing and undoubtedly many, many other companies are in the same position).

And suppose you realize that if your password database gets disclosed your users are in danger and you'd really like to change the system used to something much more secure like bcrypt or scrypt.

Here's how you can do that in one go and secure your password database.

1. Suppose you have a database that contains password hashes for the n users of your site, and for each user you have salt s_i and hash h_i (where h_i was computed with some algorithm such as SHA1 or MD5).  (Note that the rest of these instructions work if there's no salt, just ignore it).

2. Suppose that you've chosen to use scrypt.  For each user you first create a new random salt value s^'_i and then compute a new hash h^'_i using the formula scrypt(s^'_i, h_i) and store the new salt and hash in the database.  You throw away the old weak hash h_i and forget it ever existed. So you are left with two salt values and a new hash.  (I've ignored the other scrypt parameters which are left to the reader to determine).

3. When user i logs in and presents password p you use your old weak hash algorithm (let's suppose it was md5(salt, password)) to compute a hash for comparison as follows: scrypt(s^'_i,  md5(s_i, p)) and compare that with the h^'_i stored in the database.

4. If, like last.fm, you were also allowing third-parties to authorize users by presenting the old hash value instead of the password then you can still use this scheme.  When the third-party presents hash h for user i you calculate scrypt(s^'_i,  h) and do the comparison.

5. If step 4 is not needed then you can go further when a user logs in.  Once the user has logged in successfully with password p you can completely eliminate any trace of the old weak hash by choosing a new random salt value s^''_i and computing scrypt(s^''_i,  p) and storing that in the database.

This has the effect of immediately making your password database more secure if stolen without any effort on the part of your users.