Why do salts make dictionary attacks 'impossible'?
Update: Please note I am not asking what a salt is, what a rainbow table is, what a dictionary attack is, or what the purpose of a salt is. I am querying: If you know the users salt and hash, isn't it quite easy to calculate their password?
I understand the process, and implement it myself in some of my projects.
s = random salt
storedPassword = sha1(password + s)
In the database you store:
username | hashed_password | salt
Every implementation of salting I have seen adds the salt either at the end of the password, or beginning:
hashed_Password = sha1(s + password )
hashed_Password = sha1(password + s)
Therfore, a dictionary attack from a hacker who is worth his salt (ha ha) would simply run each keyword against the stored salts in the common combinations listed above.
Surely the implementation described above simply adds another step for the hacker, without actually solving the underlying issue? What alternatives are there to step around this issue, or am I misunderstanding the problem?
The only thing I can think to do is have a secret blending algorithm that laces the salt and password together in a random pattern, or adds other user fields to the hashing process meaning the hacker would have to have access to the database AND code to lace them for a dictionary attack to prove fruitful. (Update, as pointed out in comments it's best to assume the hacker has access to all your information so this probably isn't best).
Let me give an example of how I propose a hacker would hack a user database with a list of passwords and hashes:
Data from our hacked database:
RawPassword (not stored) | Hashed | Salt
--------------------------------------------------------
letmein WEFLS... WEFOJFOFO...
Common password dictionary:
Common Password
--------------
letmein
12345
...
For each user record, loop the common passwords and hash them:
for each user in hacked_DB
salt = users_salt
hashed_pw = users_hashed_password
for each common_password
testhash = sha1(common_password + salt)
if testhash = hashed_pw then
//Match! Users password = common_password
//Lets visit the webpage and login now.
end if
next
next
I hope this illustrates my point a lot better.
Given 10,000 common passwords, and 10,000 user records, we would need to calculate 100,000,000 hashes to discover as many user passwords as possible. It might take a few hours, but it's not really an issue.
Update on Cracking Theory
We will assume we are a corrupt webhost, that has access to a database of SHA1 hashes and salts, along with your algorithm to blend them. The database has 10,000 user records.
This site claims to be able to calculate 2,300,000,000 SHA1 hashes per second using the GPU. (In real world situation probably will be slower, but for now we will use that quoted figure).
(((95^4)/2300000000)/2)*10000 = 177 seconds
Given a full range of 95 printable ASCII characters, with a maximum length of 4 characters, divided by the rate of calculation (variable), divided by 2 (assuming the average time to discover password will on average require 50% of permutations) for 10,000 users it would take 177 seconds to work out all users passwords where the length is <= 4.
Let's adjust it a bit for realism.
(((36^7)/1000000000)/2)*10000 = 2 days
Assuming non case sensitivity, with a password length <= 7, only alphanumeric chars, it would take 4 days to solve for 10,000 user records, and I've halved the speed of the algorithm to reflect overhead and non ideal circumstance.
It is important to recognise that this is a linear brute force attack, all calculations are independant of one another, therfore it's a perfect task for multiple systems to solve. (IE easy to set up 2 computers running attack from different ends that would half the exectution time).
Given the case of recursively hashing a password 1,000 times to make this task more computationally expensive:
(((36^7) / 1 000 000 000) / 2) * 1000 seconds = 10.8839117 hours
This represents a maximum length of 7 alpha-numeric characters, at a less than half speed execution from quoted figure for one user.
Recursively hashing 1,000 times effectively blocks a blanket attack, but targetted attacks on user data are still vulnerable.
It doesn't stop dictionary attacks.
What it does is stop someone who manages to get a copy of your password file from using a rainbow table to figure out what the passwords are from the hashes.
Eventually, it can be brute-forced, though. The answer to that part is to force your users to not use dictionary words as passwords (minimum requirements of at least one number or special character, for example).
Update:
I should have mentioned this earlier, but some (most?) password systems use a different salt for each password, likely stored with the password itself. This makes a single rainbow table useless. This is how the UNIX crypt library works, and modern UNIX-like OSes have extended this library with new hash algorithms.
I know for a fact that support for SHA-256 and SHA-512 were added in newer versions of GNU crypt.
To be more precise, a dictionary attack, i.e. an attack where all words in an exhaustive list are tried, gets not "impossible", but it gets impractical: each bit of salt doubles the amount of storage and computation required.
This is different from pre-computed dictionary attacks like attacks involving rainbow tables where it does not matter whether the salt is secret or not.
Example: With a 64-bit salt (i.e. 8 bytes) you need to check 264 additional password combinations in your dictionary attack. With a dictionary containing 200,000 words you will have to make
200,000 * 264 = 3.69 * 1024
tests in the worst case - instead of 200,000 tests without salt.
An additional benefit of using salt is that an attacker cannot pre-compute the password hashes from his dictionary. It would simply take too much time and/or space.
Update
Your update assumes that an attacker already knows the salt (or has stolen it). This is of course a different situation. Still it is not possible for the attacker to use a pre-computed rainbow table. What matters here a lot is the speed of the hashing function. To make an attack impractical, the hashing function needs to be slow. MD5 or SHA are not good candidates here because they are designed to be fast, better candidates for hashing algorithms are Blowfish or some variations of it.
Update 2
A good read on the matter of securing your password hashes in general (going much beyond the original question but still interesting):
Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes
Corollary of the article: Use salted hashes created with bcrypt (based on Blowfish) or Eksblowfish that allows you to use a configurable setup time to make hashing slow.
Yes, you need just 3 days for sha1(salt | password). That's why good password storage algorithms use 1000-iteration hashing: you will need 8 years.