Comment by Xk | Hacker News Reader

Comment by Xk | Hacker News Reader

Parent Full thread

SHA-1 is a reasonably good hashing algorithm, but for the sake of argument, I'll talk about an imaginary SHA-4 which is perfect in every respect. It will be a 4096 bit hash function which has no faster-than-bruteforce collisions or preimage attacks or second preimage attacks.

Let's also assume that this perfect SHA-4 function is freakishly fast, say, a million times faster than SHA-1.

Now, even though my imaginary SHA-4 function is perfect in every way, it would be strictly worse to use this for password hashing than SHA-1. Why? Because cryptographic attacks aren't the problem here. The problem is that the entropy of a user's password is very VERY small. So small, in fact, that attacks on passwords aren't done through cryptographic weaknesses, they are done by simply hashing everything someone might pick as a password and asking "did I get it right?". An attacker will repeat this process for a little while, and eventually they'll get the answer "YES, this user chose to make abc123 as their password!".

Right, which is the reason why "perfect in every respect" and "freakishly fast" are mutually exclusive in a hashing algorithm.

A "perfect in every respect" hash then would be one that takes a consistent, acceptably-long time. Some large fraction of a second perhaps.

Of course, this fictional hash wouldn't be the right choice for everything. But for password hashing, it's a good start.

(Edit: see child comment -- I was responding to something other than what was intended. I'm leaving this here for clarity, but you can ignore it.)

No, not really. Hashing functions aren't designed for passwords, they're mainly used for integrity checks and other uses which need to be fast: why do you think one of the axes the SHA-3 hashes are competing on is speed?

You have your 10gb file and want to send it to your coworker and let him know it's really yours and no one has messed with it. So you run an HMAC over it and then sign it with your private key.

You want it to be as fast as possible. It would be optimal if there was a single x86 instruction called sha4 which did this in the time it takes to do an add.

Hashing is really, really not meant for passwords.

Woah, slow down, I think you whipped up a 4 paragraph reply before you ever got to my last sentence.

Or, go on and tell me more about all the things hashes are used for as if I just fell off the turnip truck.

This discussion is not about checksums on files. It's abotu passwords. And your "perfect hash" in your example about passwords is "freakishly fast." In fact, like the other guy that replied to me mentioned, this is the entire point of the workfactor in bcrypt, right?

Of course, bycrypt is really, really not meant for checksums. Good thing nobody was talking about checksums then.

When you wrote "this fictional hash" I read that as talking about the SHA-4 I made up, not the one you did.

I then didn't respond to the rest of the post because when you said "for password hashing, it's a good start" I again assumed you were talking about my hash function, which is not good for hashing. Yours would be perfectly fine.

I apologize.

Apology accepted, and thank you for adding a lot to the discussion further down the page (the interesting maths related to the probability of collisions on a hashed-hash)

... Which is pretty much what bcrypt is.

http://codahale.com/how-to-safely-store-a-password/

>Let's also assume that this perfect SHA-4 function is freakishly fast, say, a million times faster than SHA-1

This is why they invented key stretching: http://en.wikipedia.org/wiki/PBKDF2

Just set number of rounds to 10000000000 instead of, like, 10000 for SHA1.

Reply on news.ycombinator.com