How to Upgrade to a Stronger Password Hash. Such as Upgrading from MD5 to BCrypt.

Years ago I upgraded the hash algorithm in our database application from a custom algorithm to BCrypt.  Although the implementation went well I lamented the need to retain the old algorithm until such time as all users had logged in and replaced their old hashed password with a new hashed password.  Since that time I have learned there is a better way to upgrade to a stronger password hash so I am sharing it here in case I need to do this again in the future and possibly to help someone else implement a better approach.

In a nutshell, what I should have done is hashed all the existing hashed passwords using BCrypt immediately.

If that does not give you the hint you need to see the solution, allow me to explain in more detail.

Assume you have a database full of user names and passwords, the passwords were all hashed using MD5, and you now want to use BCrypt to hash them.  The approach a lot of us take, including myself, is to add the BCrypt algorithm to the application code.  When users log in to the updated application, the code does the following:

• Person enters user name and password
• Application hashes the password using MD5
• If the MD5 hash matches the hashed MD5 password in the database:
  • The application hashes the password using BCrypt and stores that in the database
• In the future, the application will use the BCrypt hash for the user instead of the MD5 password.

The problem with this approach, is that that the application must continue to support the old hash algorithm (MD5 in this example), until all users have logged in and converted their password hashes to BCrypt.

There is a better way.

• Immediately hash all the MD5 hashes using BCrypt.  (Note, this is not hashing the passwords, because we do not know the passwords.  We are hashing the MD5 hash of the passwords.)
  • This allows us to immediately have all the passwords hashed with the stronger BCrypt algorithm.
• As users log in to the application, hash the password they enter using BCrypt and see if it matches the hash stored in the database.
  • If not, then hash the password they enter using MD5 (your old algorithm), and then hash the result of that operation using BCrypt.  If that hash matches what is stored in the database, allow the user access to the application and also create a new hash of their password directly using BCrypt and update the hash stored in the database.

As mentioned, the benefit of this approach is that you immediately convert all the stored passwords to the stronger algorithm, instead of implementing a gradual process that does not convert all the passwords until all user accounts have eventually logged in, which could be never for some applications.