1

While I know that salt should never be reused, I'm interested in whether it is a significant problem if we only have a small number of hashes for which it is reused.

So let's say we have a table with N password hashes for which the same salt is used. The salt is unique but it's reused for all the hashes.

Does the table size have an impact on how much security is lost? For example a table holding only one password would obviously have zero security loss, while a table holding 10 passwords would be less secure, but not significantly so.

Does the amount of security loss depend of the size N, and at what point does a rainbow table become cost effective? At what point does security become seriously compromised? Is it N=10, or N=100, or N=1000?

Edit: Let's also assume that every password is unique in the table. We are not interested in any other kind of security loss except rainbow tables becoming more cost effective.

Edit 2: Let's say we measure computational expense in terms of teraFLOPS per password cracked. Cost-effectiveness really depends on the expected payoff of course, but let's just put an arbitrary value - we consider 1 teraFLOP / password cracked to be cost effective.

  • I don't know that you can quantify it, since password hash matches not only say the obvious (that two users have the same password), they indicate that they probably are one of the common passwords. I'm not sure you can quantify that increased chance, though (as there are other possibilities - duplicate 'standard' company passwords, rather than them being on the common password list) – crovers Oct 20 '16 at 15:34
  • @crovers Thanks. I'm only interested in quantifying rainbow-table cost effectiveness. I've changed my title. Let's just assume we are not interested in any other kind of security loss for the moment. – sashoalm Oct 20 '16 at 15:40
  • What do you mean by "cost effective"? how do you quantify "seriously compromised"? are we talking about accessing a nuclear weapon, bank accounts, a popular website, a small web forum or a home pc. The value of one account to access nuclear weapons is almost priceless, so almost anything would be cost effective and one breach would make it seriously compromised. facebook has 1000's of breaches per day but isnt seriously compromised but a small forum might be if 100 accounts are compromised. – Topher Brink Oct 20 '16 at 16:14
  • When you say "table" are you always referring to the rainbow table or a separate database table containing the users' hashed passwords? I'm really confused by the wording of your question. Are you wanting to compare real-time password cracking costs to rainbow table generation costs? – PwdRsch Oct 20 '16 at 16:25
  • @PwdRsch In the context of table size I mean the number of hashed values. – sashoalm Oct 20 '16 at 16:30
2

It depends

The purpose of the salt is to force a malicious user to use a dictionary attack instead of a rainbow attack. The reason for switching will depend on the attacker's intention and resources available.

Single user

If a hacker is trying to get the password for a single user, he wouldn't use a rainbow attack anyway. A dictionary attack is actually faster against one database row (unless the hacker is extremely unlucky).

Just targeting common passwords

If a hacker is only trying to find users who are using very common passwords, he can construct a pretty small rainbow table, one for each of your salt values. The more salts you have, the more tables he'll have to create. But there is no magic number. It will depend on the resources available to the hacker and the size of the password list he is looking for. Because each rainbow table would be small he may be willing to create hundreds or thousands of them.

Trying to get every single password

If a hacker is trying to crack every single password in your user base, he will need to construct a full rainbow table for each and every salt. If there are too many salts, he will decide it is easier just to switch to a dictionary attack. The threshold for this would probably be subjective and indicental... e.g. if the hacker had enough storage space for 100 rainbow tables, then using 101 salts would cause him to switch to a dictionary attack.

On the other hand, if your table has very few users (not few salts) then a dictionary attack may be faster anyway. When you have millions and millions of users then an attacker would be willing to go a lot further to avoid having to use a dictionary attack.

  • I found part of the answer to my question in security.stackexchange.com/a/60694/11957 - "Thus, a rainbow table is worth the effort only if it can be applied at least four times, on four distinct password hashes that shall be cracked. Otherwise, it is a big waste of time." So rainbow tables start being more effective than a dictionary attack at just N=4! That's a lot lower than I would have thought. – sashoalm Oct 21 '16 at 6:23
1

Static salt has the same effectiveness as no salt. You would have no defense against someone building a rainbow table. Users with colliding passwords would know whose password matched theirs. And it would not increase complexity or slow down the hashing in any way; it is no substitute for a pbkdf2-type algorithm.

If your system's security is relying keeping the salt a secret, then you need to treat it as a secret key, not a salt.

  • Wouldn't static salt protect against a precomputed rainbow table at least? At least the hacker will have to build a rainbow table, with unsalted passwords he can just reuse one. In fact, an unsalted password effectively makes N to be as big as all the passwords of all unsalted tables. It's as if all the unsalted hashes ever created share one big global table. – sashoalm Oct 21 '16 at 6:18
  • True, which is why I qualified it by saying "no defense against someone building a rainbow table". And to answer your edit regarding cost effectiveness, that question makes it seem like you consider it a case of "not outrunning the bear, just outrunning the guy you're standing next to." That's not a viable strategy, because once the attacker violates your site, what other sites do becomes irrelevant. The attacker may find the salt and exfiltrate your hashed entries, and then try an offline brute force attack against your data anyway - you simply never know. – John Deters Oct 25 '16 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.