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.
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.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.
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.My concern is that artificially constraining the input set to range(md5) might similarly make brute forcing (or other attacks) easier.
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 :)
The question is what to do to protect passwords starting today?
bcrypting the md5s sounds like a good approach.
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.
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)?
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.)