I feel like it might still help you to avoid wasting time exhaustingly hashing already strong passwords. I mean, how high does that uniform work factor have to be?

The guy whose password is "password" or "qwerty12" is gonna get cracked no matter what, sure. But what about people whose passwords are a couple of dictionary words? If the work factor means each hash takes a second or two, even a slightly complex dictionary attack becomes fruitless (for most crackers...)

So the user can still log in, but it takes a second or two, and there's that little message, "To ensure the safety of your password, your login has been slowed down. If you use a more secure password, like <generate password>, you will login much faster!"

And the young lady using "6ab$TRa?" isn't being punished for the fact that most users use crappy passwords, nor is your server.

But as computing power increases, that minimum strength is being pushed out. bcrypt lets us hold the line by keeping pace with computing power— couldn't it also give us the ability to push back?

How many users are using the 100,000 most common passwords? 1,000,000? As it stands today, anyone using one of those is instantly compromised the moment the hash file is accessed. With a truly variable work factor, you could theoretically ensure the safety of any password, regardless of strength.

It obviously gets silly toward the far end (make "password" take three months to hash?) And maybe it gets silly a lot sooner than I'm thinking. But surely it could be pushed back a little, yes? Make one of those 1,000,000 passwords intractable, and you're protecting thousands of users from attack.

False.

Collision attacks don't apply to many situations but are much easier to execute, for example a MD5 pre-image attack requires approximately 2^128 steps but a collision attack requires only about 2^64 steps. This is why MD5 is totally unsuitable for collision resistance, and in fact has already been successfully exploited to fabricate a real-world CA certificate, but still puts up mild resistance to password cracking. Not that I'm recommending you use it or anything -- do what the nice gentleman says and just use bcrypt already!

Please disregard my comment above.

How? If hashing one password takes one second, and you have a dump of a thousand users, it will take you a million seconds to try just 1,000 common passwords on that list.

Are you thinking of unsalted hashes, perhaps?

So really I think you were demonstrating my point :)

Have the work factor also be a function of the password itself... this would cause even more difficulty brute-forcing the password, as it means intermediate steps would also have to be tested - breaking one weak password doesn't give you any information about other passwords.

How could someone use this? Well, I could decide to only target the rows with a low work factor. Since your entropy estimate is high for these rows, I can know that it's more likely they'll be 8 characters or longer and use a wider range of characters. I can likely ignore all candidate passwords that are shorter or that do not include non-alpha characters.

How useful is this? Let's assume 2 choices of work factor. Also let's assume strong passwords of length 8 have 96^8 ~= 53 bits of entropy and eak passwords of length 8 or less have 27^8 ~= 38 bits of entropy.

You just let me cut the search space for strong passwords of length 8 to to ~15 bits, and in a double whammy, I get to use bcrypt with a low work factor when brute forcing against these rows.

I'm not a cryptographer, and so it's entirely likely I've made some mistake here. But as a general rule, I think it is an _extremely_ bad idea to use cryptography in any way that exposes additional information about individual rows in a database.

Cryptography is not a place for innovative thinking. Even cryptographers need their cleverness to undergo exhaustive review.

> … Let's assume 2 choices of work factor. Also let's assume strong passwords of length 8 have 96^8 ~= 53 bits of entropy and eak passwords of length 8 or less have 27^8 ~= 38 bits of entropy.

> You just let me cut the search space for strong passwords of length 8 to to ~15 bits…

You can’t subtract bits of entropy like that.

Here’s something I hope will convince you this reasoning is faulty.

Imagine a universe of 3-digit passwords, and there are two kinds of passwords: Strong ones use a mix of digits 0–7, and weak ones only use the digits '0' or '1'.

You could see the strong passwords could be any of 8^3 = 512 different combinations (~9 bits of entropy), except the 2^3 = 8 combinations (3 bits of entropy) that would only contain ones and/or zeros. So while a worst-case for brute-forcing a known-weak password is trying 8 strings, the worst-case for brute-forcing a known-strong password is trying 504 strings. This is still the same order of magnitude, and still approx. 9 bits of entropy! You removed such an incredibly small sliver of passwords, that an attacker really isn’t any better off than before.

Another way to think of this is, just because the user didn’t use only lowercase letters, doesn’t mean that none of the characters are!

Back to your example, with a strong password search space of 96^8. Now if you know a password is strong, that means it isn’t one of the 27^8 possible weak passwords. By how much does this reduce our search space?

  7,213,895,789,838,336 possible strings of length 8

- 0,000,282,429,536,481 possible 'weak' 8-char passwords

= 7,213,613,360,301,855 possible 'strong' 8-char passwords

We’ve reduced our search space by only .0039%.

That said, rolling your own crypto — which the grandparent post isn’t really quite doing — is something you should run away from, fast, unless you really are a cryptographer!

BCrypt is already based on the premise that there are passwords which are easy to compute, and tries to avoid that differentiation. Why would you introduce it back in?

Of course it's a good point that the challenge then becomes determining what that set of passwords is. And not having run the numbers, I can't be sure how much room for improvement there is.

E.g. an attacker can go "Oh! this password will take FIVE SECONDS to test, so I know it must be a simple password." or "Hey, check this out; this password can be tested in 0.1 seconds. It must be pretty complex."

In general, I'd guess that these kinds of information leaks are pretty bad because if an attacker can see how hard a password is to test, he now knows something about the password.

It may be better if, given a single unchanging hash, if it takes a variable amount of time to test a given password against this hash, though that might have its own can of worms.

The work factor is an input to the digest function, both when creating and when validating the password. Normally it should be stored alongside the digest itself so you can increase the work factor over time without disrupting existing passwords. So you are correct. It might theoretically be possible to correctly balance the work factor to counter variation in password info entropy so that all passwords take about the same time to crack, and this would be very cool and impress members of the opposite sex, but it would not improve security at all.

Making a probabilistic password checker is also a superficially interesting idea. Maybe my mind is too small to explore it completely, but it seems that at best it would be no better than just increasing the work factor.