# How to calculate the needed encryptions in salted passwords?

Consider if a 16-bit salt is used, and it is uniformly applied over a very large password file (200,000 entries). An attacker wants to see if one particular password (say, "bubba") is used by any of the password entries. How many encryptions must be calculated, and how many comparisons must be made (of their generated-hash vs. stored hash values)?

Assume the attacker has the stored-hash-values, but he does not know which salt is used for any individual password hash. In other words, they can see /etc/passwd (so they know the 200,000 usernames), and have only gained access to the hash (but not the salt-portion) of what is stored in /etc/shadow.

## migrated from security.stackexchange.comFeb 9 '17 at 7:43

This question came from our site for information security professionals.

• Does your scenario involve all passwords using the same salt or unique salts? – PwdRsch Feb 7 '17 at 18:54
• Sounds like the same salt. But does the attacker know the salt? Salts are typically considered a public part of the security model. In which case an attacker only needs to compute one hash, because all passwords use the same salt. Hence the requirement for salts to be globally unique. – Stephen Touset Feb 7 '17 at 19:11
• @StephenTouset His question does specify the attacker doesn't know the salt in this situation. I just got mixed messages from the question on whether the salt was shared amongst all passwords or not. – PwdRsch Feb 7 '17 at 19:15

In your case, you say the salt only has 16 bits of entropy, which is pretty weak.

To see whether 'one particular password' was used, the attacker would have to attempt 65,536 possible Salt combinations, for each 'particular password' that must be tested. The number of users does not matter because we have now established a need to brute-force the (weak) salt, and only try a single particular password.

On the other hand, with a properly implemented modern Password Hash, where sufficiently strong (e.g. 72 bits of entropy) salt is used, if the attacker fails to acquire the salt, then there would be no practical way for him to brute-force the hash.

• I like your answer but Rpach17 did say they also wanted to know how many hash comparisons must be made. That's where the number of users figures in, so I would suggest updating your answer to include that number for every salt tried. – PwdRsch Feb 7 '17 at 18:56
• The number of users does not figure in when brute-forcing the Salt. Only when brute-forcing the Password. – Bryan Field Feb 7 '17 at 21:33
• Edit suggestions and/or competitive answers are welcome. :-) – Bryan Field Feb 7 '17 at 21:34

65536 (16^2). The number of users in the file is irrelevant.

The intended purpose of a salt is to prevent a cracker from gaining access to multiple accounts at the same time. For example, let's say two users have the same password of 'Password123'. If the hashes are unsalted, then both hashes will be the same. This means that once the cracker has cracked the password of the first user, he does not need to expend any additional effort to crack the second user's password. If a salt is used, then the same password will yield two different hashes. This means that cracker must expend the same level effort (an oversimplification) to crack the second user's password as he did the first.

Storing the salt in a separate datastore from the hash does increase the overall robustness of the security system, but it does not increase the security against the threat model which salts were designed to protect against. Weigh the potential security benefit of your system against the complexity that storing the salt separately adds to the system.

• I think maybe a little bit of more details would be useful (for this particular user). Note, $2^16 = 65536$. – peterh says reinstate Monica Feb 7 '17 at 18:13
• So assume the attacker has both /etc/passwd and /etc/shadow, so they know the salt and complete hash for each user. To do a complete dictionary attack, with a 50,000 word dictionary, how many encryptions, and how many comparisons are required? – rpach17 Feb 7 '17 at 20:11
• @rpach17 Wait, you've completely changed the premise of your question by saying the attacker now knows the salt for each user password, and added an element about multiple password guesses from a dictionary. You should edit your original question if you're looking for a different answer. – PwdRsch Feb 7 '17 at 20:43
• Looking for the answer to a different question, but along the same lines as the original question – rpach17 Feb 7 '17 at 21:03
• Wonderful extension. – peterh says reinstate Monica Feb 8 '17 at 1:10