By how much does the addition of a salt slow down a rainbow table attack?

Question

I understand that the addition of a salt provides some protection, because the attacker can no longer just look up the hash value in a rainbow table. However, it is still feasible to write a cracking program that looks up the hash, and then applies the salt to it, since the salt itself is necessarily unencrypted. Thus a salted password is still crackable, though cracking it will take longer. My question is how much longer will it take? Does the salt increase the time-complexity of cracking by a significant order of magnitude? What are the respective time-complexities of cracking an unsalted hash and cracking a salted hash using the same lookup table?

Another, somewhat related, question: I read in Practical Unix and Internet Security that the Modular Crypt function used in some Unix systems does not XOR the salt with the hash, and just tacks it onto the beginning. Doesn't this defeat the purpose of having a salt, since the unsalted hash can be trivially extracted from the password string and attacked as if the salt were not there in the first place?

Answer 1

For every single string attempt, the hashing algorithm must be performed.

So this really depends on what hashing algorithm is used.

If MD5 (bad idea for passwords) was used, the difference is small. If BCrypt was used, the difference is huge..

Regarding your second question : Salting is valuable since you could not use a Rainbow Table (the salt is part of the String before the hashing occurs) .. What you are looking for is usually called the "pepper" which is similar to the "salt" but not stored next to the hash (usually on a separate system or a file on that system).

Answer 2

If you want to built rainbow table for a list of salted passwords, you need to do so for each possible salt value. If the length of the salt is sufficient and if the salts are picked up correctly (i.e. never reused), then it pretty much makes rainbow tables useless.

Basically, if you have n bytes of salts, it increases the necessary operations and storage for building a set of rainbow tables by 2^n

Answer 3

Having salted hashes also makes sense for brute force and dictionary attacks. If the password hashes are not salted, the password cracking software can hash a potential password and check it against all hashes. If the hashes are salted, the attacker needs to calculate the hash for each user. So this increases the work for the attacker by the number of users.

does not XOR the salt with the hash, and just tacks it onto the beginning. Doesn't this defeat the purpose of having a salt, since the unsalted hash can be trivially extracted from the password string and attacked as if the salt were not there in the first place?

I don't really understand this part of the question. It is typical and secure to concatenate the password and the salt, hash that, and then store both the hash and the salt. So you store (salt, hash(salt | password)). Because the hash function is one way you can not eaasily derive hash(password). To crack this you would have to hash different values for password while using the same salt.