Is bcrypt(strtolower(hex(md5(pass)))) ok for storing passwords? [duplicate]

Question

I have a large database where passwords are stored as strtolower(hex(md5(pass))) (which is a bad way to store passwords, prone to rainbow tables, cheap to dictionary attack, no salt, etc.), and I'm tasked with switching from md5 to bcrypt,

I have to use a bcrypt implementation that silently truncates after 72 bytes, and silently truncates on the first null byte (whichever comes first), and bcrypt(strtolower(hex(md5(pass)))) would not be prone to either of those issues.

Also it's possible to retroactively apply bcrypt to existing strtolower(hex(md5(pass))) password hashes, without requiring everyone to re-login/switch passwords.

Is it a bad idea? I don't think so, but still want to hear what this site has to say. Maybe there is something important I'm missing.

Answer 1

As a password cracker, I encourage all of my targets to use this technique. 😉

This (understandably!) seems like a good idea, but it turns out that against real-world attacks, wrapping an unsalted hash with bcrypt is demonstrably weaker than simply using bcrypt.

(EDIT: First, to be clear up front, bcrypt(md5($pass)) is much better than md5($pass) alone - so none of this should be take to mean that this scheme should be left as is.)

Wrapping an unsalted hash is problematic from a real-world attack perspective because attackers can do this:

1. Acquire existing MD5 passwords from leaks - even MD5s that haven't been cracked yet
2. After simpler attacks have been exhausted, run these MD5s as a "wordlist" against your bcrypt(md5($pass)) corpus, to identify uncracked bcrypts with known MD5s
3. crack those MD5s outside of bcrypt at much higher speed

And yes - you do have to discover the MD5 inside the bcrypt first. But the crucial point is that that MD5 can be an otherwise uncracked MD5 that happens to be present in some other leak, which you can then attack at massively increased speeds.

This is not a theoretical attack. It is used all the time by advanced password crackers to successfully crack bcrypt hashes that would otherwise be totally out of reach for the attacker.

How this attack works is very non-intuitive for non-specialists, so I strongly encourage skeptics to experiment with a real-world scenario to understand how it works:

1. Hash a 6-character random password with MD5.
2. Presume that this MD5 is already present in some other list of leaked passwords, proving that it has been used as a password at some point.
3. Try to attack the MD5 directly with brute force.
4. Wrap the MD5 in bcrypt and try to attack it directly with brute force.
5. Attack the same bcrypt-wrapped MD5, but this time pretend that you haven't cracked the MD5 yet, but instead use a "dictionary" of leaked MD5 that includes your MD5.
6. Once you've "discovered" that you have an MD5 in hand that is inside one of your bcrypts, attack the MD5, then pass the resulting plaintext to your bcrypt(md5($pass)) attack.

Again, very non-intuitive, so play with it (and don't feel bad that it takes work to understand it; I argued vigorously against it with Jeremi Gosney for an hour straight before I finally got it!)

I don't believe that this technique has an "official" name, but I've been calling it "hash shucking" or just "shucking."

So depending on use case, it's totally understandable why wrapping bcrypt can be attractive (for example, to get beyond the 72-character bcrypt maximum, though this can be tricky for other reasons, including the 'null byte' problem), or to migrate existing hashes.

So if someone needs to wrap a hash in bcrypt, the mitigation for this weakness should be clear by now: your inner hash must never appear in any other password storage system that might ever become available to an attacker. This means that you must make the inner hashes globally unique.

For your specific use case - in which you need to preserve existing hashes - there are a few options, including:

• adding a global pepper within your web or DB framework - so, bcrypt($md5.$pepper) This allows you to easily migrate existing MD5s, but that global pepper is still subject to being stolen (but if your web tier is segmented from your DB tier/auth, this might be an acceptable risk, YMMV);
• adding a global pepper using HSM infrastructure (storing the pepper in such a way that not even the web app can see, so it can't be stolen)
• adding an extra per-hash salt (but you'd have to store it outside of the hash somehow, which starts to get tricky and verges into 'roll your own crypto' territory);
• hashing the MD5s with a slow, salted hashing algorithm or HMAC inside the bcrypt layer (not recommended, I'm not even vaguely qualified to advise on how that might be done properly, but is possible - Facebook is doing it, but some very smart people designed that);

For more details, including some specific scenarios to illustrate why this is weaker than bcrypt alone, see my SuperUser answer here, this OWASP guidance on "pre-hashing" passwords which supports my assertion with more clarity, and this talk by Sam Croley discussing the technique.

Password upgrading in general can be tricky; see - this answer and Michal Špaček's page on password storage upgrade strategies.

Answer 2

While Royce's answer is correct in that wrapped hashes are weaker than unwrapped pure bcrypt hashes, it must be noted that they are nevertheless significantly stronger than your current implementation with a weak hash algorithm and no salt, since an attacker would have to go through the effort of individually attacking each hash, instead of simply using precomputed rainbow tables on the entire database.

While it's probably not the best option to store the wrapped hashes long term, it is (as you noted) a good solution to immediately upgrade the security of your password database without forcing everyone to change their passwords. To avoid the vulnerability of a wrapped hash, you could upgrade the hash upon the first login to an un-wrapped hash, as described by OWASP:

An alternative approach is to use the existing password hashes as inputs for a more secure algorithm. For example if the application originally stored passwords as md5($password), this could be easily upgraded to bcrypt(md5($password)). Layering the hashes in this manner avoids the need to known the original password, however it can make the hashes easier to crack, as discussed in the Pre-Hashing Passwords section. As such, these hashes should be replaced with direct hashes of the users' passwords next time the users login.

Answer 3

Transitioning from one hashing scheme to another is nothing really out of the ordinary, and is something that systems sometimes do. If you have a password hashing scheme that is less than ideal, and you want you improve it, you build it so that new passwords (including password reset from that point onwards) use the new hashing scheme, and old passwords have the old hashing scheme. You make sure that the record itself identifies which scheme is in use, and when a user logs in it's verified in the appropriate way (and can then be transitioned to the new hashing scheme). Gradually, as users come back and new users join, more and more users will be using the better hashing algorithm.

In your specific case, wrapping the md5 in a bcrypt can be thought of as an interim solution - something you can apply immediately to all existing hashes - whereas new hashes could use bcrypt without md5.

Once implemented, you have a think about whether you want to force old users across to the new scheme by forcing a password change on their account even if they haven't visited the site. To do so you would need to consider the following factors:

• How long will you wait before forcing a password change? For example, will you give 12 months after implementing the new scheme? Has a specific threat, exploit or issue with your current scheme meant that this should be done sooner?

• For both returning users and users asked to change their password, will you require verification using another method such as email? If you are concerned the current password hashes could have been, or have been, compromised, you may want to try and verify using a verification contact method.

• Will you allow users to use the same password again when transitioning to the new hashing scheme? Technically you could just let them log in using their existing password and silently update the hash at the time so the same password has a new hash. But if you have specific concerns about the security of the old scheme you may consider the old password compromised and not re-usable.

Note that crypt() itself designs its hashes to be extensible in terms of algorithm and number of rounds, so that future changes to either can be transparent to you, with older hashes continuing to work as above and standardized way to tell which algorithm and number of rounds any given hash uses. So once you move to "$2y$"... crypt serialized hashes, future switches if they can be implemented in that format can be easier.

---

Other answers have addressed whether bcrypt-wrapped-md5 is a good idea or not, I will merely add that while it may not be an immediate train wreck of an idea, it's still not ideal, and transitioning away from it as soon as you can is a good idea.

My issue with it is that the non-bcrypt-wrapped hashes may still exist in backups, old servers, or even have already fallen into the wrong hands. If the passwords haven't changed, then no matter how much more work it would be to crack the bcrypt-wrapped passwords, anybody who came upon an old dump of the bare md5 hashes could bypass that. So, that's not ideal and in this case a password change at some appropriate time is probably warranted for that reason.