Hacker News Reader

Comment by epenn | Hacker News Reader

Can someone explain to me how salts help a hashing algorithm secure itself against a rainbow table? For example, let's say my password is "justinbieber", which then has a salt prefixed to it which turns it into "iheartjustinbieber". If an attacker is unfortunately able to gain access to the hash of my password and the rainbow table he uses has an entry for hash("iheartjustinbieber"), how is that any more secure than the original?

Edit: changed "iheartjustinbieber" to hash("iheartjustinbieber") in the last sentence.

View on HN

You have to use the salt in a way that is not trivially breakable. Look up HMAC for the only approved way I know of to do it (whoops, dogma; you can probably invent many ways to do it, but HMAC is simple and considered secure, and I don't know anything else that is). Anyone suggesting just making the salt longer is missing the whole damn point of this debate: Cryptography is really hard to get right and smarter people than all of us have screwed it up. Thus, relying on only the best decisions checked by many others is not "dogma"; its the only sensible decision.

I completely agree with your "don't roll your own crypto" argument. But there's a difference between using a hash and inventing your own cryptography.

What kind of use did you have in mind with "trivially breakable"? hash(salt+pass) ?

My point is just that _some_ (not all) things considered unsafe in crypto is still good enough for this kind of use.

The wikipedia article on HMAC has a good discussion of why hash(salt+pass) isn't the best way to good.

"The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with MAC = H(key ∥ message). However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC. The alternative, appending the key using MAC = H(message ∥ key), suffers from the problem that an attacker who can find a collision in the (unkeyed) hash function has a collision in the MAC. Using MAC = H(key ∥ message ∥ key) is better, however various security papers have suggested vulnerabilities with this approach, even when two different keys are used.[1][3][4]

No known extensions attacks have been found against the current HMAC specification which is defined as H(key1 ∥ H(key2 ∥ message)) because the outer application of the hash function masks the intermediate result of the internal hash. The values of ipad and opad are not critical to the security of the algorithm, but were defined in such a way to have a large Hamming distance from each other and so the inner and outer keys will have fewer bits in common."

The why crypto works is that cryptographers -- some of the most OCD pedants you will ever know -- find a nano-scale fracture in one small relatively unimportant part of an algorithm, and then wrench it open into a gaping lava-spewing chasm of exploitation and credit card theft.

Please just use best practices, but realize that they will be periodically be updated.

Well, people have already talked about extension attacks in general, but to be specific: I can potentially calculate the state of the hash algorithm after the salt bytes have been processed, meaning I can precompute to reduce it to hash'(pass) — I consider that broken if you intended to create the function mac(salt,pass). If you have a salt per user, then that's not so bad, but why bother guessing?

Cryptography comes down to much more than using the right primitives. You also have to use the right implementations of those primitives (timing attacks), combined in the right ways (double stream cipher failure), and you have to be sure that the properties you want give you the protection you want (CBC without mac doesn't give you authentication). If you aren't using something with a wikipedia page that describes the entire system, and has some papers describing it and suggesting attacks on it, then you are inventing your own cryptography.

Actually, rainbow tables don't really matter anymore.

With the new GPU password bruteforcing techniques, it is easier and faster to just rent more Amazon EC2 machines. They're that fast.

Yes it's more expensive than rainbow tables (which are practically free), but not prohibitively so. Especially not for a criminal org bent on cc fraud, anyway.

It's more secure because if someone else has the password "justinbieber", and their salt is "ihate", then there will be two different hashes. The attacker will have to crack each individually to find out that they have the same password, instead of getting two for the price of one.

If your salt is something like rkD'O:$|tW:kU}SPuuLZ/X(iwtQzVG" then you've kicked up the size of the necessary rainbow table exponentially, or forced them to compute a custom rainbow table for _just_ your salt.

It's still better to be using a slower hash function, but a good salt helps.

btw it is important to stress that:

1) slow hash function. 2) per user random salt. 3) everything you want

don't help if the password is "apple".

So also you need:

4a) force users to passwords with required length / non alphanumerical chars, ...

4b) relax the security requirements.

If you don't use a salt, I can use one of the freely available rainbow tables online to look up your password from the sha1 hash. If you use a salt I cannot do that.

However, if you use the SAME salt for all your passwords, if I compromise your database I simply have to generate my own rainbow table of sha1(salt + actual_password) to use.

If you use a different salt for each user, I have to calculate one rainbow table per user, which is much more time consuming. That said, one user (an admin) is often enough to cause enough damage.

the salt should be a long complex string that is unlikely to be a prefix in your table. Also if the salt is just long this is enough, since the table will hold anyway passwords up to a given length.

I see what you mean. That will no doubt work for the time being, but it does make me wonder how "future proof" that method is. Calculating hashes for any number of character combinations is trivially parallelizable. Even today, price aside, it wouldn't take much effort to spin up a large number of machines on AWS or a similar service to increase the speed in which new hashes could be added to a rainbow table. Eventually the size of the rainbow table will increase to the point where it would also contain the long salt + hash.

There are only two possibilities to get more security: either don't use password based authentication or force your users to pick passwords of 16 chars or more (or smaller if you can force capitalized letters, non alphanum chars...).

In general the math is trivial:

    (alphabet_size ^ password_size) / hashes_per_second

gives you the amount of seconds needed to crack a password. You can set hashes_per_second to 1 billion for attacks that a private can do with little money. Maybe set it to 1000 billions per second if you want to protect yourself against bigger entities. But once you enlarge the alphabet_size and the password_size it is fast to reach a point where no brute force attack is feasible at all.

Do you mean generating a new rainbow table for each possible value of the salt?

Reply on news.ycombinator.com