Password hashing - how to upgrade?

Question

There's plenty of discussion on the best algorithm - but what if you're already in production? How do you upgrade without having to reset on the user?

---

EDIT/DISCLAIMER: Although I originally wanted a "quick fix" solution and chose orip's response, I must concede that if security in your application is important enough to be even bothering with this issue, then a quick fix is the wrong mentality and his proposed solution is probably inadequate.

Answer 1

One option is to make your stored hash include an algorithm version number - so you start with algorithm 0 (e.g. MD5) and store

0:ab0123fe 

then when you upgrade to SHA-1, you bump the version number to 1:

1:babababa192df1312 

(no, I know these lengths probably aren't right).

That way you can always tell which version to check against when validating a password. You can invalidate old algorithms just by wiping stored hashes which start with that version number.

If you've already got hashes in production without a version number, just choose a scheme such that you can easily recognise unversioned hashes - for example, using the above scheme of a colon, any hash which doesn't contain a colon must by definition predate the versioning scheme, so can be inferred to be version 0 (or whatever).

Answer 2

A cool way to secure all the existing passwords: use the existing hash as the input for the new, and better, password hash.

So if your existing hashes are straight MD5s, and you plan on moving to some form of PBKDF2 (or bcrypt, or scrypt), then change your password hash to:

PBKDF2( MD5( password ) ) 

You already have the MD5 in your database so all you do is apply PBKDF2 to it.

The reason this works well is that the weaknesses of MD5 vs other hashes (e.g. SHA-*) don't affect password use. For example, its collision vulnerabilities are devastating for digital signatures but they don't affect password hashes. Compared to longer hashes MD5 reduces the hash search-space somewhat with its 128-bit output, but this is insignificant compared to the password search space itself which is much much smaller.

What makes a password hash strong is slowing down (achieved in PBKDF2 by iterations) and a random, long-enough salt - the initial MD5 doesn't adversely affect either of them.

And while you're at it, add a version field to the passwords too.

EDIT: The cryptography StackExchange has an interesting discussion on this method.