0
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ For question #1, single-iteration hash databases are distressingly common, and were the default in most programming frameworks until the last 2-3 years. Unsalted SHA-1 or even MD5 seems to be extremely common even among $bigvendor offerings in 2018. I’m looking at you Cisco. $\endgroup$ – rmalayter Jul 15 '18 at 21:59
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you are being very conservative. With a proper KDF much weaker passwords are still safe. $\endgroup$ – Meir Maor Jul 15 '18 at 19:06
  • $\begingroup$ Do you think that's a minimum (as in the title of the question)? That would be unlikely to be remembered. At lease assuming (as we do) that users need to remember multiple passwords. $\endgroup$ – ispiro Jul 15 '18 at 19:13
  • $\begingroup$ @MeirMaor I am not assuming anything about the password hash that the server uses other than that there is something, even if it's just MD5. If you want to assume the additional premise that the password hash costs at least $C$ bit operations to evaluate, then you can knock $\log_2 C$ bits off the size you choose. But positing high-quality engineering in the server is beyond the scope of the question as written. $\endgroup$ – Squeamish Ossifrage Jul 15 '18 at 21:25
  • $\begingroup$ @ispiro You may find it easier to make up mnemonics for ten-word phrases than you think, and there are various choices of word lists according to taste. You can also use a password manager, if you're looking for advice for users. $\endgroup$ – Squeamish Ossifrage Jul 15 '18 at 21:33
  • $\begingroup$ @ispiro My advice is the smallest number I'm willing to guarantee attains security in this setting no matter what the adversary's budget, from your personal stalker to a joint project of the NSA and Google. (Obviously the real world has more attack surfaces; I'm not addressing other aspects of security than guessing the password.) Is it the minimum that won't be economical for the attacker? Maybe eight words is enough to make it uneconomical for that adversary, but I won't stand behind any guarantees about that. $\endgroup$ – Squeamish Ossifrage Jul 15 '18 at 21:34
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Randomly chosen phrases may be much more memorable, and less prone to errors in (for example) handwritten transcriptions, than randomly chosen US-ASCII characters. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 23:13
  • 1
    $\begingroup$ @SqueamishOssifrage: And are a pain to type, IMHO, particularly into mobile devices. In any case it's a matter that is likely subject to some mix of empirical argument and personal preference, and which I don't think we can settle here. $\endgroup$ – Luis Casillas Jul 16 '18 at 23:17
  • $\begingroup$ That's a good point. Brute forcing is only one way to get to whatever data is there. $\endgroup$ – ispiro Jul 19 '18 at 11:12
0
$\begingroup$

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 222.

In 10 years attackers will improve so let's make that 226. Let's cap our attacker at 1 million dollars. So we get 246 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.

$\endgroup$
  • $\begingroup$ Suppose a thousand users all pick their passwords as you recommend. If an adversary with a 1000000 USD budget could succeed at a single-target attack, then an adversary with a mere 1000 USD budget could succeed at a multi-target attack on all thousand users. The attacker with 1000 USD to spare may not get to choose which user's password they find, but often compromising one user in a network is enough to get a foothold into the network. And a 1000000 USD budget is quite small: there are many individuals who could afford that on a whim. This advice is not safe. $\endgroup$ – Squeamish Ossifrage Jul 15 '18 at 21:48
  • $\begingroup$ Thanks, but as I hinted in the question, I'm asking about passwords that don't require a password manager. And as made even clearer, I'm not asking how to hash passwords, but what length should they be in the current situation of how passwords are hashed "in the wild". $\endgroup$ – ispiro Jul 15 '18 at 22:14
  • $\begingroup$ If passwords are properly salted you can't attack 1000 users at once. I think most reasonable web sites use a KDF with salt. maybe not a memory hard one but at least something like bcrypt(also the default in many Linux setups). For an attacker using CPUs may analysis will hold also for bcrypt. For dedicated hardware an serious attacker could utililize lack of memory hardness. $\endgroup$ – Meir Maor Jul 16 '18 at 3:14
  • $\begingroup$ edited at top and botton to better answer question asked. $\endgroup$ – Meir Maor Jul 16 '18 at 4:23
  • $\begingroup$ @MeirMaor As I understand it, the original poster sought advice for users, not for the engineers who are building password databases. The premise is that the passwords are hashed, but not necessarily salted and not necessarily with expensive password hashes—perhaps just with MD5. Password security is not the whole story, but it is a part of the story, and rejecting the whole story because some other part might be broken is counterproductive security nihilism. Do you have overwhelming evidence that unsalted hashes are no more, or is that a convenient premise to make a nicer answer? $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 5:03

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.