Recommended minimum entropy for online passwords in 2018

Question

Assume a simple case, that an attacker knows the password creation scheme, and that we're not dealing with state actors, nor with sites which keep passwords in plain text. We're trying to defend against offline brute force attacks on a compromised database of password hashes. And we want the vast majority of our passwords to resist an attack over ten years.

From anecdotal evidence it seems like even sites that should know better keep passwords hashed only once. (And others in plaintext, but there's nothing to do about those.)

So it seems like the answer will depend on the following:

1. Are single-iteration-hash databases really common? If not, what method is the least secure and most common? (Including iteration counts, hash types, etc.)
2. And how long does it take to crack these methods. (Including common hash cracking hardware, do these databases become public and are then cracked by the best hardware out there (think ASICs),...)
3. How much time do attackers spend on a password before giving up on it (Assuming unique salts)?
4. More parameters?

Just saying that we'll never have enough information for an informed decision is not enough. We need some idea. We all use passwords, and not everyone uses password managers. (I'm not saying it's not a good idea. It's just a fact.)

_{(I initially asked this on security.stackexchange, thinking that that would be more appropriate, but got no answer there. In fact, at first I got comments questioning the basics of password storage etc. (Which were later edited out by the mods.) So I'm asking this here instead, hoping that the crowd here will have already asked itself that question.)}

Answer 1

If the password is salted, pick a password uniformly at random from ${\geq}2^{128}$ possibilities.

• Example: A sequence of ten words from a 7776-word diceware list.
• Example: A sequence of twenty graphic US-ASCII characters.

If the password is unsalted, pick a password uniformly at random from ${\geq}2^{256}$ possibilities.

• Example: A sequence of twenty words from a 7776-word diceware list.
• Example: A sequence of forty graphic US-ASCII characters.

If you do this, the cost of evaluating a password hash—be it MD5, PBKDF2-HMAC-SHA256, scrypt, or argon2id—is immaterial: an adversary must perform an expected ${>}2^{127}$ bit operations to try enough guesses to find your needle among the haystack of possibilities. Nobody can afford that, and it's not likely all of humanity could in the foreseeable future afford that.

Details. Suppose every one of $t$ users draws their passwords uniformly at random from $n$ possibilities.

If the passwords are salted, the expected cost of an attack to find at least one of the $t$ passwords is $O(n)$ trial evaluations of the password hash. If the passwords are unsalted, the expected cost of an attack to find at least one of the $t$ passwords is $O(n/t)$ trial evaluations of the password hash.

The expected time may be faster if the attacker spends money to power $p$ computers in parallel: if salted, $O(n/p)$; if unsalted, $O(n/(pt))$. But powering sixty computers for a minute is not cheaper—whether accounted in joules, rubles, or bitcoins—than powering one computer for an hour.

There are always fewer than $2^{128}$ users, so as long as $n \geq 2^{128}$, the advice above guarantees that the adversary's expected cost is always at least $2^{127}$ evaluations of the password hash.

Using a password hash like argon2id raises the cost of evaluating the password hash versus a hash function like SHA-256 not designed for hashing passwords. It is important for engineers designing systems that handle passwords to take responsibility for raising the attacker's costs using the resources available to legitimate users, and to use a password hash. But from the user's perspective, the advice above makes it immaterial what password hash the engineer choose, whether argon2id or MD5—the cost of an attack is insurmountable for humanity.

Answer 2

I think you're missing one major factor in your list:

• Is the password being used to derive an encryption key that's never in the possession of another party, or is is only used to authenticate the user to a site that has access to the user's data?

Most online passwords are only used to authenticate the user; and the fact that you're talking about stolen password hash databases confirms that you're thinking of this case. This is important because it means that even if your password is sufficiently strong to withstand an offline attack, your data is still vulnerable to other attacks on the website operator and possibly third parties. Having an uncrackable password is of little consolation when the attacker steals your credit card number along with a million other people's.

Personally, I think that 12-character printable ASCII passwords, chosen uniformly at random with a password manager and unique for each site, are not unbearably inconvenient and more than strong enough at about 79 bits. I understand this is in the ballpark of what the whole Bitcoin network might be able to feasibly compute if they all cooperated to crack your password, but I'm just much more worried about scenarios like the Equifax hack.

For a password that's used to generate an encryption key, however, you could justify going all the way up to the neighborhood of 128 bits (e.g., 19 random printable ASCII characters).

Answer 3

Single iteration hash are used but not common IMHO probably less common then plain text. A reasonable salted KDF is common. Though memory hard KDF are not yet the standard.

We can normally afford to have a KDF which will take us at least 100ms and some non trivial amount of memory to compute.

Let's do some back of the napkin throwing numbers around. With better hardware our attacker will be 10 times more efficient than us. Let's say our hardware costs us 10 cents an hour. So our attacker could for 1$ check 3.6M or 2²².

In 10 years attackers will improve so let's make that 2²⁶. Let's cap our attacker at 1 million dollars. So we get 2⁴⁶ minimum password entropy.

We can play with these numbers, I'm most unsure about the efficiency factor we should allow attackers vs memory hard functions (For simple hash functions they are far far more efficient then the honest CPU user). But regardless the methodology I outlined is sound.

You can easily select a memorable password with enough entropy (To protect your password managers holding higher entropy passwords I hope).

With non memory hard functions like bcrypt an attacker with specialized hardware will be more efficient, so probably add an extra factor of 10-100. I believe bcrypt with load factor of 10 is something reasonable to assume. Any service using something significantly weaker probably isn't very security minded and is likely to have more serious issues than password hashing. Good password hashing is easy to implement while good security is hard.