Stop wasting time making the wrong passwords stronger


Most of the effort spent on making passwords stronger is wasted, according to a trio of researchers from Microsoft in the USA and Carleton University in Ottawa, Canada.

The researchers, Dinei Florêncio, Cormac Herley and Paul C. van Oorschot, said in a recent paper that there are two vast “don’t care” regions where energy spent on strengthening passwords is simply wasted.

The chasm

The first “don’t care” region is an online-offline chasm. The chasm represents the gap between the number of guesses a password might have to withstand in an online attack and how many it might face in an offline attack (you can read more about it in my article Do we really need strong passwords?).

To withstand a determined online attack using a website’s login screen your password might have to withstand 1 million guesses. To survive an offline attack by an attacker with specialist hardware, direct access to the password database and plenty of time the figure is eight orders of magnitude greater: 100 trillion guesses.

If passwords sit between these two thresholds then they’re more than good enough to withstand an online attack, but not good enough to handle an offline attack.

Any effort to strengthen passwords in the chasm that falls short of pushing them out of it is therefore wasted.

The saturation threshold

The second “don’t care” region is the threshold at which an attacker stops trying to crack passwords because they’ve already thoroughly compromised the system they’re attacking.

…for an enterprise network a compromised account almost certainly has snowballing effects … The first credential gives initial access to the network, the second, third and fourth solidify the beachhead, but the benefit brought by each additional credential decreases steadily.

So an attacker doesn’t need to crack all of a system’s passwords: in fact they can probably leave most of them untouched.

The point of saturation varies from one network or system to another but the researchers set themselves an upper bound for the saturation point at just 10% of passwords, with the caveat that “saturation likely occurs at much lower values”.

Efforts to strengthen the passwords above the saturation point yield little if any additional security.

Focusing where it matters

On any given system a huge number of passwords are likely to sit in one of the two “don’t care” regions.

If you’re an end user you’ll never know how your passwords are stored or which side of the saturation point they sit, so you should shoot for the strongest passwords you can muster.

If you’re a system administrator charged with keeping your network safe and you don’t have infinite time and resources, the “don’t care” regions can help shape your approach to passwords.

…many policy and education mechanisms are unfocused, in the sense that they cannot be targeted at the specific part of the cumulative distribution where they make most difference (and away from the “don’t care” region where they make none).

How then should you make sure that your efforts to strengthen users’ passwords actually make a difference?

Don’t waste time on composition policies

Perhaps the least popular approach is password composition policies.

These are sets of rules such as “your password should be at least eight characters long and contain at least one uppercase letter, one number and one special character”. They’re popular because the rules are easy to check and they increase the entropy of your password (which can be important but isn’t the same thing as password strength).

However, the case against these rules is compelling: they’re annoying (to everyone, even people choosing really strong passwords); they measure something that isn’t password strength and they restricting the pool of possible passwords (the “password space”), which is a helping hand to password crackers.

Microsoft Research has come up with another reason to ditch those policies, which is that even if they do help to make passwords stronger, they fall into the “don’t care” region where it makes no difference:

…the evidence strongly suggests that none of the password composition policies in common use or seriously proposed can help … enterprises that impose stringent password composition policies on their users suffer the same fate as those that do not

Do block common passwords

Instead of using password composition policies organisations should simply stop users from choosing anything that might appear on SplashData’s annual worst password lists.

Attackers know what the most popular passwords are and any attacker worth their salt will be sure to try them first.

Password blocklists work just where you want them to: below the saturation point for online guessing. Sure, blocklists can be annoying, but they only annoy people choosing poor passwords.

Microsoft and Twitter are both mentioned as sites that use blocklists of hundreds of passwords, but the authors suggest going much further and blocking not just the worst few hundred, but the worst million passwords.

They also suggest that you might use zxcvbn on your website, a password strength meter that actually tries to measure password strength.

Throttle passwords

Limiting the number of times a user can try a wrong password can reduce the vulnerability of passwords below the saturation threshold. Attacks against rate-limited interfaces take a long time and attackers have to be far more circumspect about the guesses they make.

If you’re in any doubt about just how inconvenient rate-limiting can be, just ask the FBI.

The best bang-for-buck guesses for attackers are the the most common passwords, so password blocklists and throttling make a potent combination:

Together with password blocklisting … throttling may almost completely shut down generic online guessing attacks.

NIST (the National Institute of Standards and Technology) now recommends that users be allowed no more than 100 consecutive incorrect guesses in any 30-day period.

Note that whilst sysadmins looking to shepherd flocks of dodgy passwords can feel good about blocklists and throttling, it’s not an excuse for individuals to back off on their password discipline. Recent research showed that if attackers (or more likely their software) target you personally then even the NIST limit of 100 guesses might not be enough to keep you safe.

Enforce two-factor authentication

The paper is tightly focused on passwords and doesn’t cover things like 2FA (two-factor authentication) so I’m going to give it an honorable mention.

Two-factor authentication forces users to provide two pieces of information – typically their password and a code provided by a token, an SMS message or an app.

It protects systems from attackers with stolen passwords, because passwords aren’t enough by themselves to gain access, and it makes guessing passwords online very hard indeed.

Store passwords correctly

Throttling and blocklists are great for fending off online attacks but if a hacker makes off with your password database they can’t help. After a password database has been stolen the password hashes stored inside it are at the mercy of whatever time and hardware the attacker can afford.

How the stolen passwords have been stored makes a huge difference to how big the chasm is.

Passwords should be stored as hashes that have been salted and stretched (for an exhaustive examination of why read How to store your users’ passwords safely).

“Stretching” means repeating the salting and hashing process over and over, typically thousands and thousands of times, in an effort to make password hashing much more computationally expensive.

Moore’s law sees to it that the hardware used for password cracking is always getting faster. Stretching gives system administrators an easy way to keep up – as computers get faster they can simply increase the number of salting and hashing iterations passwords are passed through before being stored.

The upper limit on the number of iterations is determined by what users will stand because they have to wait for their passwords to pass through the salt, hash, stretch process to be authenticated.

The slower the hash the longer that both users and password crackers have to wait:

If 10ms is a tolerable delay an attacker with access to 1000 GPUs can compute a total of … 1012 guesses in four months.  Directing this effort at 100 accounts would mean that each would have to withstand a minimum of T1 = 1010 guesses. Since these are conservative assumptions, it appears challenging to decrease [the chasm] below this point.

1010 guesses reduces the online-offline “don’t care” region considerably but it still leaves us four orders of magnitude adrift of the chasm’s leading edge. But what about other ways of storing passwords?

Administrators can eliminate the online-offline chasm completely by removing the possibility of stolen hash databases, and one way to do that is by using an HSM (Hardware Security Module). An attacker who steals the password database without the HSM has nothing more than a useless list of Message Authentication Codes.

What it all means

The conclusions of the research have the world’s sysadmins in mind. If your job involves looking after users’ passwords and your time is limited then its conclusions can help you focus your energy where it matters – on actually improving security.

If you’re an end-user however, you can’t relax. You’ll never know how your passwords are stored or whether yours sits above or below the saturation point. The measures that sites use to defeat online guessing may be more obvious to you but you’ll still have no control over them, aside from adopting 2FA if it’s available.

Make sure that every password you choose is unique and strong enough to withstand an offline guessing attack. Make each password a random collection of at least 14 letters, numbers and wacky characters and (if you don’t have a photographic memory) use a password manager to keep them safe.