Is the time complexity to crack a hash of a salted password greater than the time complexity to crack a hash of an unsalted password?

Question

Assuming someone is trying to crack a leaked password through brute force (i.e., not using rainbow tables or commonly used password lists), is the following true?

O(cracking_salted_password) > O(cracking_just_password)?

If an attacker has managed to get access to my user database, they obviously also have the salt used when hashing my users' passwords, even though it's completely unique for each user. I would like to know if the time complexity also plays a role when someone is trying to crack a salted password through brute force.

Answer 1

Since salting really only creates a certain number of different values that a particular plaintext hashes to (i.e. instead of the password "password" hashing to value X1, with, for example, a 16-bit salt, there are 65536 different possible values that it can hash to), the effect of salting is really only to change the constant multiplicative factor in the equation. In other words, if your hash algorithm is O(n^2), then salting the input makes it k * O(n^2), which is really just the same as O(n^2). Yes, it will take more time to match the hash of a particular password, by a factor of up to however big your salt is, but it really doesn't change the O() complexity measure. The complexity measure isn't about how long it takes to perform a certain problem; it's about how much longer it takes to solve a problem of twice the size compared to the original problem.

Answer 2

I would like to know if the time complexity plays a role when someone is trying to crack a salted password through brute force.

No, the time complexity for a single password is not greatly increased by a salt. The salt does add a tiny constant amount to the encryption time, but not enough to cause problems.

That doesn't mean salting is useless. There are two important reasons for salting:

1) Users with the same password will look different. If an attacker sees that several users have the same password, he/she will assume that the password is not random, and attack that password first.

2) It makes Rainbow Tables impractical.

Before, you just needed one lookup table for all your password guesses. You could pre-compute that offline (and even re-use it between some systems!).

But when you add a salt, the attacker needs one Rainbow table per user. That makes the Rainbow Tables exponentially bigger, and can even make it quicker to use brute force rather than use Rainbow Tables!

So the salt may not help if you only have one user, but as you get more users, the salt is essential. It's better to always have the salt, since small systems often turn into big ones.

Answer 3

If there is a database with dozens of passwords as hashes and an attack by hashing a (large) set of possible values that make these hashes then the work can be applied to multiple hashes at a time

However, if the passwords are salted then each one is unique and the work needs to be repeated for each one