SCrypt's goal and the role its salt plays

Question

Am I right in stating that SCrypt as an algorithm is useful where many passwords are stored in a database, but not against one specific encryption key derived from one password of one user?

For example, let there be a password, a salt, and parameters for the SCrypt algortithm. Let key = SCrypt(password, salt, params). The salt is supposed to be stored with the hash/key itself. If an attacker has a table containing the password, can't he/she brute-force the password given the salt? That defeats most of the purpose of a KDF, as the only goal achieved is an addition of a few seconds in the brute-force process.

Sure, the addition of a few seconds will increase the time needed if many passwords need to be tried, but if the password is an easy password like "ilovesteak", which will not take many tries to guess, instead of seconds to brute-force, it will take hours. But the time taken is still feasible, especially if the data is extremely confidential.

How can I derive an encryption key from a password which makes it mathematically difficult to brute-force derive?

Answer 1

The goal of using a memory-hard hash function like scrypt with a random salt is, generally, to make brute-forcing much more expensive. This has two side effects:

• First, if the database leaks, it will be expensive to try to crack all the passwords. Because each has a random salt, this is O(M*N) in the number of passwords and guesses. If we had no salt, then guessing would be O(N) in the number of guesses, since we could reuse or precompute guesses.
• Second, it can make a password which might otherwise be marginal provide a little more security by making it harder to crack. This is due to the nature of the memory hardness, which limits the use of GPUs for cracking and therefore makes each attempt more expensive.

You are correct that if you have one single, weak password, then it is easy to attack, even with a properly salted scrypt. That's because the secret, the password, has low entropy: it comes from a small set of inputs. There is no magical cryptographic technique that can create entropy where it doesn't exist: cryptographic techniques are assumed to be publicly known, and the attacker can always try to use brute force to guess. This is why we generate keys with 128 or more bits of entropy: because it makes brute-force computationally infeasible.

Ultimately, that means that you need your inputs to have reasonable entropy. For many API interfaces, that generally means credentials are pseudorandomly generated and provided to the user instead of the user choosing their own. For websites, this means that we encourage the use of password managers and pseudorandomly generated passwords. If you have to read a password from the user, you may encourage a passphrase by forcing a longer password (e.g., 16 characters or more) and rejecting known weak passwords to make the likelihood of choosing a good password better.