Migrating password db off MD5 by chaining MD5 and Bcrypt?

Question

I have a legacy system currently storing unsalted MD5 passwords. Unfortunately, some other controls are not in place (like the ability to expire passwords) and I'm trying to upgrade my algorithm to something newer and avoid prompting the user for a new password.

I am wondering what the impact will be if I just use something like a bcrypt on the current MD5 hash. In other words:

1. User submits clear text password
2. Password is hashed using MD5
3. MD5 hash is hashed using bcrypt
4. Hashes compared for authentication purposes

Is this going to "lessen" the strength of the resulting bcrypt hash somehow?

Answer 1

What you would essentially end up with is MD5-ing the users passwords before feeding them into BCrypt.

While MD5 is a fast and badly broken algorithm, it does not remove any entropy from the passwords (unless they have more than 128 bit of entropy, but the password of the average user will have far less). So the entropy you feed into BCrypt is still the same.

When an attacker steals your database and wants to brute-force it, they still need to run BCrypt, just instead of running it on the one million most common passwords, they would run it on the MD5 hashes of the one million most common passwords. That won't take much longer, but it also won't take any shorter.

So as far as I see it there is really nothing wrong with your plan.

Answer 2

First, please see this question and my answer to it since I think it covers most of your question.

It's good that you want to update you password db off unsalted MD5. Since you don't have the ability to expire user passwords, you want to make sure that no passwords in the database are left as unsalted MD5.

You basically have 3 options for how to do this:

1. Move everyone to Bcrypt immediately by running a script on the database to double hash their current MD5 hash and store Bcrypt(MD5($passwd)) in the database. At their first login you see their plaintext password have the option to move them to Bcrypt($passwd), or you can leave the double hashing forever.

2. Leave everyone's password as MD5 in the database and update them to Bcrypt at their next login.

3. Do 1. or 2. coupled with a password expiry that will remove their hash from the db and force them to do a recovery if they haven't logged in after X time.

---

Pros / Cons

1. It's generally accepted in the security community that "double hashing" is fine - it won't give you any more security, but it won't weaken your security either. Here are two questions on crypto.SE on that topic: [more mathematical] and [more explanatory]. The advantage here is that if your db of password hashes is stolen tomorrow, all your users are protected by the newest tech, whether or not they've loggen in recently. This is really nice considering that even if a user has not logged in for 5 years, they may still be using that password on other sites. Another plus is that if you choose to go with the Bcrypt(MD5($passwd)) option, then you don't actually need any db schema changes. I would do this option.

2. As mentioned above, this option offers no protection to users who don't log in again, and requires db schema changes to track who is on MD5, and who is on Bcrypt. Moreover, if your password db is stolen a couple of months / years from now, the hackers will see which users are on MD5 and will crack their passwords first, so you're essentially throwing away the security for users who never log in again - and as mentioned above this is a problem because users tend to reuse passwords between sites. Overall, this option is more work for lower security and I think it's irresponsible towards your users.

3. If you are willing to expire passwords then combining this with 1. gives you maintenence options, and actually makes 2. a viable option since all the MD5 hashes will be out of your db after some fixed time. But since you said that expiry isn't an option, I won't linger on this.

---

Two aditional things you want to think about are:

• Whether you ever want to retire MD5 from your login code, or if you're happy doing Bcrypt(MD5($passwd)) forever. I don't think there's any security reason to remove the MD5 step, but if you do want to retire MD5 then you'll have to do something tricky on a user's first login, add a db column to track which hashing method they're using, etc.

• Consider what you're going to do in 5 years when we discover some flaw in bcrypt and everybody moves to the new all-powerful SuperHash. If you're storing Bcrypt(MD5($passwd)), then you can do the same trick and move to SuperHash(Bcrypt(MD5($passwd))) and everything will be fine. If, however you opted to move users to the cleaner Bcrypt($passwd) then you have to do some more tricky stuff with db columns because there's a good change you'll have users who have never logged in to update to the new hash.