45

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.

Peter Mortensen
  • 885
  • 5
  • 10
user1067003
  • 564
  • 4
  • 11

3 Answers3

92

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.

Royce Williams
  • 9,318
  • 1
  • 32
  • 55
  • 12
    interesting, it's basically using a md5-dictionary instead of using a password-dictionary, not that using a md5-dictionary for the attack is any cheaper than using a password-dictionary for the attack (but bruteforcing md5 is much cheaper than bruteforcing bcrypt), but you're practically saying `there's a chance the attacker has the md5 but not the password itself, and that makes it a bad idea to bcrypt(md5)` ? – user1067003 Jul 17 '20 at 14:00
  • 2
    **YES!** It takes many people a _very_ long time to get this subtle point (and some never do!) Major kudos for understanding it so quickly! – Royce Williams Jul 17 '20 at 14:02
  • @RoyceWilliams: I don't see your point. In my opinion you essentially argue that `bcrypt(MD5(...))` is __not more secure__ than only using bcrypt. While this is true it does not answer the actual question - which is about `bcrypt(MD5(...))` possibly being __less secure__ than bcrypt alone. The question is about protecting existing badly hashed passwords, not about inventing a better hashing. – Steffen Ullrich Jul 17 '20 at 14:18
  • 1
    @SteffenUllrich I am 100% arguing that it makes it **less** secure than bcrypt alone. I've worked very hard to make that clear in my answer ('weaker', 'otherwise totally out of reach for the attacker', etc.). How can I improve my answer to make this more clear? – Royce Williams Jul 17 '20 at 14:32
  • 5
    If I understand it right (from reading your superuser answer as well), doesn't this really boil down to a password reuse problem? If the md5 of my password is nowhere on the internet, then I guess I'm good, right? – nobody Jul 17 '20 at 14:41
  • 12
    Yes. As _an individual user_, you can influence the likelihood that _your own password_ is protected by picking a strong password. (As I've said elsewhere "even a weak hash can protect a strong password.") But for people _writing software_ to protect passwords - many of which are chosen poorly - we must design the system to protect even bad passwords, which includes reused passwords, or even passwords that happen to be rare but also happen to be poorly constructed. – Royce Williams Jul 17 '20 at 14:44
  • I know I'm probably stupid but... how is this different from a dictionary attack? Instead of trying a list of known passwords, you try their md5s. If the md5 hasn't been cracked before, chances are that the password is strong enough to resist being cracked now. – nobody Jul 17 '20 at 14:55
  • 16
    Because there are plenty of MD5s in the wild that A) just happen to not have been cracked yet because they weren't interesting enough to stand out, but B) once an attacker can figure out that that MD5 is inside _a really interesting, high-value-target bcrypt_, they might spend _a lot more effort to crack that MD5_. So it's not just a dictionary attack; it's a dictionary attack _of passwords that are currently unknown but might be crackable with additional effort_. And that effort is **much** less than trying to crack that password _if it was only inside a pure bcrypt_. – Royce Williams Jul 17 '20 at 15:00
  • 1
    Oh I think I see now. But how do we mitigate this? – nobody Jul 17 '20 at 15:02
  • Very fair question - will update answer. – Royce Williams Jul 17 '20 at 15:04
  • 3
    @RoyceWilliams: thanks, the link to the OWASP guide on pre-hashing cleared things up. – Steffen Ullrich Jul 17 '20 at 15:15
  • 1
    @RoyceWilliams But in the OPs scenario, the hashes are simple md5s, no salt, no pepper. What do they do now? – nobody Jul 17 '20 at 18:06
  • 1
    Might help if I actually answered the question. Got excited about the methodology. ;) Answer updated. – Royce Williams Jul 17 '20 at 20:05
  • How about we do this for existing passwords, but update the hash on next login to bcrypt(salt + fold64(string)). The idea is fold64 does key-mixing only if the string is > 64 chars in the first place and otherwise just returns its input. – Joshua Jul 17 '20 at 22:38
  • 3
    Have I understood correctly if I summarize it by: `md5($pass)` < `bcrypt(md5($pass))` << `bcrypt($pass)`? If so, that would mean `bcrypt(md5($pass))` is generally not a good idea, but in the context of OP's question, it's a little bit better to use `bcrypt(md5($pass))` as it's an easy-and-quick implementation in the short-term? – Evariste Jul 18 '20 at 09:26
  • 1
    Yes, I think that's a fair summary. – Royce Williams Jul 18 '20 at 15:16
  • @RoyceWilliams I think I understand the attack you're describing, but I have a hard time seeing how it could be very practical. The point of bcrypt is to make it expensive to test password guesses, and that'd apply to testing leaked MD5s as well. Thus, while you could certainly test them, you shouldn't be able to test huge quantities of them (and I'd expect there *are* huge quantities of them). – Gordon Davisson Jul 20 '20 at 05:53
  • 2
    This is a great answer, and as the primary author of that OWASP cheat sheet it's really good to see this type of attack being more widely discussed. However, one change I would make to this answer is to emphasise that while `bcrypt(md5($pass))` isn't ideal, even without the additional suggestions it is still **orders of magnitude better** than the existing `md5($pass)`. – rbsec Jul 20 '20 at 10:45
  • Concur 100% - updated to clarity. Good call, @rbsec. – Royce Williams Jul 20 '20 at 19:28
37

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.

March Ho
  • 1,685
  • 1
  • 13
  • 15
  • 8
    I gotta say ... that's a very good point. And IMO, as each existing successful login comes in, its hash could further be "upgraded" to simply be bcrypt($password), side-stepping the shucking problem. (This is on the assumption that 72-character passwords have no actual practical value and that plain bcrypt would do just fine; extra complexity to work around that maximum length has little value.) – Royce Williams Jul 18 '20 at 05:22
  • 2
    @Royce "This is on the assumption that 72-character passwords have no actual practical value" passphrases? – Vaelus Jul 18 '20 at 13:02
  • 2
    Very fair question. Definitely better answered elsewhere, but I'd argue that the actual math (dictionary length + number of words chosen) means A) most risk models require neither count nor word length that forces total length much above 72, even for fast hashes, and B) if the goal of passphrases is be memorable, using a dictionary with dramatically long words reduces UX without useful increase in entropy. A six-word passphrase, drawn from a 20k dictionary, almost always fits under 72 characters - and even truncated, doesn't make the keyspace feasible for even high-resourced attackers. – Royce Williams Jul 18 '20 at 15:26
  • 3
    That being said, **the mission of hashing is to protect even weak passwords** as much as feasible. So if a naive user thinks that passphrases are good, and length is good, so "pneumonoultramicroscopicsilicovolcanoconiosis-antidisestablishmentarianism-pseudopseudohypoparathyroidism-floccinaucinihilipilification-supercalifragilisticexpialidocious" must be a good password, then truncating such passwords at 72 results in significantly reduced entropy, and is a case worth considering. So ultimately, if there's a clean way to support arbitrary lengths, that would indeed be ideal. – Royce Williams Jul 18 '20 at 15:31
  • @Royce Goid point, I hadn't realized strong EFF diceware passwords actually fit in 72 chars. – Vaelus Jul 18 '20 at 21:14
0

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.

thomasrutter
  • 1,608
  • 12
  • 17
  • 1
    A key point you've missed here is that you don't need to wait for the user to _change_ their password to upgrade the hash, only for the next time they _provide_ it. This is the reasoning behind [PHP's `password_needs_rehash` function](https://www.php.net/password_needs_rehash): whenever the user logs in, you have the plain text available, and can re-hash it and update your database if necessary. This is separate from the valid concern you mention of considering the old passwords compromised because of the risk of the old hashes leaking. – IMSoP Jul 20 '20 at 10:30
  • ^ If you're reasonably sure the md5 hashes haven't leaked (yet), you could choose to log all of your users out; forcing them to log back in. This won't protect inactive users... but it's not as intrusive as requiring everyone to change their passwords. – Stephan Bijzitter Jul 20 '20 at 12:47
  • @IMSoP very good point thanks, I'll update the answer to point that out – thomasrutter Jul 21 '20 at 03:50