The problem of how to migrate password hashes has kept many using old algorithms, or unsalted algorithms. Many admins think about it for a second, and conclude they must wait for users to login to update stored password hashes, as they don't have the plaintext password in the database to rehash. NO - This is not true.
While considering how to do it, I came up with a simple, elegant, and secure way to do it. I am SURE it has been done before, but I have never seen it described, so thought it might be useful to someone.
The idea is simple: HASH the HASH. That's right, hash the hash. Of course, you'll want to salt both too, but I'm trying to be simple for the sake of discussion.
Say for instance I initially stored my passwords using SHA1 (again, ignoring salting for ease of discussion), and wanted to update to SHA2-512. Well, I could wait for users to log in, the ones that did, and let them slowly get updated, OR I could update them ALL AT ONCE by re-hasing the SHA1 hash with SHA2-512.
So, if the original algorithm was:
The new algorithm would be, hashing the hash:
This allows for INSTANT updating of the ENTIRE database. As an added benefit, it increase complexity and uniqueness of the hash, making your system more secure - as there aren't rainbow tables for combined hash formats.
On user login, of course, you simply run the password through SHA2-512(SHA1(password)).
Now, in practice, you'll want to use SALTing. So, it would really look like:
The beauty of this is not only can you INSTANTLY improve your database's password storage security, but you can also take it as far as you want. And the farther you take it, the longer brute force takes, assuming the attacker even figures out the sequence of algorithms you used. Later, for instance, I might add RIPEMD to the mix.
I would recommend sticking to digests no smaller than 512 bits, just to be safe.
Easy? Eh? Sometimes the most simple things are glossed over though, so I wanted to mention it. While considering it, this seemed the ONLY way to do it like I wanted, and it has additional benefits to. Elegant, I think. I'm SURE I'm not the first to do this, but I've commented on it at security forums the last week, and nobody seems to have done it before, surprisingly ;o.