[riquito]

AFAIK you store the hash along the algorithm/parameters you used to generate it. To update the hash you wait for the user to log in and...

1. check if the stored hash is identical to the hash you generate on fly using the old algorithm

2. create a new hash using the new algorithm and substitute both the old hash and the old informations about the algorithm/parameters

What's the trivial way to achieve it without the user logging in?

[kijin]

GP might be thinking of cases where the Nth iteration of the hash is only based on the salt and the result of the N-1st iteration, rather than on the original passphrase.

I'm not aware of any currently recommended algorithm that does this, though. The original passphrase usually goes into each and every iteration, not just the first round.

[mankyd]

Hash your existing hash with a more powerful algorithm.

[nly]

Exactly, it's hacky, but Scrypt'ing your ancient MD5 databases is better than sitting on your ass and being caught with your pants down when your database gets dumped on pastebin or a Russian forum