3
$\begingroup$

I feel like I am missing some information regarding salting. How does one choose the salt? If you reuse the same salt for all passwords, can it just be figured out and then used in conjunction with normal brute-forcing. And what are the common ways to generate the salt?

$\endgroup$
3
$\begingroup$

Salt is not secret. This is the open part of the encrypted data. It should be open to decrypt the data.

Reusing the salt is not good. The whole purpose of salt is to prevent usage of rainbow table. If an attacker has descrypted one text, it should not be easy to use it for other texts. Where as if you reuse the same salt for many texts, it may make sense for the attacker to create a rainbow table because he can then decrypt your multiple texts via the same rainbow table.

To your question, how salt is chosen: As @Swashbuckler said, it should be random. Important: Not once random, but it should be randomly generated for each your text or password.

$\endgroup$
  • $\begingroup$ salts predated rainbow tables by a wide margin. They prevent attacking multiple passwords at once. Even before rainbow tables I could mount a dictionary attack against an entire database of unsalted hashes at once. Time memory attacks only became popular after rainbow tables were introduced in 2003(Even though rainbow tables only give a factor of 2 over previous time memory tradeoffs) $\endgroup$ – Meir Maor Jun 26 '18 at 5:38
  • 1
    $\begingroup$ factor of 2? Doesn't it depend on how you construct rainbow table? $\endgroup$ – mentallurg Jun 26 '18 at 5:51
  • $\begingroup$ rainbow tables give a time-memory-data tradeoff curve. It is the same curve as previous multi table time memory tradeoff but with a factor of 2 on runtime. compared to brute force with no pre computed tables these can be many orders of magnitude faster. $\endgroup$ – Meir Maor Jun 26 '18 at 7:34
2
$\begingroup$

From Wikipedia: "In cryptography, a salt is random data ..."

So, just use CSPRNG to generate your salt.

$\endgroup$
1
$\begingroup$

How exactly salt is chosen or generated does not matter a lot, nor does it need to be secret. What matters is that your salt is unique.

In principle, you could start at any one random number, and increment that number for each user. But of course, simply using a pseudorandom number (needs not be cryptographic) for every user is just as easy! If the number is reasonably large (say, at least 64 bits or so), you can assume that every pseudorandom number will be unique (likely enough anyway).

Ideally, when saying unique, that means unique for every record in your user database, not just unique in respect of someone else's system. It is possible to just use one salt for all users, but then you do not get the full benefit. Thus your assumption that you can reuse the salt for all passwords is, well, not outright wrong, but certainly sub-optimal (that usage is more like "pepper", too).

What a salt does is, it makes identical passwords appear different in their hash values. Identical passwords occur often because people re-use passwords on different sites, and many people use easily guessable passwords, such as normal words you'd find in a dictionary (or easy variations thereof).

This is something that can be exploited by precomputing. An attacker thus only needs to do the work once, and basically reduces the effort to crack any number of passwords to virtually zero. Plus, entire databases of hashes (the word for that is "rainbow table") already exist for exactly that purpose, so an attacker can just reuse someone else's work, too.

Having a salt which makes identical passwords different in their hash thwarts this attack. So far so good.

However, unless every user record has its own, individual salt, an attacker can still reuse work done while attacking your user database, and what's worst: You can tell at the first glance when several users have the same password!
If several have the same password, you know whom to attack first. Not only is it highly likely that this is a weak password, but also having found one password means having compromised several accounts.

That's why salt should really be unique for every user record, not just your site.

$\endgroup$
1
$\begingroup$

Selecting salt should be random at the same same time it shouldn't be short. Below image indicates the usage of salt and the randomness salt value in action.

enter image description here

Salt is used to mitigate following attacks types by increasing the complexity of the cypertext with random salting as indicated above:

  • Dictionary attack
  • Brute force attack
  • Rainbow table attack

You shouldn't use/choose salt as per below recomendations:

Salt reuse - This is highly vulnerable to the reverse lookup attack and the plain text/password could be recovered easily. Hence it's always recommended to use random not hard-corded salts.

Short Salting - It is recommended to use complex salt instead of short and simple. If you use simple salt the probability of attacker recover your plain text would be high.

User name as salt - Since most of the user names are predictable or easily recoverable it is not recommended to use usernames as salt

Hope this clarifies your concerns...

You may refer following wiki for more details: https://en.wikipedia.org/wiki/Salt_(cryptography)

$\endgroup$
1
$\begingroup$

TL;DR: Use 16-32 bytes from something like /dev/urandom for your salt. This type of salt best defends against certain types of threats against password hashes. Pairing a unique salt with every password hash is a lot like using a separate hash function for each password.

Threat 1: Precomputed Tables

Password cracking can take advantage of precomputed tables. The straightforward method is to pre-generate a table that maps hashes to passwords. When you have a database of password hashes you want to crack then start with hashes that match entries in the table. New password/password-hash pairs can be added to the list whenever a new password is cracked or leaked. The table can grow ever larger without significant increase in lookup-time. Even if you use a strong password stretching hash function, not using a salt means you only need to hash a candidate password once as long as you have space to store new entries.

Rainbow tables are a different type of pre-computed table that use less space. They take advantage of a time-memory-trade-off. I will omit the details because they aren't relevant and because rainbow tables are easily defeated.

Solution: Use a decently unpredictable salt. If you use an $n$ bit (unpredictable) salt, then you increase the number of required "stored" passwords by a factor of $2^n$. This makes the two types of tables infeasible for sufficiently large $n$. If someone has already generated tables then adding a salt to your hash function makes those tables useless. If they have a table for one specific salt, then it is useless for other salts.

Threat 1½: Tables for preditable salts

If your salt is predictable (or known) then someone preparing to crack your website's passwords could generate tables to attack your specific website or specific users' passwords in advance of your password database getting stolen. Therefore you should make your salt:

  • A username. Tables can be generated for common usernames. Not just "John", "Bob","Lucy", but also things like "Admin".
  • A userid. Web app developers have already thought of using the automatically assigned ID numbers as a salt. Two problems. 1) URLs or network traffic with a user's ID can leak these numbers. 2) When it is an auto-increment field in a database pregenerated tables can be made for low numbers. ie. 0, 1, 2, 3, ... There is also an increased chance those low number user ID will correspond to an account with admin priveleges.
  • Email addresses. This lets someone prepare for a targeted attack in advance.
  • Your website's name or domain name. There are problems beyond predictability with using a constant salt for every password.

Specific solution: Use a 16 byte value from the same RNG you use to generate new keys.

Threat 2: Identifying identical passwords:

Without a salt, it is pretty easy to determine if two accounts have the same password. If $$x = H(p_1), \\ y = H(p_2), \\ x = y$$ then: $$p_1 = p_2$$

When you add a salt those conditions become $$x = H(s_1, p_1) \\ y = H(s_2, p_2) \\ x = y \\ s_1 = s_2$$

You have the same problem if you use one salt for every password entry. This information leak is much more serious than it seems. If someone can identify that two accounts have the same password then they also identify which accounts have weak passwords. Arrange every password hash in one column. List every account who password-hash matches in another column. Sort the table by the number of accounts in the second column.

You can tell without even testing one password that everyone listed in the first row has something like "password1" for their password. And even if you're wrong then pick one account, test each password in a top 1000 most common passwords list. Once you found the password for the one account, you then know the passwords of probably hundreds of specific users.

Solution: Generate a random salt. One 16 bytes long will work and will likely be globally unique. It is far easier to take bytes from Linux's randombytes(bufAddr, 16, 0), Windows' cryptgenrandom, Java's SecureRandom.generateSeed, Python's os.urandom, PHP's random_bytes, (and so on) to ensure uniqueness than to make up some hack involving usernames, email addresses, domain names, hard-coded constants, etc.

Random numbers from an ideal uniform distribution of $n$ bit numbers will be unique with high probability for up to $O(\sqrt{n})$ samples due to the birthday paradox. 64 bits isn't high enough to have any certainty that your value is globally unique. $\sqrt{2^{64}} = 2^{32} \approx 4 \text{ billion}$. That is a lot for one small website, but small for the whole internet.

You should generate a new salt every time someone sets a password. That includes the first time an account gets created and every time the password is changed.

Threat 3: Cracking Every Account's Password at Once

Adding a salt to a password does not make cracking an individual account's password slower, except in terms of the above attacks. It appears to be a common misconception that using a salt is sufficient to make password cracking slow. It's not.

There is, however, another crucial difference between unsalted (or identically salted) password hashes and individually salted hashes. If every account uses the same salt then I can compute a password's hash once then compare it against every account's password hash for matches. (In the amount of time it takes to do one hash and one table lookup.) If any account(s) hashes match then I have recovered the password of each one of them. Furthermore for every account with a hash that doesn't matched I can rule out that candidate password for every one of those accounts' passwords.

If instead every account uses a unique salt then I have to test every account separately to determine which ones use "password123". This does slow untargeted attacks down; I have to do $numberOfAccounts \times numberOfCandidatePasswords$ instead of just $numberOfCandidatePasswords$. However if I am targeting just one account then there is no difference because $numberOfCandidatePasswords = 1$.

Solution: Use a unique salt for every hash.

Threat 4: Side Channel attacks

During the Password Hashing Competition (the one that resulted in Argon2) people were concerned that RAM access patterns could enable side channel attacks via cache timings.

There were algorithms that used password-dependent and password-independent data access patterns. (Argon2d and Argon2i corresponding to dependent and independent respectively.) Both need to use unpredictable salts.

Argon2i needs a salt to prevent a different type of pre-computation. RAM usage heavy hashes (like Argon2, scrypt, and balloon hashing) need to make unpredictable access to RAM. Random RAM lookups are hard to optimize much beyond what commodity hardware already does. If RAM can be accessed less randomly (by reorganizing the layout of memory or by prefetching) then crackers can gain an advantage. If access patterns can be analyzed to skip or postpone certain computations, then attackers can gain an advantage. Making these optimizations requires significant pre-processing time. Argon2 prevents this by making the RAM access patterns dependent on the salt. Therefore Argon2i should use an unpredictable salt.

Argon2d access patterns are salt and password dependent. (It's stronger if timing attacks aren't a concern.) If your salt is unpredictable and secret then this helps mitigate potential timing attacks.

Solution: Use unpredictable salts. Keep them secret as best as you (practically) can.

Conclusion:

Use random salt values at least 16 bytes long. Use the same non-deterministic CSRNG you use for generating new keys in order to make them unpredictable and unique. (No need to use more than 32 bytes = 256 bits.) Use a different salt every time a password is assigned. (On account creation and when passwords get changed.)

You should generate salts this way if you're implementing something new. If you don't need to implement password hashing yourself then you shouldn't. Look for an existing library (one that is secure and bug-free) that does the work for you.

If you are using PHP, for example, you can use password_hash, password_verify, and password_needs_rehash. This generates salts for you, performs password stretching with a optimized native implementation of bcrypt or Argon2i, and does constant time hash comparison for you. I don't know enough about it to know if I can fully endorse it or the default configuration it uses.

Additional information:

You don't "encrypt" or "decrypt" passwords. Despite the sequence of letters "crypt" appearing in "crypt", "brcrypt", "md5crypt", "scrypt", etc. this is the wrong terminology. Encryption is invertible. Passwords should be hashed, meaning the only way to get a password from its hash should be by comparing the hash of a candidate password to the hash you store for the actual password. If salts are used correctly then the fasted way to crack a password should be by brute force starting with the more likely candidate passwords.

Hashing a password does not automatically make it safe. It's a garbage in garbage out scenario. You should use strong passwords to protect your stuff. You should use a stronger password to protect cryptographic secrets than you use for online services. (Random passwords with high entropy are stronger than "clever" solutions. You would be surprised by how many people think of the thing you thought nobody else would think of.)

You can use password stretching if you want to make your password harder to crack by making hashing slower. (And more expensive if someone isn't using a botnet for cracking.) This process is called password stretching. It makes hashing slower for both legitimate password checks and (hopefully) for password crackers.

You should use whatever password stretching hash function you have available that is optimized for your native hardware. Implementing Argon2 in Javascript, PHP, Python, or Bash is a bad idea. It will run slow for you, because it's not optimal, but the point is to slow down other people not yourself. (For the same reason using a call to sleep doesn't help at all.) It's better to use bcrypt if that's what is available than to use a slow implementation of something else.

You should not use scrypt for website password databases. It needs more RAM than you'd assume to be sufficiently expensive. The amount of RAM it uses can only be increased if you increase the amount of time it runs. You should use a password stretching function that uses a lot of RAM if you're using it as a key-derivation function, (Argon2i, scrypt, ballooon hashing) but more importantly you should use a higher entropy password.

The term salt is generally not applicable to things other than hash algorithms. Somewhat related terms are "nonce", "tweak", and "IV". There is also a related term "pepper" which can have several meanings, but usually refers to something like "like a salt, but secret." Peppering isn't a good idea because password stretching hash algorithms are a better option.

Don't combine two password stretching hash functions. It's never more effective than running one hash with double the cost parameters.

$\endgroup$
1
$\begingroup$

The salt is generated randomly and is used to prevent the use of rainbow tables against hashed passwords. The salt needs to be uniquely generated for every password. A salt can be generated just using any crypto library available to generate just a random number of bytes. People say that the salt should be stored alongside the hash, but I prefer the method of storing it on a separate database on a separate server instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.