Hacker News Reader

Comment by Cushman | Hacker News Reader

I wonder, is it easy to use bcrypt with a variable work factor per-password?

I'm thinking you could take your entropy analysis of the user's password and set it so that "weaker" passwords use a higher work factor. This analysis could be easily done before hashing every time the password is input, so an attacker wouldn't be able to single out weak passwords from the hash file.

Theoretically, you should be able to tailor the numbers so that cracking a weak password isn't any faster than cracking a strong one, right? Plus it will encourage your users to use a stronger password in the first place, since it'd make login slightly faster.

Any obvious problems with this plan?

View on HN

It's not hard to do this (with Ruby bcrypt, it's 2 lines of code using the public interface), but I think you're overthinking it. Most users will use crappy passwords. Set the work factors uniformly high.

Definitely a good point.

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.

You're overthinking both the security aspect of this and the performance aspect of it. User-imperceptible hash times are adequate to make most conceivable brute force attacks intractable.

That's true of passwords over a certain strength, for sure. And it always has been; "6ab$TRa?" has never been counting on the difficulty of hashing for security, and probably won't for some time.

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.

"6ab$TRa?" has never been counting on the difficulty of hashing for security, and probably won't for some time.

False.

Elaborate. Obviously its security depends on the hashing scheme (if it's CRC32, you could find a collision pretty easily), but educate us -- is that all you meant?

To nitpick, the topic at hand is pre-image attacks, not collision attacks. Pre-image is where you know the hash and want the plaintext, collision is where you create two plaintexts with the same hash but don't care about the actual hash value. The former is recovering information, the latter is falsifying trust and almost always involves signatures.

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!

Wrong. Collisions can be found in MD5 in 2^21 time due to an attack by Xie and Feng. 2^64 is a very respectable number and is not practical for people to do on their home machines. 2^21 is.

You are right, of course. I wrote that as 'ideal digest' instead of MD5 then rewrote it. Specific digests always lose a few bits in real life, or in MD5's case, most of the bits...

Plus you only need a collision to break into a system that uses hashed passwords, not a preimage.

Clarify? Collision attacks by definition do not feature an existing digest as input so they are not useful for breaking into a system secured with a digest.

Ah, I misunderstood. By "collision attack" you meant "find two plaintexts that hash to the same digest", I interpreted it as "find one plaintext that hashes to a specific digest", and "preimage attack" as "find the plaintext that was hashed to this digest".

Please disregard my comment above.

I guess he could mean that you could find a plaintext that had the same hash value through use of a collision ... but that's just finding a preimage.

That's all I meant. 8 type-able characters is pretty easy to break if you have a couple of grand to invest in GPU's.

> As it stands today, anyone using one of those is instantly compromised the moment the hash file is accessed.

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?

As noted in the OP, it takes far, far less than one second to hash one password using standard algorithms.

It seemed to me like you were talking about bcrypt, weren't you?

Well, the argument was that user-imperceptible hash times should be sufficient for all passwords. I was trying to make the case that even the class of extremely weak passwords can be protected with perceptible hash times.

So really I think you were demonstrating my point :)

I think it would be enough to get hold of the 1,000,000 most common passwords and tell the user it's not allowed.

That still leaves you open to side-channel attacks, yes? It's easy for an attacker to find which passwords are prohibited, so by restricting them you remove them from the search space. But your users aren't going to start choosing fundamentally secure passwords, the attack just shifts to the next 1,000,000 common passwords.

Maybe it just shifts to the secure password you generate and suggest to them?

Dumb idea:

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.

I'm not sure about the bcrypt implementation, but if the work factor is public (i.e. you have to know it before calculating the hash), this gives you information about the password, which is bad.

This exposes information about the password: namely it's estimated entropy. The bet you're making is that the increased work factor overshadows any advantage an attacker may gain knowing that information.

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.

If I’m remembering my discrete math correctly, your claim isn’t correct:

> … 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!

You are correct: 2^10 - 2^5 != 2^(10-5); which is what he is doing by subtracting the entropy.

Thanks for the correction!

If I understand the grandparent correctly, there would be no way to determine which rows have a higher work factor. The work factor would be determined when the password is given, based on the password entropy - the correct password will always have the same entropy, therefore the same work factor. If the work factor is calculated on the wrong password (typo, etc.) it will not generate the correct hash anyway. Therefore an attacker has no way of determining which password hashes have a high work factor, and which ones have a low work factor.

Ah, yes, I'd missed that. Since you have the password at login time, you don't need to store the work factor. There are some practical things about making sure you can version the entropy estimate code without breaking existing logins, but it's certainly doable.

The definition of a "weak" password is so loose it doesn't make sense to make your work factor a function of it. The most common attack on this kind of schemes is a side-channel attack, where you single out a subset of the password alphabet with a relatively small "work factor" and crack passwords which use that alphabet quickly.

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?

I see it as a kind of side-channel defense; take the set of passwords which it is possible to crack quickly and use the work factor to even it out so that the total time to crack a password remains relatively constant.

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.

Hm. I don't know about bcrypt at all -- is it possible, given the ciphertext, to know roughly how much work is required to test a password?

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.

> is it possible, given the ciphertext, to know roughly how much work is required to test a password?

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.

Yeah, obviously if you can tell from the hash which class the password came from you lose the benefit.

Doesn't matter. 5 seconds or 0.1 seconds per test means that you cannot brute-force. Even for 5-letter English lowercase letters your search space is 11,881,376 combinations. At 0.1 sec/try it will take you 6.8 days on average to find just one password.

Reply on news.ycombinator.com