3 ms·
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
by Cushman 16y ago
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.
- andreyf 16y ago"6ab$TRa?" has never been counting on the difficulty of hashing for security, and probably won't for some time. False.
- gcr 16y agoElaborate. 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?
- gxti 16y agoTo 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!
- Xk 16y agoWrong. 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.
- StavrosK 16y agoPlus you only need a collision to break into a system that uses hashed passwords, not a preimage.
- gxti 16y agoClarify? 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.
- Xk 16y agoI 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.
- StavrosK 16y agoAh, 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.
- gxti 16y agoYou 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...
- andreyf 16y agoThat'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.
- StavrosK 16y ago> 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?
- Cushman 16y agoAs noted in the OP, it takes far, far less than one second to hash one password using standard algorithms.
- StavrosK 16y agoIt seemed to me like you were talking about bcrypt, weren't you?
- Cushman 16y agoWell, 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 :)
- stcredzero 16y agoI think it would be enough to get hold of the 1,000,000 most common passwords and tell the user it's not allowed.
- Cushman 16y agoThat 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.
- stcredzero 16y agoMaybe it just shifts to the secure password you generate and suggest to them?