How to upgrade a password storage scheme (change hashing-algorithm)

Question

I've been asked to implement some changes/updates to an intranet-site; make it 'future proof' as they call it.

We found that the passwords are hashed using the MD5 algorithm. (the system has been around since 2001 so it was adequate at time).
We would now like to upgrade the hashing-algorithm to a stronger one (BCrypt-hash or SHA-256).

We obviously do not know the plaintext-passwords and creating a new password for the userbase is not an option^*).

So, my question is:

What is the accepted way to change hashing-algorithm without having access to the plaintext passwords?
The best solution would be a solution that is entirely 'behind the scenes'.

_{*) we tried; tried to convince them, we used the argument of 'password age', tried to bribe them with coffee, tried to bribe them with cake, etc. etc. But it is not an option.}

Update
I was hoping for some sort of automagic solution for solving the problem, but apparently there are no other options than just 'wait for the user to log in, then convert'.

Well, at least now I now there is no other solution available.

Answer 1

Add passwordChange datetime field to the database.

All password set before day X, check using MD5

All passwords set after day X, check using BCrypt or whatever.

Answer 2

You could store, either in the hash field itself (e.g. "MD5:d41d8cd98f00b204e9800998ecf8427e") or in another column, which algorithm was used to create that hash. Then you'd have to modify the login process to use the correct algorithm when checking the password. Naturally, any new passwords will be hashed using the new algorithm. Hopefully, passwords eventually expire, and over time all of the MD5 hashes will be phased out.

Answer 3

Since you don't know plaintext password, maybe you should to create a field which indicates encription version (like PasswordVersion bit default 0)

Next time user tries to log in, check hashed password using current algorithm version, just like you do today. If it matches, hash it again and update PasswordVersion field.

Hopefully you'll not need a PasswordVersion column bigger than bit. =)

Answer 4

First, add a field to the DB to identify whether or not the password is using MD5 or the new algorithm.

For all passwords still using MD5:

-- In the login process, where you verify a user's entered password: temporarily store the user's submitted password in memory (no security issue here, as it is already in memory somewhere) and do the usual MD5 hash & compare with the stored hash;

-- If the correct password was given (matches the existing hash), run the temporarily stored password through the new algorithm, store that value, update the new field to identify that this password has been updated to the new algorithm.

(Of course you would just use the new algorithm for any new users/new passwords.)

Answer 5

You should change your password database to store 3 items:

1. An algorithm identifier.
2. A random salt string chosen by the server when it first computes and stores the password hash.
3. The hash of the concatenation of salt+password using the specified algorithm.

Of course these could just be stored together in one text field with a delimiter:

"SHA256:this-is-salt:this-is-hash-value"

Now convert you existing entries to a value with empty salt and the old algorithm

"MD5::this-is-the-old-md5-hash-without-salt"

Now you have enough information to verify all you existing password entries, but you can also verify new entries (since you know which hash function was used). You can convert the old entries to the new algorithm the next time the existing users login since you will have their password available during this process:

1. If your database indicates they are using the old algorithm with no salt, first verify the password the old way by checking that the MD5 hash of the password matches. If not, reject the login.
2. If the password was verified, have the server choose a random salt string, compute the SHA256 hash of the salt+password, and replace the password table entry with a new one specifiy the new algorithm, salt and hash.
3. When the user logs in again, you'll see they are using the new algorithm, so compute the hash of the salt+password and check that it matches the stored hash.

Eventually, after this system has been running for a suitable time, you can disable accounts that haven't been converted (if desired).

The addition of a random salt string unique to each entry makes this scheme much more resistent to dictionary attacks using rainbow tables.

Answer 6

I'm not entirely sure about this option, since I'm not an expert on cryptography. Please correct me if I'm wrong at some point here!

I think Dave P. has clearly the best option.

... but. There is an automagic solution - hash the older hashes themselves. That is, take the current hashes, and hash them again with a stronger algorithm. Notice that as far as I understand, you don't get any added security from hash length here, only the added cryptographical complexity of the new algorithm.

The problem is, of course, that checking a password would then have to go through both hashes. And you'd have to do the same for evey new password as well. Which is, well, pretty much silly. Unless you want to use a similar scheme like Dave P. explained to eventually graduate back to single-hashed passwords with the new hashing algorithm... in which case, why even bother with this? (Granted, you might use it in a flashy "Improved security for all passwords, applied immediately!"-way at a presentation to corporate suits, with a relatively straight face...)

Still, it's an option that can be applied immediately to all current passwords, without any gradual migration phase.

But boy, oh boy, is someone going to have a good laugh looking at that code later on! :)