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?

Haemostat

possible duplicate of Use SHA-512 and salt to hash an MD5 hashed password?. (Not identical, but most of the answers sound they apply here too.) – Ignatz

Just found that one... The most important aspect is removing / securing the current data ASAP. – Haemostat

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.

Diversify

"The brokenness of MD5 results from it's relatively small length (more collision surface) and it's computationally simple calculation" -- the real problem with MD5, which is very severe, is that it is not collision resistent. Using Klima's method, you can find a collision to a given key within about a minute on a low-end system, using the CPU -- no massive GPU setup needed. This does not reveal the original password, but it delivers a "password" that is just as good, as it passes the hash challenge. – Toshiatoshiko

Answer 2

This is actually a very ingenious idea you had. Normally i would have:

• waited until a user returned
• realize that their stored password needs to be updated
• now that i have their (known valid) password in memory: rehash it with the new algorithm
• store the new hash in the database

The downside to only having used MD5 is that it's easy to bruteforce. By (temporarily) treating the MD5 result as an intermediate step before applying the real scrypt/Argon2, you thwart bruteforcing attempts.

Using a fast hash algorithm as a pre-processing step before the "real" password hash is not unheard of - and can even be useful.

• BCrypt has a known password length limitation of 72 bytes (71 utf-8 characters and then a null terminator). Dropbox applies SHA2-512 to the incoming plaintext password before running it through bcrypt. By running a long password through a hash first, they overcome the 71 character limit.
• Not only does this overcome the password length limitation (avoiding having to truncate or limit the password size), but it can prevent a Denial of Service attack when someone supplies an extraordinarily long password. BCrypt and Scrypt are suseptible to attacks with longer passwords (i don't know about Argon2).

So there can be a virtue in using a pre-hash (although not necessarily MD5).

I don't know how you're currently storing the MD5 hashes. MD5 is 128-bit. Assuming you store it in Base64, you can easily recognize it:

• MD5: nMKuihunqT2jm0b8EBnEgQ==

The desired final goal is something like scrypt:

• MD5: nMKuihunqT2jm0b8EBnEgQ==
• scrypt: $s0$e0801$epIxT/h6HbbwHaehFnh/bw==$7H0vsXlY8UxxyW/BWx/9GuY7jEvGjT71GFd6O4SZND0=

So when validating credentials against a saved hash, you can figure out which hash it is and use the appropriate algorithm. Your intermediate step, which adds the computational complexity, is defining your own format for:

MD5 + scrypt

something like:

• MD5: nMKuihunqT2jm0b8EBnEgQ==
• MD5 + scrypt: $md5s0$e0801$eX8cPtmLjKSrZBJszHIuZA==$vapd0u4tYVdOXOlcIkFmrOEIr1Ml2Ue1l2+FVOJgbcI=
• scrypt: $s0$e0801$epIxT/h6HbbwHaehFnh/bw==$7H0vsXlY8UxxyW/BWx/9GuY7jEvGjT71GFd6O4SZND0=

Now you recognize the algorithm being used based on the saved hash, and can upgrade passwords in pieces.

Cowbane

Quite an old question! I ended up just waiting for the users to upgrade and the plan was to eventually lock the old accounts and for them to recover their passwords which would have brought them up to the latest standard. Additionally, I added a version to the password system to make it easy to upgrade to new algorithms on a per user basis as they became available and the system would automatically upgrade them to the latest version when they logged in. – Haemostat