Can I improve the security of MD5 hashed passwords by salting the existing MD5 hash and hash the result using Scrypt or PBKDF2 HMACSHA256?

Question

I have a database of legacy passwords that were salted and hashed using MD5. I would like to update the system so that the data is more secure.

The first option is to transition the users to a new hashing scheme (Salt + Scrypt or PBKDF2 HMACSHA256) when they login and deactivate old users after a certain period of time so they have to use the password recovery feature which would automatically update their hash.

Another option that would allow me to instantly upgrade everyone would be to take the existing MD5 hashes, add a new random salt value to each, and then hash the result using the new hashing scheme (Salt + Scrypt or PBKDF2 HMACSHA256) and store that value to the database and delete the old value.

Then when users login, I would have to apply the old, and then the new method. I like the second option better since it allows me to remove all the old insecure hashes from the database sooner than later.

Is it secure to salt and rehash the existing hashes? Is MD5 so broken that I can run a script to de-hash the passwords and rehash them using the new scheme?

Or maybe the best solution is to do a combination of both options? This way I don't have to leave the existing MD5 hashes unsecured in the database and I can migrate users to the new system for a period of time?

Answer 1

MD5 is not so broken that you can de-hash all the passwords easily, but assuming the quality of the passwords isn't too good then you could probably brute force them and convert them to the new, more secure format. The brokenness of MD5 results from it's relatively small length (more collision surface) and it's computationally simple calculation (meaning brute force attacks are more feasible than algorithms that have larger run-time complexity such as SHA2)

If I were you I'd do both methods you listed (because as you mentioned, getting the passwords moved over quickly is important in case your DB is hacked). First I would brute force all the brute forcible MD5 passwords and convert them to the new format. I have done this in the past, and by far the best results have been using HashCat (the Cuda or OCL flavors preferably since they use the GPU and are 200 times faster). If Hashcat is too difficult (the learning curve can be steep), then try John the Ripper. It is a lot slower than HashCat but it's a lot easier to use.

For the passwords that you can't crack, expire the user's account and have them reset the password. Or to be nicer to your users, just update the password in the database to the new format the next time they log in by sending both hashes. If the MD5 checks out, then destroy it and replace it with the new format. These are just some ideas.

EDIT:

Forgot to mention that if you want to just hash the MD5 passwords into the new format that would be just fine security-wise, though it adds another layer of complexity to your code, and where there is complexity there is room for implementation flaws. Just something to think about.