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

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.)