If an attacker has a database of 1,000 users' hashed passwords which are hashed with SHA-256 with a 128-bit salt and all of these users used 10,000 common passwords. How many hashes will the hacker need to do to recover all passwords?
I was thinking it would just be 1,000*10,000 = 10,000,000 hashes but I am not sure how the salt affects the computation in recovering hashes.
There are two things the attacker needs to do to recover a password:
Importantly, the hashing operation is much more expensive than the comparison, particularly if using an algorithm designed for the purpose like bcrypt, scrypt, PBKDF2, or Argon2 (SHA-256 is designed to be fast, for data verification, so is not a good choice). So we generally ignore the comparisons, and just count how many hashes need to be generated.
Without a salt, the same password always results in the same hash, so given a list of common passwords, the attacker can generate the hash for each of them once and compare the result to as many stored hashes as they want. In your example, that's a fixed cost of 10000 hash calculations to attack the full set of users.
With a salt, the same password results in a different hash every time it is stored. The attacker has to take their list of common passwords, add the salt stored against a particular user to each one, and calculate the hashes; then for the next user, they have to do it all again because the salt will lead to completely different hashes for the same password. In your example, that's 10000 hash calculations per user, so a total of 10000 x 1000 = 10 million hash calculations.
Note that these numbers are for the highest possible cost, where the correct password is always the last one the attacker tries. In reality, there's a possibility that the correct password is the first one tried, or the 100th - eventually, we can expect it to average out to testing about half the list each time. For the unsalted case, this doesn't make any difference: the attacker can't do much better than calculating all 10000 hashes, then comparing half of them on average against each user. But for the salted case, they can calculate them one at a time and move onto the next user once they find one, so the expected total cost is just over 5 million hash calculations.
This is of course a simplified model of reality: we're assuming that each user picked at random from exactly the same list of 10000 passwords; in reality, some of those passwords will be more common than others, so the attacker can try those ones first, further reducing the number of hashes they need to calculate.
It also assumes that the attacker wants to crack all the passwords in the stolen database. If they just need one account to compromise, they can perform their search "breadth first", trying the single most common password against all hashes, then moving onto the next most common password, and stopping once they have any match.
[Hat tip to fgrieu for pointing out several of the above caveats.]
Salting makes you have to try each candidate password from the wordlist against each hash. So it's 1000 target hashes x 10000 words, worst case.
