1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Does your scenario involve all passwords using the same salt or unique salts? $\endgroup$
    – PwdRsch
    Feb 7, 2017 at 18:54
  • $\begingroup$ 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. $\endgroup$ Feb 7, 2017 at 19:11
  • $\begingroup$ @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. $\endgroup$
    – PwdRsch
    Feb 7, 2017 at 19:15

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – PwdRsch
    Feb 7, 2017 at 18:56
  • $\begingroup$ The number of users does not figure in when brute-forcing the Salt. Only when brute-forcing the Password. $\endgroup$ Feb 7, 2017 at 21:33
  • $\begingroup$ Edit suggestions and/or competitive answers are welcome. :-) $\endgroup$ Feb 7, 2017 at 21:34
2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I think maybe a little bit of more details would be useful (for this particular user). Note, $2^16 = 65536$. $\endgroup$
    – peterh
    Feb 7, 2017 at 18:13
  • $\begingroup$ 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? $\endgroup$
    – rpach17
    Feb 7, 2017 at 20:11
  • $\begingroup$ @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. $\endgroup$
    – PwdRsch
    Feb 7, 2017 at 20:43
  • $\begingroup$ Looking for the answer to a different question, but along the same lines as the original question $\endgroup$
    – rpach17
    Feb 7, 2017 at 21:03
  • $\begingroup$ Wonderful extension. $\endgroup$
    – peterh
    Feb 8, 2017 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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