Comment by Cushman | Hacker News Reader

Comment by Cushman | Hacker News Reader

Parent Full thread

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.

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.

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.

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.

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...

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?

Reply on news.ycombinator.com