Does a "salted hash" really help?

I've been trying to research more about salts to further understand the purpose and I'm having a difficuilt time getting anywhere. Here's my problem - I understand a salt can prevent two hashed passwords from appearing the same (because their salts are unique) in a database if the system is compromised, but what I don't get is how this makes dictionary attacks hard?

A salt is always stored in a database along with the hash(password,salt) value. If I wanted, I could retrieve a list of passwords and their associated salts. I can then take my dictionary attacking app, and run through converting each "common password" to the salted hash equivalent for a particular record, then continue that process for all records in the passwords table. Sure, it would take a little longer, but not *that* long, right?

A 2 GHz machine can do 2 billion cycles / second and an MD5 on a simple string takes roughly 64 cycles - so you're talking 3/10 of a second to hash 1,000,000 passwords with a particular salt. If you have 1,000 users to crack, you could get that done in, oh, a minute or less right?

I *know* I'm missing something here, I just can't figure out what. Please help me understand how salts really help here.

Thanks!

A salt will prevent the hashes from appearing similar when different users chose the same password or parts of a password. By using a diffrent salt, once one password is cracked you cant just scan the other hashes in the password list for matches. Even if 2 users use the same passsword you cant crack one and instantly crack the other, you will still have to retrieve the hash from the second one and create a hash list from your dictionary to crack the same word. This was probably much more effective against a dictionary attack when PC's were not quite as powerful but even now if you were forced to use brute force instead of a dictionary attack (Which you will if good password policy is enforced) then using unique salt will indeed take that long. Imagine this, if no salt(or identical) is used you only have to create one hash table from your dictionary and compare all passwords to it. If a unique salt is used you must create a new table for each password. Without a unique salt the entire password list or much of it can be cracked quite quickly after only a portion of the passwords have been discovered.

-Maestr0

Ok, I agree with what you are saying but lets say we're still doing a dictionary attack - a moderm computer could still crack passwords at an astoundingly fast rate, correct? When I started doing the math I was expecting something to be an exponential, making it exponentially more time consuming to crack with a salt, but it's not - it's completely linear so one could just throw more hardware at a pw database and crack as fast as he/she wanted to.

I agree about the strong passwords, that would help prevent this a great deal because it would eliminate dictionary attack as a possibility - even brute force would be impossible in that situation because you would have nothing to compare it with to determine if it was cracked (a good system will lock you out or luck itself up after several, let alone millions, of attempts).

I'm still eager (and hopeful!) to here if I've missed something in my logic :)

The unique salt will not prevent a dictionary attack from succeeding on a weak password. What it does do is attempt to protect strong passwords from being cracked by preventing the attacker from creating a codebook from the weak passwords discovered via the dictionary attack or just using every possible hash. Without the unique salt you can create a list of all possible hashes and then decrypt the ENTIRE password list.

-Maestr0

Heres a bit about

http://www.securityfocus.com/archive...6/2003-12-22/0

I don't understand how a code book of cracked weak passwords would be of any help in cracking a strong passwords (with or without a salt). Can you explain how a codebook would be helpful in cracking a strong password (without salts)?

I could see if we were using symmetric encryption how it might be helpful, but I'm not sure I get how this would be helpful for decrypting a 1-way hash.

You're right you cant build a codebook from the weak passwords (Sorry, I've been on an airplane for the last 5 hours and I think its melted my brain:) ) But you could say create just a bruteforce list of digests and then compare it to the password list and reveal them all, or a dictionary list may reveal multiple accounts with one digest. Once you use a salt there is no 'master' list that can be used to reveal all the passwords because the space of all possible combinations gets much larger.


-Maestr0

Ah, hah! Now we're getting somewhere. A brute-force list of digests would be like a very big dictionary - too time consuming to construct multiple times. Thanks!!