Page 1 of 1

Cryptographic strength of salts

Posted: Mon Feb 21, 2011 5:02 pm
by Mordred
My original article (draft, still unfinished) about password hashing: viewtopic.php?t=62782

MichaelR asked how to determine what is a suitable strength for salts and pepper in a password hashing scheme.

In the original article, this question is only briefly and inadequately addressed. I'll try to give a better answer and back it up with my thoughts on the matter:

Both the salt and the pepper (I use the the terms as I originally used them in the article - salt = per-user random value; pepper = per-system random value) should be as strong as the strength requirements of passwords in your login system. 8 chars of upper/lower/digits are about 48 bits which is okay for your everyday use (I think; your paranoia levels may vary). If you're an online banking site, go for the 128 bits. Anything in-between is a reasonable value.

First, what do we mean by "strength"? It means "resistance against a bruteforce attack (or an optimization thereof)". N bits of strength mean the attacker will have to make 2^N attempts to guarantee the recovery of the password.

Second, about the bits:
N = 48 bits is low, and borders the realm of the practical attacks. It requires 1-2 CPU years to bruteforce for fast hashes like MD5, which is expensive, but not prohibitive.
N = 128 bits is the recommended strength for future-proof (30 years if I recall correctly) rich-adversary bruteforce resistance. The reason longer hashes exist is the birthday paradox, which requires double-the-requirement bits of hash output. It affects the collision resistance of hashes which is used in other cryptographic contexts. In password hashing we only care about the irreversability of the hash function, so 128 should be enough. That said, this should not stop you from using more bits if you so wish.

Now, why would we need N-bit salt and pepper values for systems requiring N bits of strength?

First consider the trivial case of a 0-bit pepper a.k.a. password+salt scheme. I've already explained (in the article) why I think this is bad, so I won't do it again, but it's useful to observe the edge cases. So, the attacker has the salt and the hashed password+salt. How strong should the salt be to guarantee N-bits of strength for the hash, even for the password 'a' or '123456'? The purpose of the salt is to forcefully increase entropy and strengthen low-entropy plaintexts (which is a polite way of saying "your password is stupid"). Adding N bits of entropy to even the weakest plaintext will make the resulting hash at least N-bits strong.

This seems to imply that we only need strength(salt) + strength(pepper) = N. Here's why this isn't so:

Imagine a system with K-bit strong pepper and a breach of security like in our first case. The attacker knows all salts and all the hashed password+salt+pepper values. In order to recover a password, he needs 2^(N+K) bruteforce attempts. This is (by the definition of N) way out of his league / processing power, so he wants to try something more clever, an optimization of the bruteforce attack, whereby instead of exploring the entire space of possible passwords, you only try the ones that are most likely (another polite way of explaining people's lack of imagination where it comes to choosing passwords). This is known as a dictionary attack. The attacker has a list of D words, and D is way less than 2^N, the "size" of the space of all passwords. A reasonable D is in the vicinity of 2^28. Here's where the pepper comes useful, for every password the attacker needs D*2^K attempts. It is obvious that for K = N, that is, for peppers as strong as the strongest required passwords, the attacker again crosses the border of infeasibility. Why should we care if K is not as big though, D * 2 ^ K seems big enough by itself? Surely a K of ~30 bits should be enough (remember that D is already as big as 2^20-2^28 bits)?

Here's another possible attack: the attacker registers his own account in the system and then downloads the password database. He knows the password, the salt and the hashed password+salt+pepper for his account. The only unknown now is the pepper, which he can bruteforce until he gets the correct hash. Then, knowing the pepper and the salts for the other accounts he can successfully continue with a dictionary attack on them. This is why we need a N-bit pepper and nothing less will guarantee N bits of strength for the final hash.

P.S. How do we estimate the size of the password space in order to judge if our minimal requirements are adequate? We need two numbers: C, the number of possible characters in the password and L, the minimum number of letters. The size of the password space is C^L, and to find N we need to take the log2 of that value. You can easily find it with google like this:
6-letter lowercase passwords are C=26 L=6, space size = 26^6
1 < (26^6)/(2^28) < 2
So N is about 28.

Re: Cryptographic strength of salts

Posted: Mon Feb 21, 2011 5:20 pm
by Jonah Bron
Very good, quite educational. Thanks, Mordred :)

It's cool how we have experts in most areas of programming here:

Mordred: security guru
Ridgerunner: regex wizard
Josh: unit tester extraordinaire
...?