Hacker News Reader

Comment by mrb | Hacker News Reader

It is possible to tell the passwords were unsalted because: "We compared encrypted password hashes and discovered that 11 passwords were shared by over 10,000 players each" and one of the points of salting is to make impossible to identify identical passwords from the hashes.

View on HN

Not really. You get that with per-password salting, but having a single salt for your whole database is not uncommon. Since the main point of salting AFAIK is to ward off rainbow tables, it's better than nothing.

EDIT: As noted in the comments, the way I put this originally was kind of flip and misleading and I apologize for creating confusion. My point was that I've seen a number of places do it that way, so just throwing at at your problems doesn't necessarily fix everything.

A single salt for the whole DB is not salting. It is no different than a (custom) hash function, which does not prevent identifying identical passwords, and which does not prevent rainbow table cracking.

Preventing rainbow table attacks is exactly what a custom hash function would do. You can't precompute hashes if you don't know the hash function. But you're right that a single salt in conjunction with a known hash function generally provides little additional protection, although this depends on the size of the salt.

A good cryptographer assumes that a custom hash function does not prevent rainbow table attacks, because he should not assume the algorithm will remain secret (security by obscurity, yadi, yada).

The right way to prevent a rainbow table attack is to computationally prevent it via unique salts.

Yes but it's not like the random hacker has a 600 gig rainbow table for MD5('DATSALT' + PW). If you REALLY want to do the right thing when it comes to storing passwords, you need to use a hash algo that is computationally hard enough to brute force, it should take at least .5 sec on a good computer to compute. Every couple years, you should add another pass of the algorithm, ie. F(F(X)), to compensate for faster computers. By adding the extra pass, you won't need the original password to generate the new, revised, stronger custom hash algo. If you do this, in 10 years your passwords will still be secured. Also, salt your passwords with each a unique at least 100 random bytes, shouldn't need to be said.

Not an expert, but I believe rehashing the hashes is a good way to decrease entropy.

As long as the salt is added for each recursive iteration, it should destroy any kind of cryptographic hints given by hashing a hash. So you shouldn't be doing F(F(F(X))) rather it should be F(SALT + F(SALT + F(SALT+X)))

But anyhow, I was talking about increasing the security of an already-existing hash algorithm. Even if the recursive hashing isn't that much more secure, it definitely isn't less secure than one pass...

Unique salts are absolutely the correct way to rainbow-proof a database of hashes[1]. But a novel hash function will still do the trick and isn't comparable to using a single salt across the entire database, as you originally claimed.

Reverse engineering a novel hash function, while theoretically possible, isn't a capability possessed by the folks dumping passwords from LinkedIn or Riot. And even if it were, doing so would cost more than would be gained by compromising those passwords[2].

Thus, in practical terms, a novel hash function is a great way to undermine attackers, not unlike using Linux or opening files in non-standard viewers (LibreOffice, Nitro PDF Reader, etc.).

1. And if you have access to a good cryptographer, you should absolutely roll a novel hash function as well. Security through obscurity is the proverbial cherry on top of your defensive sundae, i.e. it's only a bad thing if you rely on it exclusively.

2. Not to mention that the whole point of rainbow tables is that they've already been computed. If an attacker has to reverse engineer a hash function to create a rainbow table, that largely defeats the rainbow table's purpose.

1. No. A good cryptographer will tell you to not re-invent crypto and to use existing peer-reviewed hash functions. This is why the NIST is hosting an open competition for selecting the future SHA-3.

2. This is exactly what happened with the custom proprietary "obscure" GSM A5/1 encryption algorithm. First it was reverse engineered (based on a leak), then David Hulton and Steve Muller created rainbow tables for it. The fact that it was a custom algo did not defeat the rainbow table's purpose.

There are many ways a custom hash algo designed by a company could end up being used across multiple of its password databases, and could subsequently be leaked, making the generation of rainbow tables possible and valuable (by rogue employees or hackers), that relying on the obscurity of a custom algo is a bad idea. As you recognized, salting is the ultimate protection. So there is no point in talking about alternatives.

But a novel hash function will still do the trick and isn't comparable to using a single salt across the entire database, as you originally claimed.

I'm not sure I understand this point, what is the criteria for a function to be novel?

This function produces different hashes from most other hash functions, eg, it is new and possibly novel, but is equivalent to using a single salt across a database:

    function novelHash(password) {
        return md5("novelHash" + password);
    }

A few years back I started a project to create rainbow tables for Oracle hashes with friends. The old Oracle hashing algorithm was pretty weak, but used the username as a salt. Within a few weeks we had rainbow tables for lots of default oracle accounts.

Moral of the story is to use a unique salt per account, but don't roll your own crypto in the process.

What?

So if I have access to that salt, I generate a new rainbow table and get a huge percent of your users.

The point of salting is to make rainbow tables no more efficient than brute forcing. If each user has a unique salt, there's literally no benefit to generating a rainbow table.

Out of curousity - is it a salt if you do something like this:

salty = md5(md5(pw) . pw . 'poniesaremagical' . md5(username));?

It is per-user... how is it different than using a timestamp which will be as unique as username?

Technically yes, but don't use md5 for anything security-related ever. It's broken. http://www.mscs.dal.ca/~selinger/md5collision/ is just one example. (I also remember reading some years ago that md5s within md5s can make the resulting hash more vulnerable to certain attacks but I don't have any formal knowledge in cryptology to say for sure.) Use bcrypt/scrypt and you're automatically protected from both rainbow tables and brute force.

H(Salt . H(Password)) is a lot like an hmac (minus the secret part and the padding). I'm not sure about the pre-image vulnerability mentioned on wikipedia's md5 page, but as for collision vulnerabilities, according to wikipedia's hmac page, "HMACs are substantially less affected by collisions than their underlying hashing algorithms alone. Therefore, HMAC-MD5 does not suffer from the same weaknesses that have been found in MD5."

Yes, as long as you use some salt data that is unique per user (timestamp, random number/guid/whatever) (you have to store that obviously), then it's fine. The problem is acting as if a site-wide salt is an ok-thing. It's not.

Incidentally, as the guy who started this whole thing, I'd just like to note that I actuslly agree with this. When I said they were "OK" or whatever, I meant it in the sense of "I guess it's good they're doing something," not like I'd recommend it. Please nobody get that idea.

It's not salty enough for my taste. What you've done is no different than:

  H(H(Password) + Salt)

If I steal your db and have another db that contains your user's unsalted password hashed with the same hash function, I can easily test if the same password is used in both places, simply by replacing H(Password) with the other hash. This leaks information and provides incentive to continue trying to crack the easiest target, if I really want what you have.

A simple change makes this comparison impossible:

  salty = H(H(Password + Salt)

Now there's no place to plug in the other hash, so I can't tell if the accounts share passwords until I successfully crack one and try it on the other. I might not bother and focus on lower hanging fruit.

Always assume your salting method is public, even if you make attempts to keep it secret. And remember that your site isn't in isolation; your user and every site they interact with are also potentially weak links in the chain.

Note that the examples above are oversimplified. You should look to a better authority on how to properly store passwords. In a future leak, we'll be surprised that the sites involved only salted their passwords.

Then the rainbow table can only be used with this specific site. This makes it no more efficient than brute forcing. You can store the hashes yes, but you can also include the cracked passwords in the dictionary and it takes only slightly more time to compute them even with unique salts.

Site-wide salting has almost the same security as per-user salt, as long as the salt is not leaked or cracked before the database is leaked for pre-computation.

>This makes it no more efficient than brute forcing.

Jesus, no. It absolutely does make it more efficient than brute forcing each password.

I compute one rainbow table that I can run against 10,000 users. Or I brute force 10,000 users' passwords because they have unique salts.

>_< God, I need to just accept the fact that people are going to talk out their ass about this and stop trying to get people to spread bad, insecure information.

oh sweet jesus of irony, you're the guy that was wrapped up in Bitcoinica.

Oh, I got it. My brain wasn't working then.

Don't worry, I use per-user salts for all my web projects following all security best practices that I know.

A database-wide salt makes cracking the database as hard as forcing one password. You only need to do the computation once and then you have a super-quick lookup for all the other hashes. Per-entry salts totally bust that.

normally salt is some random string unique for each user, but you have to store the salt of each user in database for authentication, if your database is hacked and they got both your hash and salt, it is really no difference between salt and no-salt

Parent is talking about the League of Legends North American region which does not necessarily share its authentication code base with the European regions which were the ones compromised.

Ok. That would make sense. The parent seemed to claim the leaked passwords were salted.

You left out an 'un' in front of salted. Or you're wrong. I'm hoping you just mistyped. [edit :)]

Oops. Fixed. Thanks.

Reply on news.ycombinator.com