Hacker News Reader

Comment by yummyfajitas | Hacker News Reader

Hypothetical question - say I'm an idiot and I already have a database full of md5-hashed passwords. What do I do now?

The best I've been able to come up with is bcrypting the md5's. But unfortunately, while bcrypt^-1(ALL STRINGS) is hard to compute, it's not clear that bcrypt^-1(range(md5)) is. I see no compelling reason why it wouldn't be, but I don't know enough about the subject to offer a strong claim.

Can any experts offer advice on this?

(I'd also replace the `bcrypt . md5` password with a regular bcrypt one after the user authenticates.)

View on HN

Since MD5 hashes and bcrypt hashes are recognisably different: when the user next successfully logs in, check if they have an MD5 hash; if they do, use the password they just submitted (that you know is correct) to generate a bcrypt hash and then update your password database with that.

If you have a large number of inactive users, this might not be as effective (you'll still be left with lots of MD5 hashes in the event of a dump) but for other sites it can be quite useful.

You can also use the same strategy to increase the work rate of your bcrypt hashes in the future.

What kind of database are we talking about? The kind of database where you can't reset users' passwords?

Someone asked a question similar to yours a while ago. Maybe the answers may be of help: http://news.ycombinator.com/item?id=4076257.

I guess you could run bcrypt on all your database's md5 hashes and do something like:

    if entered_password.md5.bcrypt == stored_password:
        stored_password = entered_password.bcrypt
        login()

That way, you will only have to store the bcrypted md5 hashes, until the next time someone tries to log on - assuming that's the kind of back-end you have.

If inverting bcrypt(md5(.)) was easy then you'd have a preimage attack on md5: given your value md5(x), compute a bcrypt digest of that and attack that instead. (Which is not exactly the same as inverting bcrypt(md5(.)) given a dictionary of likely inputs, though.)

Anyway, if there's any input set X for which bcrypt(X) can be inverted more efficiently than brute force, then you could say that bcrypt is flawed. If that set is the random-looking hashes of user passwords, instead of a carefully constructed one designed to attack bcrypt, then you can safely say bcrypt is catastrophically broken.

Anyway, if there's any input set X for which bcrypt(X) can be inverted more efficiently than brute force,

Here is one:

    [ (bcrypt x salt) | x <- dictionary, salt <- all_bcrypt_salts ]

Now I do think it's unlikely that range(md5) is a good domain on which to attack bcrypt, but I also recognize I'm not smart enough to be sure.

I don't get what you're saying here. Is your input set a bunch of outputs of bcrypt? Is your input set `dictionary`? Either way, how can you invert the output of bcrypt more efficiently than brute force?

In my particular example, you need only brute force it over a dictionary, which is not that hard to do (even for bcrypt). That's because the input set for bcrypt is being artificially constrained.

My concern is that artificially constraining the input set to range(md5) might similarly make brute forcing (or other attacks) easier.

Add a new bcrypted password column.

Alter authentication so that it uses bcrypt column if populated.

Alter registration/password changes so that it populates bcrypt by default.

As old users log in (and you therefore have access to their plain text password and know that it's valid) populate the bcrypt with the correct hash.

After a period of N weeks when you've basically migrated all of your active users, do a forced password reset on the rest.

Kill the MD5 column.

Done :)

As I said: "I'd also replace the `bcrypt . md5` password with a regular bcrypt one after the user authenticates."

The question is what to do to protect passwords starting today?

Apologies. I'm an idiot who can't read a question :-)

bcrypting the md5s sounds like a good approach.

bcrypting your md5 hashes is much better than having the md5 hashes around for various reasons. The major reason is that there are many md5 rainbow tables, and if your md5 hashes ever leak out, a huge number of your passwords will be known almost immediately. bcrypt+md5 rainbow tables are much less common.

If you can, also add a user-specific salt (username is the obvious choice).

In theory cracking bcrypt+md5 is easier than plain bcrypt, because users could have passwords with greater than 128 bits of entropy. However, the vast majority of users won't, and generating a 128-bit rainbow table isn't practical.

...bcrypt+md5 rainbow tables...

I don't think this is possible, since bcrypt has a built in salt.

Does the fact that you bcrypt and md5 undo this salt? I.e., is bcrypt(md5(password), salt1) == bcrypt(md5(password), salt2)?

No, certainly not, as bcrypt doesn't "know" it is getting md5, there is nothing wrong with passwords being hexadecimal strings. Sorry, I miswrote there.

Reply on news.ycombinator.com