> I have a database of 1 million users.
Similar to Linkedin with 6.5m, we have a real-world case study.
> Regardless of what hashing algorithm I am using, if there is no salt I just need to hash the entire password space once, where the password space could be a dictionary attack or a brute force of passwords up to length 10 of letters, digits, and symbols.
When you say "entire password space" you're implying that there's a hard upper limit on the complexity of a user's password. Many sites do indeed restrict passwords to 8 or 10 characters, but that's horrifically broken.
Any not-completely-broken system has an password space so much larger than an attacker could search that it's effectively infinite. Note that even the silly system proposed here uses MD5 which accepts password longer than would even fit into available memory.
> If there is a salt, it means that after hashing the entire key space I only have the password for 1 user rather than all of them.
As described, the "key space" is effectively infinite, but luckily for the attacker some parts of it are far more richer to mine than others. This is where the easy-to-guess passwords lie.
So the attacker won't do anything as dumb as "hashing the entire key space". The attacker will search the most rewarding parts of the keyspace first.
> It means attackers must use targeted attacks and slows them down by a factor of # of users. Rather than having all my passwords in a day, an attacker gets access to one user's password per day (over the course of a million days). (Still not a good thing to happen)
For example, recent data breaches suggest that 50% of users will choose one of the 10,000 most-common passwords. So the attacker tries this set on all 1M of your users. That's 10,000,000,000 hash operations. A typcial rate for SHA-1 is 3.8 billion per second, per GPU. http://hashcat.net/oclhashcat-lite/
So our expectation is that the easiest 500,000 of your 1M accounts will be cracked in the first 5.2 seconds by a single GPU attacker. And this is approximately what happened with Linkedin, ISTR 60% of the passwords were reported cracked that first day.
But the rate of success slows down for the attacker and the remaining passwords begin to take exponentially longer. As of today, 90% of the Linkedin database is reported to have been cracked: http://arstechnica.com/security/2012/12/25-gpu-cluster-crack... So there are really only 65,000 hashes posing any difficulty at this point.
When a fast hash function is mis-used for password hashing, salt or no salt, there's not a case where "an attacker gets access to one user's password per day". The attacker cracks the majority of passwords in the first few seconds yet a small minority will never be cracked.
Salting doesn't save the database as a whole. Salting doesn't help the users with weak passwords. Salting doesn't even help the few users with very strong passwords, they wouldn't need salt in the first place. But for the users in the 60 - 90 percentile, it might buy them a few hours or days.