Why are good passwords required if we use good hashing algorithms?

Question

Again and again are we adviced to make good passwords: At least 12 chars, numbers, signs, upper and lowercase.

But why is that really needed?

I can see the need, if the system uses a hashing algorithm that can be implemented in ASIC, where an attacker can test trillions of combinations per second.

But using scrypt, Argon2 and similar technologies we ought to be able to make it so expensive for an attacker that testing just billions of passwords will be infeasible. Both can be tuned to require a massive amount of RAM, and in that configuration they are not at all comparable to MD5, SHA-1, or SHA-2. E.g. if we make the hashing take 3 seconds and use 1 GB RAM it will take 100 CPU-years and 100 GB*years to test just 1 billion combinations.

Would it not be relatively easy to trade compute+RAM ressources for allowing simpler (though not completely trivial) passwords?

Answer 1

First of all, password strength rules like "at least 12 chars, numbers, signs, upper and lowercase" are actually counterproductive — they result in passwords that are only slightly harder to guess but significantly harder to remember, and worse, they also often end up also disallowing passphrases generated by actually secure methods like Diceware.

Their one arguable merit is that they disallow very common weak passwords like "password", "abc123" or "letmein". Alas, preventing a user from choosing these weak but easy-to-remember passwords will typically just result in them choosing the simplest password that the system will accept, like "Password123!", which is still trivially guessable by any half decent password cracking tool (but now the user is much more likely to forget which punctuation symbol they used and whether they put it before or after the number).

(Another arguable historical rationale for such rules is that using a diverse selection of characters allows squeezing a little bit of extra entropy out of a short password, which could be relevant on systems that severely limit password length, like the old Unix DES-crypt scheme from the 1970s that truncated passwords to at most 8 characters. But such archaic password hashing schemes are fundamentally unsafe anyway, and mixing a few punctuation characters into your password will not make them safe. Still, this is likely one reason why such rules were originally introduced and popularized in the first place.)

---

Anyway, as far as it goes, your math it looks more or less reasonable to me: 3 billion seconds is about 95 years, so if testing a single password takes 3 seconds on a fast CPU, a password with about 30 bits of entropy (i.e. chosen uniformly at random from among $2^{30} \approx$ 1 billion possibilities) will take 95 CPU-years, which most attackers may consider too much effort. That said, however:

• Password cracking is an embarrassingly parallel task, so an attacker willing to dedicate 95 CPU cores to it will shorten the time to just one year. With 5000 cores (which could be easily within reach of e.g. even a fairly small botnet or a server farm) it comes down to one week.

  Also remember that processors still continue to get faster (and/or more parallel) and RAM prices still keep going down. Not only does this mean that the time cost of cracking any specific password hash goes down over time, but you also cannot assume that all your users have the latest and greatest CPUs, whereas any decently motivated attacker probably does have access to those, or at least to something reasonably close. Some of your users might be (at least occasionally) using 10 or 20 year old devices with slow CPUs and limited memory, and they'll want to be able to log in using them; an attacker with a botnet will have plenty of newer devices at their disposal.

• Three seconds is already a rather awkwardly long time to wait for your password to be accepted. For infrequent use it can be fine, but do you really want to wait that long every time you log in to a website or return to your workstation from a bathroom break? I've seen one second listed as the maximum delay that most users are likely to find acceptable, and that's probably pushing it a bit. Personally, I wouldn't aim much higher than 0.3 to 0.5 seconds.

  If you'd like to try a quick experiment, count how many times you have to enter a password (even a prefilled one) or a PIN code per day. Then try counting slowly ("1 mississippi, 2 mississippi, 3 mississippi") to three before pressing enter each time. See how long it takes before you get tired of those pauses.

• In any case, for authenticating to a remote server such as a website, even 0.3 seconds of key stretching per login is really only feasible if you can do the work on the client. If you try to do the kind of slow and memory-intensive hashing you suggest on the server side, anyone can bring your server to its knees with a trivial denial-of-service attack just by having a bot try to log in with random usernames and passwords a couple of times a second. Heck, you could probably do that even without a bot just by repeatedly clicking the login button.

  With the Web Crypto API and/or WebAssembly implemented in modern browsers, it would be possible for a website to do key stretching on the client side. I haven't seen any standards or widely used implementations for this, though, and while doable in principle, it has some nontrivial security and usability pitfalls that any custom implementation would need to be careful to avoid. Also, it basically makes logging in impossible for users who cannot or will not run JavaScript, as any alternative fallback mechanism could also be abused by attackers. So, at least for a while now, we're still mostly stuck with server-side password hashing.

Answer 2

First of all, it's of course a good idea to use something like Argon or a similar implementation for password management. But there are some issues you would have to consider with your proposition:

1. Complexity: The main reason for implementing password policies is to prevent a user to choose too simple passwords. If you leave out password policies you can be sure that a very large percentage of users will use simple passwords. That's where an attacker can use other attacks than simple brute-force, for example dictionary attacks. Without the use of at least some reasonable password policies you would find quite a few passwords by trying out the most frequently used passwords. The use of a resouce-intensive algorithm wouldn't prevent it from happening in a manageable time-space for an attacker.

2. Performance: Depending on your resources it's maybe not a very good idea to have the server perform such intensive calculations. It's acceptable to set the number of iterations reasonably high without impacting the server's other functions. But you could prevent the issue of performance with client-side hashing.

In general you have to find a reasonable compromise for this issue: Users want simplicity and want a login to happen fast. People responsible for the security of a system would want users to use very complex and secure passwords and would want the login to take some time.

Answer 3

But why is that really needed?

• Shortly;

  The old but still valid brute-force all passwords still apply if you don't follow the guidelines and enable them to use shorter lengths.

• A bit longer;

  The memory expansion prevents the parallel running in ASICs or FPGAs. The iteration count increases the timing both for the attacker and the system/user. From the user's perspective, you cannot set it so high since the users will start to complain about it. 1 sec may be good enough and that can be around 1M iteration. Therefore, you can not use a very high iteration number that effects the attacker speed linearly, too.

  Once you get the timing of your system (scrypt, Argon2id, etc), calculate the possible attackers' power, and consider your risks so that you can set the minimum strength of your password policy. You can use various sites or the table on Wikipedia's page, (alpha-numeric with 11 char has 64-bit entry and 14 has 80 bits).

  If you choose password strength lower than the necessary, you let the attackers try all possible passwords by brute force on the possible password space (they will look at 6 alphanumerics, then 7, then.., if you let 6 as the minimum). Of course, the attacker may not be able to find the stronger passwords, they can still find passwords where the users use the minimum requirements because you let them choose smaller that under threat.

Would it not be relatively easy to trade compute+RAM resources for allowing simpler (though not completely trivial) passwords?

If you let your user choose simple passwords, it will be the first target of attackers instead of searching all space. They will use the publicly known information about the common passwords if they don't have a DB from their previous attacks.

For example, if you use 6 alphanumerics, you will have 32 entropy, for 7 40 bits entropy. This is very low. Consider that bitcoin miner reached $2^{60}$ SHA2 double hashed per second. Making an analogy about possible attackers' power, you should consider an adversary having power around this while determining the minimum requirements.

Keep in mind that, while considering the strength of the passwords you should not consider today's technology.

Use the guidelines to be safe, at least for a while.

Answer 4

Because the slowing down by better hashing requires the same factor increase of the resources on the productive server. That means, to slow the attacker down by factor 10 you need 10 times as much resources for your server (simplified by excluding the other tasks he does), for slowing down by factor 50 you need 50 times as much resources.

In contrast by simply adding one character to latinmixedcasealphanumeric password you slow him down by factor 62, for 2 characters by factor 3844. When you change a 12 character password from latinalphapethical to latinmixedcasealphanumeric plus 10 possible special characters you get a factor of 203 380.

But this also is in contrast to usability like you noticed. So it is also about to find a sweet spot where you don't annoy the user too much but the attacker enough.

Next point:

if we make the hashing take 3 seconds and use 1 GB RAM it will take 100 CPU-years and 100 GB*years to test just 1 billion combinations.

This is nothing when the attacker is just renting cloud computing for cheap and this requires a randomly chosen at least 6 character long latinalphapethical password. This is defeated by common password lists. Leaked password lists showed that it is enough to test for the most common 10.000 passwords to crack more then 99% of the passwords if there are no password rules in place. So that is less than 9 CPU-hours. Rent 9 cloud-CPUs per password and you have more than 99% of all passwords cracked in 1 hour.