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

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?

• In some scenarios common passwords can be tested using Argon2 etc.. taking up time, yes, but will commonly yield correct results if weak passwords are used – SamG101 Dec 20 '19 at 10:45
• "Common passwords" is what I mean by "completely trivial", so Summer2020 is still not acceptable. – Ole Tange Dec 20 '19 at 10:48
• 0.3 s, though, would still take 10 years which is a not-too-bad deterrent against many common attackers, while still remaining fairly responsive. – The_Sympathizer Dec 20 '19 at 21:44
• This is far more security specific than cryptography specific. Could I suggest moving this question over to Information Security? – Ghedipunk Dec 21 '19 at 2:52
• This question is missing an important part, what are the security risks? – kelalaka Dec 21 '19 at 8:54

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.

• @OleTange: Offering a range of security/speed tradeoffs when the account is created (or the password changed) is one solution, but not entirely problem-free either: a user could easily be surprised if they choose a setting that takes half a second on their new laptop and later find out that it takes 10 seconds on their old smartphone (or vice versa!). Or, worse yet, runs out of RAM and takes 20 minutes as the OS has to start swapping RAM to disk and back. Or just crashes because there's no swap space. Or runs for 20 minutes and then crashes because there is swap, but not enough of it. – Ilmari Karonen Dec 20 '19 at 12:45
• @Ghedipunk no. It's true that the stretched password would be password-equivalent (and you should probably hash it again server-side -even just a quick one-, just to ensure that it cannot be stolen from a SQLi), but replaying that is not an issue. It would be equivalent to the attacker having the right password the first time. The attacker could try stretched hashes without being limited by the stretching time, but the point is that bruteforcing the hashes would be completely impractical, as it would have a so larger search space. – Ángel Dec 21 '19 at 0:54
• @IlmariKaronen: even funnier. The site might be working if you logged in just after rebooting, but fail (crash the browser / render process) if the user attempted to login later, when there were other applications open (office tools, email client...) or simply many pages. – Ángel Dec 21 '19 at 0:56

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.

• But in advice given to the public I do not see we give the public the choice: You can have simpler passwords (though not so simple it is in a dictionary) if you are willing to wait. Instead I see the security industry only promote: You have to make better passwords. – Ole Tange Dec 20 '19 at 12:19
• @OleTange Sometimes the security industry moves slowly. Consider that NIST recently declared that expiring passwords every X days is less secure than not expiring them, despite everybody knowing what people do to work around the password expiration, generating weaker passwords in the process. Also, you may only be seeing the slow bulk of corporations, not the fast parts. It's been known that password rules have serious issues for some time – Cort Ammon Dec 21 '19 at 13:34

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.

• SHA2 does not require 1 GB RAM to test a single combination, so it seems to me that is highly irrelevant. Can you elaborate on why you bring SHA2 into the mix? – Ole Tange Dec 20 '19 at 12:47
• Given that the hash algorithm in the setup is RAM hard (1 GB RAM/core) I still do not see how it makes sense to compare it to an algorithm that is CPU hard (SHA2). Please update where you take 1 GB RAM/core into the mix. scrypt/argon with 1 GB RAM requirement is by no means comparable to a simple SHA2, so arguments that apply to SHA2 does not necessarily apply to scrypt/argon with 1 GB requirement. – Ole Tange Dec 20 '19 at 15:38
• That can be used for comparison, for example, take hashcat 7493.4 MH/s (89.28ms) for SHA-256 and 1172.8 kH/s for scrypt. I could not see an argon2 implementation – kelalaka Dec 20 '19 at 16:57
• SHA-256 cannot be tuned to require 1GB RAM and is thus also irrelevant, because it is not RAM hard. Is the referenced scrypt with 1 GB RAM as parameter? If it is not, please justify why you find that relevant for the discussion. It matter if scrypt is called with 1Kbyte or 1 Gbyte as parameter, because a GPU with 256 cores that each have 2 MB RAM is useful if we are talking 1 Kbyte, but useless if we are talking 1 GByte. – Ole Tange Dec 20 '19 at 17:25
• Yes, SHA's are not RAM hard, and I don't claim it either. There are no Argon2 in hashcat yet, there is an OpenCL implementation, though. I couldn't one result that uses 1GB scrypt, currently is uses 16K around that is tiny. We can still relate the numbers if attacker is dedicated, this is your case since you are considering 1GB usage. A dedicated attacker can build specialized hardware. – kelalaka Dec 20 '19 at 21:13

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.