Is forcing complex passwords "more important" than salting?

Question

I've spent the past 2 hours reading up on salting passwords, making sure that I understood the idea. I was hoping some of you could share your knowledge on my conclusions.

---

If I'm an attacker, and I gain access to a user database, I could just take all the per-user salts present in the table and use those to create my rainbow tables. For big tables this could take a long time. If I could cut the list down to users of interest (admins, mods) I could use much bigger dictionary lists to create the rainbow tables, raising my percentage of hits...

If this is true then it seems that salting really doesn't do all that much to help. It only marginally slows down an attacker.

I know ideally you would want to force complex passwords and salt them with unique and random strings, but forcing complex passwords can annoy users (i know it annoys me), so a lot of sites don't do it. It seems sites are doing their users a disservice with this, and that forcing complex passwords is a lot more important than a good salting method.

I guess this isn't so much a question, but a request for others knowledge on the situation.

Verlaverlee

You need to specify the particular encryption usage you have in mind, as well as the type of attacks you wish to prevent. For example, you indicate taking "all the salts in the table", it is unclear as to what this means. – Vivica

I didn't really have a particular encryption method in mind. I was more curious on the general idea of salting and best practices. Edited it to hopefully make it more clear, thanks. – Verlaverlee

Answer 1

The point of a salt is that an attacker can no longer use a pre-existing dictionary to attack any user in your system. They have to create a brand new dictionary for each user using that user's salt, which takes time and effort. If you learn about a breach before dictionaries are created for all users of your system, you have time to act. (Alert users that their log-in credentials must be changed, which should generate a new random salt.)

I would say that you should use both a salt and the most complex password (pass phrase, really) that your users will tolerate. Even still, salting is a fundamental security measure, and you can't really afford to do without it.

Licketysplit

Agreed, salting should not be optional. It takes out a whole attack vector that could compromise an entire security system, where as allowing weak passwords would only compromise individual accounts. – Mimesis

You should also mention that there's no point creating a per-user dictionary - faster to just crack their password brute-force. – Soothsay

The most important point here is that creating that brand-new dictionary takes just as long as it would to bruteforce that user's salted hash directly - rainbow tables are only an optimisation if the same table can be used against multiple password hashes. – Codeine

Answer 2

Is keeping properly hydrated more important than breathing?

Deration

Answer 3

I tend to favor an approach that uses a salt per user, global salt (salt per algorithm), and modest password complexity rules (8+ characters with some combination of at least 2 uppercase/digit/punctuation characters) for most web sites. Using salts requires the generation of a rainbow table per account you want to break -- assuming unique salts per user. Using a global salt requires that you both compromise the DB and the application server. In my case, these are always two separate systems. Using password complexity rules helps to protect against simple, easy to guess passwords being used.

For accounts with more privileges, you may want to enforce greater password complexity. For example, admins in our AD forest are required to have a minimum 15 character passwords. It's actually easier than shorter passwords because it pretty much forces you to use a pass phrase rather than a password.

You also want to instruct your users in how to create good password, or better yet, pass phrases and to be aware of various social engineering attacks that circumvent all of your technical means of protecting your data.

Bizarre

I never really understood the "global salt." Suppose you use a per-user salt of 8 bytes chosen by a good RNG. What further value does the global salt provide? – Understood

+1 - A tiered policy is a great idea for protecting privileged accounts. – Licketysplit

@Understood - typically the per-user salt is stored in the DB. If you compromise the DB, it is only a matter of time and resources to crack the passwords. A global salt stored in the algorithm requires that they crack the app server as well as the DB. An added benefit is that a cracker needs to check twice as many permutations of the three when hashing. – Bizarre

A+1 on the pass phrase idea. beside it's easier for human to remember, at the same time the length will add complexity to the password. – Clog

Thanks, i like the idea of having a per-user salt and a global salt. – Verlaverlee

Answer 4

Okay, let's look at real figures:

A single Nvidia 9800GTX can calculate 350 million MD5 hashes / second. At this rate, the entire keyspace of lower and uppercase alphanumeric characters will be done in 7 days. 7 chars, two hours. Applying salting will only double or triple these times depending on your algorithm.

Cheap modern GPUs will easily boast one billion MD5 hashes / second. Determined people typically link up about 6 of these, and get 6 billion / second, rendering the 9 character keyspace obsolete in 26 days.

Note that I'm talking about brute force here, as preimage attacks may or may not apply after this level of complexity.

Now if you want to defend against professional attackers, there is no reason they can't get 1 trillion hashes / second, they'd just use specialized hardware or a farm of some cheap GPU machines, whichever is cheaper.

And boom, your 10 character keyspace is done in 9.7 days, but then 11 character passwords take 602 days. Notice that at this point, adding 10 or 20 special characters to the allowed character list will only bring the cracking time of a 10 character keyspace to 43 or 159 days, respectively.

See the problem with password hashing is that it only reduces time until your futile doom. If you want something really strong, but still as naive as stored hashed passwords are, go for PBKDF2.

Then there is still one more problem, will the user use this "strong" password you forced him to use on all his other sites? If he doesn't save them in a master password file, he most certainly will. And those other sites wont use the same strong hashing algorithms you use, defeating the purpose of your system. I can't really see why you want your hashes to be super strong if it isn't to stop users from using the same password on multiple sites; if an attacker has access to your hashes, you most likely already lost.

On the other hand, like I will repeat and repeat again to people asking questions about how "secure" their hashing scheme is, just use client certificates, and all your problems are solved. It becomes impossible for users to use the same credentials on multiple sites, attackers cannot break your credentials without modifying them, users cannot easily have their credentials stolen if they store them on a smart card, etc etc.

To naively answer your question: a strong password is only backed by a strong hashing algorithm.

Restricted

"Applying salting will only double or triple these times depending on your algorithm." - uh, salts aren't designed to make it harder to crack individual passwords, but rather to prevent the use of a pregenerated table of password hashes. – Soothsay

I know, I was talking about brute force time as preimage attacks aren't generally useful if there is a strong random salt system. – Apiarist

A known salt won't change the time it takes to search a given space at all. But since we're performing thousands of iterations of the hash, boom, a 10 character keyspace takes decades. – Understood

Yes, but you forget that the password for one site is usually not that important, unless the target has the same password on multiple sites, in which case a strong password hashing scheme will not help at all. Otherwise, if the password is that important for just your site, you most likely already lost... – Apiarist

Anyways, you are right that a strong, iterated, salted hash is ideal for places where you can't use real authentication such as client certificates, but I would not and never have used the inferior hashing technique in a real scenario (except when hybrid with client cert). – Apiarist

Answer 5

With the sole exception of a requirement for a long string, every constraint reduces the size of password phase space. Constraints cause a decrease in complexity, not an increase.

If this seems counterintuitive, consider that you are providing a bunch of reliable assumptions for the cracker. Let me illustrate this point with a true story from my misspent youth:

In the early days of twin-primes encryption processors were so slow that people tended to use int32 arithmetic for speed. This allowed me to assume the primes were between 0 and four billion. People always picked large primes because conventional wisdom held that bigger was better. So I used a pre-computed dictionary of primes and worked down from a known ceiling, knowing that people generally chose keys close to that ceiling. This generally allowed me to crack their key in about 30 seconds.

Insist on long pass phrases, and use salting, with no other constraints.

When people say "sophisticated" techniques they often mean complicated. A transformation can be very complicated and yet be commutative, and unfortunately if you don't know what that means then you're not in a position to assess the merits of the technique. Complexity of algorithm lends only security by obscurity, which is a bit like getting a house out of town and not locking the doors.

Effy

But doesn't that simplify cracking? If the minimum password length is 2, then it is pretty certain some users will select a 2 character password. Anymore, that's milliseconds for a brute force password attack, or at least a couple seconds for an unknown salt of 12 bits. – Lemay

By minimum password length I meant enforcing fairly long passwords. – Effy

Answer 6

Use sophisticated techniques like salthash to keep your users' private information safe.

But don't obstruct your users. Offer suggestions, but don't get in their way.

It's up to your users to pick good passwords. It's up to you to suggest how to pick good passwords, and to accept any password given and keep the user's information as safe as the password given permits.

Ribwort

You have a responsibility to your other users to ensure that all users maintain good passwords. As the importance of the data increases, the importance of enforcing good policies increases. Your data is only as secure as your least secure user's access to it. – Bizarre

As the importance of the data increases and as the user in question gains more access to more data of more importance, one might consider enforcing strong passwords. So long as each user's account contains only his own data, that user is responsible for his own account. – Ribwort

Answer 7

Both salted passwords and complex passwords are necessary for real security. Typically rainbow tables aren't created on the fly to attack a specific site, but are rather precomputed. It would be far more efficient to simply brute force a password than to generate a look up table based on a particular salt value.

That being said the purpose of a hash it to ensure that an attacker can't recover a password if your database is compromised. It does nothing to prevent an attacker from guessing an easy password.

Requiring password complexity is really a matter of the type of site/ type of data you are protecting. It will annoy some users, and cause others to write their password out on a post it and stick it to their monitor. I'd say it is absolutely essential to use a strong hash and salt on your end- neglecting to do so exposes not only your site, but completely compromises every user who recycles username/ password combinations.

So in my opinion salting is mandatory regardless of the security level of your site. Enforced password complexity is good for high security sites - but is definitely more situational. It won't guarantee good security practices on the part of your users. I'll also add that requiring a secure password for a site that doesn't require it can do more harm than good as it is more likely that a user will recycle a high-security password that they use on other more essential sites.

Hummocky