To increase the work factor, there are three approaches you could take:
Rehash all passwords immediately, continue the same hash
Take the hash currently stored in the password file, and hash it a few more times.
We may (see below) be able to do this immediately with every entry in the password file.
Example: let's switch from a work factor of 10 (i.e., hashed 2^10 times) to the same hash function with a work factor of 11 (hashed 2^11 times).
To do that, we pull the old hash value from the password file -- that has already been hashed 2^10 times -- and use the same salt to hash it another 2^10 times to create the new hash value, and replace the old hash with the new hash.
Then we somehow tell the "login" program and the "passwd" program (or the equivalent), instead of using a work factor of 10, they now need to use a work factor of 11.
See "Is it possible to increase the cost of BCrypt or PBKDF2 when its already calculated and without the original password?"
for more discussion of this approach.
Alas, in some cases you can't simply "continue" to hash like this -- say, you want to switch to a completely different hash algorithm, or you want to change the salt,
or your current hash function has a "setup" or "finalize" step that interferes with "continuing" to hash like this.
Rehash all passwords immediately, without continuing the old hash
Take the hash currently stored in the password file, and hash it a few more times.
We can do this immediately with every entry in the password file.
Example: let's switch from MD5 (hashed once) with a 3-character salt, to bcrypt with a work factor of 11 (i.e., hashed 2^11 times) and a fresh 32-character salt.
To do that, we pull the old hash value from the password file, and replace it with a new hash value:
new_hash = bcrypt( old_hash, new_salt, work-factor=11 ).
Then we somehow tell the "login" program and the "passwd" program (or the equivalent) to use this somewhat awkward hash function:
bcrypt( MD5( password, old_salt ), new_secure_salt, work-factor=11 )
See
" Is this password migration strategy secure? "
for more discussion of this approach.
Rehash passwords one at a time, as people log in
Many UNIX-like systems are already set up so the sysadmin can change the "preferred" password algorithm, work factor, and salt length at any time.
Later, whenever a user logs in by typing their password, the system updates that user's row in the passwd file to use the system's current "preferred" work factor etc.
See a, b, c, d, e, f, g, h, i, j, k, L, m, n, o for how to tweaking the appropriate configuration file in order to set the "preferred" algorithm etc.
Typically this involves pluggable authentication modules (PAM).
Many passwd files (or thier equivalent) store, for each user,
not only the the salted hash,
but also the user-unique salt, the ID of the hashing algorithm used, and the work factor
(often dollar-sign delimited).
That allows us to gradually switch to a completely different password hash algorithm and salt width.
details:
For example, let's say we want to switch from inadequate amounts of salt and some obsolete hash to bcrypt with a work factor of 11.
The sysadmin sets the "preferred" algorithm, salt, etc. to "bcrypt with a work factor of 11", etc.
The next time a user logs in, resets their password, or changes to a new password -- i.e., uses the login or passwd programs -- those programs:
1) Hold on to the plaintext password the user typed in for a few moments.
2) Check the passwd file to see if that user's hash already uses the latest algorithm, work factor, and salt width. If so, continue with 4.
3) Authenticate the user with whatever old, obsolete algorithm the passwd file indicates for that user. If successful, additionally create a unique new salt with the latest salt width.
Run that salt, and the plaintext password that we're still holding on to, through "bcrypt with a work factor of 11" (or whatever today's preferred algorithm is) to get the new hash.
Update the passwd file for that user with the new hashing algorithm ID, the new work factor, the new salt, and the new hash.
4) Authenticate the user with the shiny new algorithm the passwd file indicates -- the latest algorithm, work factor, and salt width.
5) Then the server must forget the plaintext password.
After a month or two, if some rows of the passwd file still indicate some old, obsolete hashing algorithm and work factor -- i.e., those users haven't logged in for a month or two since you made the change -- you might send them a mail or call them on the phone and ask them nicely to log in soon.
After a few months, if there's still some user whose row of the passwd file still indicate some obsolete algorithm -- i.e., that user hasn't logged in for months -- perhaps you could reset that password and generate a new random unguessable password, more-or-less the same as if that user had forgotten the password and gone through the normal "I forgot my password" process.
If the user ever comes back, go through the normal "I forgot my password" process again to reset the password back to whatever the user wants to use.
See "Migrate old md5 passwords to bcrypt passwords"
for more discussion of this approach.
further discussion
"How to upgrade a password storage scheme (change hashing-algorithm)"
has some discussion of both the "Rehash all passwords immediately, without continuing the old hash" and the "Rehash passwords one at a time" options.
All of the above approaches have the advantage that your users can continue to use the same password -- it's a "transparent upgrade".
Alas, that means they all have the same flaw:
If any of your users was using a short or otherwise easy-to-guess password,
and then the bad guys somehow get their hands on old server backup tapes (you do make backups, right?) that contain the old, easy-to-crack hashes,
then the bad guys could use one of several infamous utilities to discover those easy-to-guess passwords -- passwords which will still work just fine after any of the above approaches.
The knee-jerk response of some system admins is to force your users to change their password every 90 days to one that is significantly different from any previous password they've ever used this year, and this time reject proposed new passwords unless they jump through a bunch of unnecessary hoops to make the password strength checker happy.
