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.
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.
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...
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".
> 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.
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 :)
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.
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.
