Thoughts on Password Strength and Reuse

When I interview software engineering candidates with a security background, I ask them:

Write a function that accepts a password string and returns an integer from 0 to 100 indicating its strength.

In some ways, it’s a fizz-buzz type of problem. Many people can’t easily write an algorithm that guarantees the mapping of a string to a specified range of integers, even if the “strength” algorithm is trivial. The implementation, however, is less important than the reasoning. What makes a password strong?

We want to make it hard for attackers to guess passwords. We could enforce really high entropy passwords, with tough complexity requirements, rotation schedules, and reuse policies. This adds so much frustration to the user experience that you really only see it with a captive user base within an enterprise or under some kind of mandate. Looking at the way most popular services handle password selection, it’s clear that people will only put up with moderate password entropy requirements, and so some users will have relatively simple passwords.

From Password Dictionaries to Dumps

Since some people will have low-entropy passwords, most services will have some form of protection against attackers attempting to log in with a bunch of common passwords. The main defensive tool here is rate limiting, where you keep track of how often someone tries to log in and deny access after a large numbers of incorrect password attempts. If you have sensible and consistent rate limiting, it is pretty easy to determine how many password guesses an attacker would be able to attempt within a given time, and to make sure it falls within a reasonable bounds of your expected password entropy.

Modest password complexity requirements and rate limiting can make remote brute force attacks difficult. But passwords have an inherent tension; the easier they are to remember, the easier they are to guess. This doesn’t just translate to simply constructed passwords. Remembering a good password is difficult, and remembering many different good passwords is really difficult, so people will tend to reuse passwords across sites.

Attackers who get access to a cleartext password dump from any site on the internet, no matter how trivial, can attempt to use the passwords to log in to other, potentially more valuable sites. From a defensive perspective, this can be a problem because it may not be prevented by simple brute-force rate limiting. So what can be done? Expecting users not to reuse passwords, or all services across the internet to store passwords securely, is unrealistic.

I can think of two ways to defend against password reuse that don’t involve changing user or external service behavior: preventing users from choosing leaked passwords, and not using passwords as the sole form of authentication evidence.

Rethinking Password Strength

Fun fact from the early days: Twitter’s password strength check used to consist of a client-side Javascript file of several hundred common passwords and was ROT13 encoded, because it had curse words (e.g. fuckyou) and would be blocked by some adult content filters. Over the years I worked there, we experimented with a variety of password strength mechanisms, including a project where we put passwords from password dumps (as opposed to actual Twitter passwords to avoid potential privacy issues) in a Bloom filter and prevented users from using them, à la the “Popularity is Everything” paper.

There are good examples of estimating password entropy, like zxcvbn, but there isn’t an obvious way to estimate a password’s strength from the perspective of password reuse. Something like haveibeenpwned.com for passwords seems promising, but sending anything related to passwords over a remote connection should raise concerns. I would be interested in a shared collection of leaked passwords from publicly available dumps, perhaps condensed in the form of a bloom filter, that could augment existing password strength meters.

Authentication Isn’t a Boolean Function

Authentication is Machine Learning discusses how passwords represent only one type of signal in an authentication event. There’s also the IP, the user agent, the time of day, previous bad authentication attempts, and so on.

Not only is the input to authentication multi-dimensional, but so is the output. A simple yes-or-no isn’t sufficient. For a questionable login, a service may trust the user to perform some limited actions. Maybe the user needs to provide additional evidence, or the authentication attempt is clearly fraudulent and future similar attempts should be treated suspiciously.

Simply put, blindly exchanging a password for an authentication token ignores many different attack scenarios, including password reuse.

Non-idea: Let’s Kill Passwords

While it’s easy to criticize passwords for their usability and security flaws, they’ve been difficult to displace. An important (and elusive) reason why passwords have never been killed is the advantage of their own longevity. From a usability perspective, the familiarity of the password ceremony makes them easier to use for most people than new and confusing alternatives. From a security standpoint, passwords are at least well-understood and battle-tested, which puts new, even potentially more secure technologies at a disadvantage.

Password reuse isn’t the only way that attackers takeover accounts, but it’s a method that seems to be relatively unmitigated. While I have a few thoughts about how to fight it, I’d be interested to hear about other ideas. So, if I’m interviewing you, don’t just talk about measuring password entropy. Talk about how you’d check if the password was reused in some deep, dark corner of the internet, waiting to be stolen; I’d be impressed.

Thanks to @jimio and @mfinifter for their reviews and #shipits.