Why Enforced Password Complexity Is Worse for Security (and What to Do About It)
Sorry, your password doesn’t meet our complexity requirements. Please choose a password that’s at least 73 characters long, contains 17 unreadable ASCII characters, 22 non-repeating numbers, and three synonyms for the word “obscure.”
Sound familiar? This is the world we now live in, password complexity, yet we’re not quite sure what it is or why we need it.
Everybody hates password complexity, and it seems to be taken as “truth” without any real considerations to its actual impact on security. In fact, even NIST has recently started suggesting that the added complexity of passwords be scaled back, as it is weakening overall security (Grassi, 2021).
A password is fundamentally used to prove identity and provide authentication. Given that, it should be clear why we want to keep the password secret and make it hard for an attacker to guess or steal. Passwords have to tread a delicate line between convenient and easy to use while also providing enough security to keep your kids from cashing out your savings account or arguably worse, prevent someone from replacing your companies prized source code or signed release packages.
In the infancy of computing, passwords relied heavily on trust. These early passwords were relatively short and simple. As the trust eroded and the threat model changed, we started to enforce restrictions around passwords such as minimum length and using encrypted passwords for system access. As computing continued to evolve, it became even easier to guess or manipulate passwords thereby driving more artificial complexity and, ultimately, user hate and non-compliance.
Let’s take a step back, evaluate some password threats, review their protections, and challenge evolving complexity requirements.
Brute forcing passwords
It’s no surprise that early passwords were short and easy to guess. Many early passwords were all lower case and seven characters or less. These passwords were classics like “love”, “god”, and “secret”, and they began the book of never-to-use-passwords. Not surprisingly many of these passwords continue to be used in various forms today.
At seven characters max, that leaves us with 26ˆ7 possible passwords. We are of course assuming here that nobody wants to use the shift key, let alone CAPS LOCK or the number pad….So all lowercase passwords it is for this discussion. Of course, we can probably simplify this by assuming most passwords come from the English language as it’s much easier to remember a word vs. something like ‘oowouqu’. ‘oowouqu’ is kinda fun to try and say out loud though, so maybe we’ll use it as our password after all. But even if we don’t make assumptions and simplify the math, it would take a very slow computer around 254 years, assuming one password guess per second, to guess the correct password. As computing evolved, already nefarious individuals with too much time on their hands figured out how to parallelize that operation enabling it to be accomplished significantly faster.
In order to combat brute force attempts, you have a couple of potential countermeasures:
Rate-limit requests (example – one password attempt every five seconds, making our base here take almost 1,000 years)
Lockout an account after a given number of attempts (not the most user friendly but provides an opportunity to fail secure, at least if you’ve given any forethought to how the organization handles password resets and unlocking - as is usually the case though, this just opens the side door to abuse, increases the burden on the help desk, and probably enables social engineering).
Enforce multi-factor authentication (MFA) so an attacker has to have both your password and something you have (where have could be physical or ephemeral).
Though increasing the minimum password length, in theory, would increase the possible password combinations, in practice, it actually makes brute-forcing easier, since we are now artificially establishing a floor to begin our password guesses. Take a twelve-character password minimum, for example. In theory, this would bring the possible password combinations to 26ˆ12. However, there is a huge gotcha in that thinking because, in practice, most users create passwords that meet the minimum – twelve characters exactly. Therefore, to brute force this, we only have to look at passwords that are exactly twelve characters long vs. passwords that are more or less than twelve characters, which is a much smaller search space and effectively decreases the overall strength.
Similar things happen by mandating additional character classes, numbers, and symbols. As an example, if we include all common character classes (both lower- and upper-case letters, numbers 0-9, and the standard ASCI keyboard symbols) we have 96 possibilities for each position. So, for a twelve-character password, we end up with 96ˆ12 password combinations. However, in the real world, we can often simplify this based on English dictionary wordlists, password trends, and other requirements.
Congratulations, we’ve now forced everyone to use Ahh00000gah! As a password! It’s memorable, 12 characters, and includes all of the character classes we require.
Let’s look at the password requirements from one unnamed secure messaging portal:
8-15 Characters
At least one capital letter
At least one lower case letter
At least one number
At least one special character from a reduced set of 30 characters
In an ideal world, this should give us 92ˆ15 possibilities. But that’s not the whole story. Because the password must be at least 8 characters, the search space is effectively reduced to 92ˆ15 - 92ˆ8 possibilities, a significant reduction. You’ll also notice that, for whatever reason, they reduced the allowed symbols or special characters by four (we can maybe speculate they didn’t know how to escape those characters to prevent something like SQL injection). Even that reduced set doesn’t tell the whole story though, as four of those seven positions must be from specific character classes leaving only three positions for the full possible character set. So, while the math isn’t exact and is greatly simplified for clarity, we now have a total set of passwords that is closer to 2.3*10^29, a reduction of ~5*10^28 from our starting set of 92^15 or 2.89*10^29. If you’re really curious about the math, grab a beer and work your way through [2].
It looks like everyone can keep using Ahh00000gah! As a password though. Please don’t though, that password is not secure at all, and well now everybody knows it.
With some simplifications, we now added security in the form of complexity and intended to increase password strength to 92ˆ15 and ended up with a lower effective length ~2.31*10^29; experimentally, we’ve seen a reduction of about 20% in possible password combinations with these rules. 2.31 * 10^29 is still a really huge number, but it’s a smaller set of passwords then we were trying achieve. If we assume our same one guess per second as above, we’re still in the realm of a “lifetime”. By forcing arbitrary constraints on passwords, we added complexity, annoyed the users, and resulted in passwords that are even less secure than we had before!
Being that we as an industry have pushed the concepts of not writing passwords down, having memorable passwords, etc. we can make some additional assumptions about how users will create passwords. Namely, we can assume most passwords will be based in parts of the English language, and have recognizable patterns further decreasing that 9 days.
We can expect users to create passwords like Moneyˆ(1/2)evil (Exactly 15 characters, uses all of the character classes, easy to remember, etc.). By assuming passwords like this we can essentially use permutations of word lists, with some punctuation, and “leet” speak replacements to further reduce our search space. Similarly, if we force passwords to be changed every 60 days, we can expect most passwords to then take on some form of a pattern like:
Bank_balance000 => Bank_balance001 => Bank_balance002
Which again only serves to simplify the search space and reduce the total permutations of passwords that need to be checked.
Don’t take this to mean that you should never rotate or change passwords, there are still many great reasons why you would want to change or rotate passwords.
Some fun side effects begin to emerge if we try to prevent users from using patterns or reusing portions of a password.
Case #1 - Each password change must not use more than X% of a previous password. This indirectly forces you to store the previous N passwords (most likely in the clear, so you can check reuse percentages of a password).
Case #2 - Trying to limit patterns during password setting, which (no surprise) just further reduces our password search space and possible patterns.
The ultimate solution here is to change our password mindset and force users to use a password manager, while simultaneously removing most password restrictions. Yes, removing password complexity enforcement; if everyone is using a password manager, then suddenly the notion of complexity diminishes. Most modern browsers and ecosystems (Apple, Google, etc.) have a password manager built-in, and additionally, there are a wide variety of 3rd party password managers with various benefits (all opening their own can of security worms, but that’s a story for another blog).
Through the use of a password manager, as a user I am now free to use passwords like:
VS0h;|O]$W"H@+yH
SCRAP?CRAFTILY?STYLIST?hubcap
In the first case, we used `pwgen -y -s 16 1` to generate a random password. This doesn’t limit the character classes, it does however make it a challenge to manually copy and paste or enter using a TV remote (strangely enough, it’s not uncommon to find systems that won’t let you use a password manager or a variety of devices that give you a horrific interface for entering passwords), making this undesirable. Using pwgen in this fashion makes the most secure passwords and doesn’t limit the scope of character classes, but it presents some slight user interface challenges.
The second example was generated using `xkcdpass -n 4 -d ? -C random` and presents a slightly more user-friendly password, that slightly reduces the available complexity by limiting it to English words with random capitalization and a chosen delimiter. The above real-world example effectively eliminates both of these possibilities due to the arbitrary restrictions and instead suffers from a very weak enforcement of passwords. Either way, with a password manager in most cases the password can be copied and pasted, and as a user, I don’t have to remember it. At the same time, they are secure (or at least more secure than the arbitrary restrictions above).
It should also be noted that the arbitrarily low, max length above (i.e. 15 characters) in the real-world example, effectively prevents the use of most password generators, especially those of the xkcdpass form, as even something like our example above “SCRAP?CRAFTILY?STYLIST?hubcap”, far exceeds 15 characters.
Password Reuse
As computing became more ubiquitous, it became common for users to use the same password on multiple systems because remembering lots of passwords is hard. Once this was realized, nefarious users began targeting the system’s password file. Why try to generate all of the possible passwords, when you can just see what they are using on another system and try it? This then led to various forms of encryption and, eventually, one-way hashing of passwords. Unfortunately, the introduction of encrypted password files leads us back to brute force.
Attackers started to pre-compute (i.e., encrypt) the brute-force guesses, and keep tables of password guesses vs. encrypted variants. This effectively enabled them to steal the encrypted password files and very quickly determine a set of known user accounts/passwords, thereby enabling a whole slew of additional attacks.
Eventually, encrypted passwords gave way to one-way hash functions being used, but it still doesn’t prevent you from precomputing (or even brute forcing) passwords, it just requires significantly more computing resources. Moore’s Law, the introduction of cloud computing, and things like GPU offload essentially helped to reduce the time required to compute one-way hashes of “common” (or even guesses) for passwords and check the hashes against the stolen password files.
The solution here is to use salt. The salt is stored alongside the hashed password and is either pre- or post-pended to the user’s password before applying the one-way hash function. So, the user’s password either becomes SALT+PASSWORD or PASSWORD+SALT. The result is then fed into the one-way hash function. The salt is non-sensitive but acts to significantly increase the complexity (storage and processing) of pre-computing passwords to perform quick comparisons for reused passwords.
The salt we’re talking about here isn’t NaCl (Table Salt), but it is almost like a password in its own right. You can’t lick it though, or at least not easily.
When combined with other approaches such as rate-limiting password attempts, locking accounts, and Multi-Factor authentication mechanisms, salts significantly raise the bar and improve the security of password-based systems. However, even with the use of salts and one-way hash mechanisms, users should still use a password manager.
The use of a password manager encourages unique (or at least practically unique) passwords and enables user-friendly, arbitrary length and complexities to be used.
Wrapping it all up
As a security professional with a strong reliance on a password manager (a quick check shows I have in excess of 1200 passwords stored, all unique or practically unique) there is nothing I find more frustrating than having to tweak my auto-generated passwords to meet arbitrary password policies which only serve to reduce the effective strength of my passwords. While well-intentioned, the use of arbitrary password policies is a poor practice, and as we’ve shown, significantly decreases the search space required for guessing passwords. Through the use of a password manager, we can however remove some of the “user element” and end up with even stronger passwords in many scenarios.
So, what do we do?
Encourage the use of a password manager – Both organizationally and individually; It’s probably a topic for another blog post, but you probably don’t want to force a specific password manager to be used.
Stop enforcing arbitrary password policies – If everyone is using a password manager, then the arbitrary restrictions only help to reduce the password space.
Permit reasonably long passwords (it’s not unreasonable to accept up to say 256-character passwords, extra credit for enabling this to be multi-byte Unicode characters so users can have passwords like I-Wonder-if-the-ƒ(coåt)-KeepsME@warm≤32ºF). If you’re using a one-way hash function to store the password (and seriously, why wouldn’t you use a salted one-way hash function), there is no storage penalty for the added characters of a hash (one of the characteristics of a hash is that the resulting hash is always the same size regardless of the input to it)
Enable Multi-factor authentication everywhere (and all the time) – yes, this means organizations and systems need to support it, and because most users are rather lazy, it also means that it should be enabled by default (i.e., you want the user to turn it off if they really don’t want it). As a bonus, recovery codes and such can also be stored in a password manager if needed.
Utilize additional mitigations as the threat space requires (rate-limit password entries, locking out accounts after failed logins, etc.)
Uniformly apply security engineering principles and don’t try to just “bolt-on” knee jerk solutions
References
Grassi, P. et al. (March 4th, 2021). NIST Publication 800-63B: Digital Identity Guidelines – Authentication and Lifecycle Management. NIST. https://pages.nist.gov/800-63-3/sp800-63b.html