How long should a salt be to make it infeasible to attempt dictionary attacks?

Question

I'm designing an authentication system that works like the following:

1. User enters password
2. Salt is generated.
3. Password is hashed with whirlpool
4. Whirlpool hashed password concatenated with the plain salt
5. The concatenated version is hashed with sha1 and stored in the database.
6. I check the password is correct by hashing the password on the application layer, and then doing this (in MySQL):

MySQL

WHERE `Password` = SHA1(CONCAT('$hashedPassword',`Salt`)) AND [..]

At the moment my salt is 64 bytes. Will that be enough to make it infeasible to dictionary attack?

I'm sure sha1 has known vulnerabilities, but it's the only function available on my version of MySQL (5.1) that I can use on the database layer, rather than selecting the plain salt over a connection between the app and the database layer.

Hovey

64 bytes sounds way long enough. But I must be missing something. How do you verify the password later on? You need to repeat the hashing sequence using the same salt as when it was saved but you don't store the salt anywhere, only an SHA-1 of the salt plus other stuff. – Ia

The application layer is only concerned with whirlpool hashing the plain text password. It is stored in MySQL as SHA1(CONCAT(PHP_WHIRLPOOL('correct horse battery staple'), Salt)), where PHP_WHIRLPOOL takes place on the application. Hopefully that makes sense? :) – Hovey

Yes, that pseudocode matches what I thought you meant in the text. So I still don't understand how you repeat the operation for verification. I guess maybe you meant to say that both the SHA-1 result and the salt are stored in MySQL? – Ia

Yep, the sha1 result of the hashed password and the salt is stored in the password field. – Hovey

@Will Morgan: Soo, how are you going to verify a password then?? You need to store the salt in a separate data field. Also, the length of the salt doesn't matter too much, as long as it's long enough that the probability is very low that there already exists a rainbow table for it (8 bytes should be more than enough here). – Premise

Please see above answer - Salt references the field itself, not the literal string. – Hovey

@WillMorgan: Okay, I see that now. – Premise

I'd never use a salt longer than 16 bytes. Imagine your encryption and hashing algorithms never get broken so that brute force is all your adversary has. Once your salt is 16 bytes, the adversary is already smarter to brute force attack your key directly than to attack the salt, a successful attack against which still would not allow him to read your plaintext (though it would bring him closer to it). If your salt is reasonably close to random, I cannot think of any reason you ever need more bytes in it than are in the key itself. – Largely

Answer 1

I think you are misunderstanding the concept of a salt. Salts do not prevent or slow down dictionary and brute-force attacks significantly.

The whole point of using salts is to avoid the possibility that someone has already precomputed a dictionary/brute force attack for your password hashes (for example using rainbow tables). Thus, it only needs to be long enough to exclude the possibility that such a table already exists for a specific salt.

Considering the typical size of such a rainbow table, it is extremely unlikely that somebody already has precomputed such tables for salts of even small size like 8 bytes or so (consider the number of possible salts: 256^8 = 18446744073709551616). The premise is of course that the salts are randomly generated and that you don't use the same salt value multiple times. 64 bytes can't hurt, of course, there's nothing wrong with that.

However, if you want to make brute-force or dictionary attacks infeasible, it won't help you to use a longer salt. Instead, make your users to choose strong passwords and consider using key stretching.

Premise

Salts do not slow down attacks against a single user significantly, but they do slow it down against a large database. Consider having a salt-less database, now you start with common passwords, you compute the hash once, and check it against the entire database. Then onto the next common passwords. This doesn't work with salts. – Hemichordate

Answer 2

My copy of Practical Cryptography (Ferguson, Schneier) with a copyright date of 2003, suggests using 256 bits (32 bytes) for salt length. It says that 128 bits is "probably" okay, but, as it points out, bits are cheap. Given that, the relatively minimal cost of storing 64 bytes for a salt on disk for each password seems reasonable. It is probably overkill but it would not hurt.

You may also want to consider password stretching (repeat the hash function many times) to increase the computational complexity of attacking a password via brute force. Adding a few hundred milliseconds to the cost of checking the password can greatly increase the cost of a brute force attack.

Romain

The wikipedia article about "key stretching" is wrong. It describes key strengthening. Key stretching is a method that allows you to derive an output that is longer than the output size of the underlying hash function, and is one of the things that separate the PKCS#5 PBKDF2 from PBKDF1. – Deracinate

@HenrickHellström: What it describes as Key Stretching is consistent with how I have seen it described. I have also seen it called "Password Stretching" (as I referred to it here). – Romain

Well, that doesn't make it correct and such usage is bound to incur confusion among readers not familiar with cryptography. Key strengthening is what you do when you specify a high iteration count. Key stretching is what you do when you want a derived key of a specific length. If you use a PBKDF to produce a 256 bit key for AES-256-CBC encryption, you have performed key stretching but not necessarily key strengthening. You don't necessarily get 256 bits of security just because the derived key is 256 bits. – Deracinate

@HenrickHellström: I agree that it is important to use the terms correctly. Do you have available the definitive reference for these terms? I now notice that the accepted answer to this question uses the same term and references the same wiki page (or one that points to the same one). – Romain

I think the (ab)use of the term "key stretching" for key strengthening dates back to an article from 2005 by Frances F. Yao and Yiqun Lisa Yin, where they discuss iterations as a method for "stretching" the entropy of a password. The use of "key stretching" as a synonym for key expansion can be found e.g. here rfc-editor.org/rfc/pdfrfc/rfc5931.txt.pdf – Deracinate

Another example of using "key stretching" as a synonym for key expansion: tools.ietf.org/html/draft-krovetz-umac-01. One more: gnu.org/software/gnu-crypto/manual/api/gnu/crypto/prng/… – Deracinate

Answer 3

The salt determines how much space is required to store a pre-computed table (such as a Rainbow Table) that allows an attacker to quickly lookup a password for a given hash.

The number of hash iterations (not the salt) is what determines the time required for an attacker try each password in his dictionary of candidates.

Every bit of salt doubles the space required for the lookup table. So, 8 bytes (64 bits) would result in a space multiplier of 16 million terabytes—taking the total space well into the yottabyte range (and probably beyond the reach of most attackers).

Exit

Rainbow tables don't appear out of nowhere. They need to be computed. Using longer salts also significantly increases the time needed to create rainbow tables for passwords of up to a fixed length (up to the point where it becomes infeasible to actually generate those tables in the first place). Even if one had enough space to store the hypothetical Yottabyte table, he'd hardly have enough computing power or even storage bandwidth to generate it in the first place. – Premise

How would a rainbow table be generated to attack salted passwords? – Exit

Either you create separate tables for every possible salt value or (in the case of your hypothetical 8-byte hash) you find a reduction function that transforms a hash value into the cartesian product of the salt and password space. The latter would be a bit unnecessary, though, as the salt should be known to the attacker. However, that wasn't my point, I just wanted to add that the entropy of the salt not only exponentially increases the space required to store the lookup tables, it also increases the time to generate those tables exponentially, which is at least equally important. – Premise

This is all moot, because salt makes pre-computation infeasible. No one can afford the energy to compute the tables, or storage to keep them. – Exit

Answer 4

A salt is used to add additional random bits to the password to make certain attacks less efficient. So the more entropy the salt adds, the better.

Currently, PKCS #5 recommends a salt length of at least 64 bits entropy, the often recommended bcrypt uses 128 bits and you could even use more. But there certainly is a point where you won’t add additional practical complexity as the resulting complexity is already utopistic.

So you should have at least one unique salt per password so that only one password can be cracked at a time. At best, use a already proven password storage scheme.

Guffaw

Answer 5

Book:

Cryptography Engineering: Design Principles and Practical Applications

by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno

21.2.1 Salting and Stretching

Since bits are cheap, for simplicity we suggest using a 256-bit salt.

Girandole

Answer 6

8 Bytes are sufficent.

When you look in Linux (kernel version 3.16) in /etc/shadow, where the passwords of the user are saved, you can see a form like this:

$id$salt$encrypted_password

• id defines the hash algorithm

In my Linux-Version the salt is 8 digits so 8 bytes and i think the kernel developers know what they do, so i also use 8 Bytes for my salt, which comes from a Cryptographically Secure Pseudo Random Generator source. In Linux you can simply read /dev/random (which blocks when entropy is low) or /dev/urandom (which doesn't block).

For more information read the manpages for crypt.

Robinson

Answer 7

Consider 8 billion users for your application (the current world's population). Today the world's total storage capacity is around 10 ZB (source: IDC) and doubling every 4 years which would means around 13800 ZB in 2064. Consider a very small rainbow table of 1MB as the attack dictionary. A 64-bit salt will require 18446 ZB of storage for the rainbow tables (1MB * 2^64). Thus a 64-bit salt is more than sufficient for the next 41 years, and a 96-bit salt for the next 161 years. Using a slow hashing algorithm like Argon2 will also increase the initial cost of creating the tables.

Cata