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.

sashoalm
  • 587
  • 1
  • 4
  • 12
  • 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
  • Also what do you know of the passwords? are they random? if not do you know what the password limits are? (eg. must be over 8 characters long, have 1 number and 1 special character and no character can be used more than 3 times) – Topher Brink Oct 20 '16 at 16:43
  • FLoating-point Operations Per Second (FLOPS)/password cracked is a really bad measure because you need to work out how many FLOPS per hash and then multiply the number of hash results that dont go into your table per ones that do by the FLOPS/hash to find out if it is over 1T. Also FLOPS are for specific types of operation, MD5 is worked out in 0 FLOPS, some processors are better at different types of operation which is why we have special graphics processors. 1/2 – Topher Brink Oct 20 '16 at 16:54
  • What you need to give us is how many useless hashes per useful hash you deem cost effective, This can be worked out by working out how much a password is worth. eg 1 password is worth $10, it costs 0.01¢ per password so hashes per password of 100000 hashes per useful hash which would make a table with only one 3 letter passwords efficient to crack 2/2 – Topher Brink Oct 20 '16 at 17:02
  • But why? In what way is it hard for you to just create a new one per password? – Neil McGuigan Oct 20 '16 at 17:54

2 Answers2

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.

John Wu
  • 9,181
  • 1
  • 29
  • 39
  • I found part of the answer to my question in http://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 06: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.

John Deters
  • 33,897
  • 3
  • 58
  • 112
  • 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 06: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