Hacker News Reader

Comment by ryan-c | Hacker News Reader

This article says salting hashes is only useful against rainbow tables. That does not make sense to me. Say you have a password database with 10,000 users in it. You want to see if any of them used "Passw0rd$". Without salt, you compute the hash once and check it against all the users (perhaps with a bloom filter). With per-user salts, you have to compute the hash for each user.

I think salting offers pretty clear benefits against other attacks if you have more than one user.

Edit: The point I'm trying to make here is that it is N_USERS times better to have a unique salt per user, regardless of the hash. One should use bcrypt/scrypt/pbkdf2 with unique per-user salts.

View on HN

A better argument for per-user, randomly-chosen-at-password-change-time salts is so that you can't determine that two users (currently or historically from a password history) are using the same password by comparing the hashes.

If you knew that a hash was used many times over in a system, then you'd try cracking that password first to get access to the most accounts.

With salting you don't get to prioritize, or compare to previous information trivially.

I don't think that's a "better argument". I think it's a second, also good, argument that I didn't repeat because it's been mentioned by several other people.

Your argument is about protecting trivial passwords. It's quite common for people to independently come up with the same crappy passwords - the adobe "crossword puzzle" leak was a particularly interesting example of that.

My argument is about protecting moderately good passwords. If you use, for example, PBKDF2 with a fixed salt and have a million users, an attacker can try close to a million times as many passwords vs random salts.

You can still prioritize cracking with salted passwords in many cases. Say you had a dump of hashes form hackernews, and they were bcrypted with random salts. You'd go after the admin accounts first, then the well known accounts with a lot of influence, then everybody else.

That's the exact same argument, phrased differently.

The salt is typically assumed to not be secret. With modern hardware recalculating the hash is not hard for "fast" hashes, regardless of salting. That's why choosing a slow hash is more important for this vector of attack than anything else.

Of course salting is better than no salting, but its orders of magnitude less important than choosing a good hashing mechanism. Luckily, the good hashing mechanisms do the salting for you so fixating on salting really just serves as a proxy for letting us know that you don't understand the attack vector.

Whether the salt is secret or not doesn't matter. If it's known that I salt passwords in the USERS database with the `uname` field, hashes for "workloginpa$$word" and "kasey_junkpa$$word" will look different, even though our passwords are the same. There's no easy way to compare passwords when they're salted, and that's the point to understand.

Yes, having a good hash in the first place is more important, but salting is right up there.

No, it's not, because choosing a proper KDF will make your passwords take years to crack, while choosing a standard digest with a salt will turn the time from fractions of a second to days.

The only thing that matters is whether or not your password database ends up on a message board somewhere, not about how you feel about hashing.

A proper KDF is more important if you are trying to break a specific user's password. It will simply take too long to try any reasonable number of attempts. However, in the event that you have a large database leak individual salts become just as important. When looking thousands of users, unsalted hashes allow attackers to start with the most common passwords used and compare them to the entire leaked database in one try.

Are there any proper KDFs that don't include a random salt?

this whole discussion is a red herring. Of course all current KDFs include salting as a form of key stretching. That's because no one designing them is writing off rainbow table attacks.

Yes, it is!

Since DDG does it quick, I'll use MD5 as an example, but don't ever use MD5 as your hash!

An attacker already knows a user's plaintext password is "pass123" and no salting has occurred. He can search for "32250170a0dca92d53ec9624f336ca24" in the database and find 5 other users that have the same hash. He now knows that those 5 people have the same password.

Meanwhile:

    Johnpass123: e3445c82086cff25a79dcbbe59b569d1  
    Mattpass123: fd6d563970fd6ead6391a997a5e06d80

Moral: It's not about how hard it is to crack. It's about comparisons of hashed values without cracking necessary.

I think you're severely underestimating the importance of salting. I agree that choosing the "correct" hashing algorithm is more important than salting, but not by magnitudes.

Even if you're using a "hard" hashing algorithm, you're significantly reducing the amount of computations an attacker would have to go through by forgoing salts. Especially considering that salting has very, very little overhead.

forgive me, I haven't worked with a good hashing mechanism before.

How can it "salt for you" without you providing the salt?

This question is operating on the presumption of a unique salt per user.

I was skipping some complexity. Something like b/scrypt are more than just hashing. They are key derivation functions, which look similar to hash functions on their inputs.

bcrypt for instance generates a random salt on the input and stores it in the output.

http://stackoverflow.com/questions/6832445/how-can-bcrypt-ha...

A lot of password hashing APIs have two calls - one where you provide the password (and possibly work factor) and it returns a hash that includes a randomly generated salt, and another where you pass in the hash (which includes the salt and work factor if any) and the password which returns true/false.

The attack you are describing would just be a rainbow table. That's exactly the point.

No, brute-force attacks are different from rainbow tables: http://en.wikipedia.org/wiki/Rainbow_table

But that's the point - you're not describing a brute-force attack, you're just describing a rainbow (/lookup) table. Precalculating hashes and then matching hashes from the dataset to them.

It's a different form, but it's pre-calculation and lookup nevertheless.

I don't understand this comment.

Are you somehow interpreting the stolen database as the rainbowtable somehow?

Are you saying that, when the attacker calculates the hash, it's analogous to looking that hash up in a rainbow table?

My understanding was ryan-c was describing a database that has a hash(global_salt+password). This concept of the global_salt was introduced specifically to baffle rainbow tables that attacked databases of hash(password)

ryan-c was describing how, if you have a database of salted hashes, the attacker can check every entry in that database against attempt, multiplying his efficacy by the number of people in that database.

To me, these are different threat vectors, rainbow-tables attacking hash(password), ryan-c describes attacking hash(global_salt+password), and to mitigate ryan-c's attack you must do hash(unique_user_salt+password)

can you explain to me how ryan-c's attack is analogs to a rainbow table?

The core of the attack that ryan-c is describing, is this:

> Say you have a password database with 10,000 users in it. You want to see if any of them used "Passw0rd$". Without salt, you compute the hash once and check it against all the users (perhaps with a bloom filter).

That is basically the same as a rainbow table attack. A conventional rainbow table attack looks like this:

for user in users: for hash in rainbowTable: (hash == user.hash)

The attack that ryan-c is describing looks like this:

for hash in rainbowTable: for user in users: (hash == user.hash)

They are still fundamentally the same concept.

A single hash per user is not any significant protection. As the article pointed out, the rig could compute 71000 bcrypt hashes per second, so even if you had 1M users, that would take less than 30s/password.

That calculation can't be done without knowing the bcrypt costs used to benchmark the rig and on the unknown password (I was pondering a similar calculation on another story and the only thing I found was a brief statement that pw crackers report performance for cost=5 (just by habit/convention).)

Fair enough, and it seems the same cost was used in this case! http://passwords12.at.ifi.uio.no/Jeremi_Gosney_Password_Crac...

Yes, I was thinking the same thing. I am really mystified by their saying this.

Reply on news.ycombinator.com