System-Wide Unique Passwords (SWUP)

System-wide Unique Passwords (SWUP)

Here’s a possible security control, prompted by @westmaaan‘s Tweet. I call it “system-wide unique passwords” or SWUP for short. When users create accounts or change their passwords, the system should make sure that no two users have the same password on the system.

In this blog I lay out some high-level system design, some benefits, and some disadvantages. I’m trying to explore this. The goal of this entire post is to explore the benefits of this system to see if they’re worth the cost. The problem I’m having is that too many people are distracted by what they think are weaknesses created by this system. So in the interest of getting to discuss the benefits, I will address each of these supposed attacks. I’ll try to show that they are not interesting or not impactful. I’m not sure SWUP is a good idea, but I’m also not convinced it’s a bad idea. I’ll update this post in response to comments and ideas.

The Design

Basic Behaviour

When you go to create an account or to change your password, you enter a new password. If the new password you’ve chosen matches any password currently used by any user on the system, you’re told you need to choose another password. (It doesn’t matter if it tells you “someone else has that password.” We assume a clever hacker will figure that out even if we don’t say so.)

Some Standard Defences

We assume that we do a lot of pretty basic defences. I’m not interested in the argument that lots of people don’t do these things. They could. So lets assume we put rate limits on the create account page. We can put captchas in place and some basic validation. For example, when you create a new account you have to click a unique link that we email you. After you verify your email by clicking the link, THEN will ask you what you want for your initial password. Thus, for you to enquire about passwords through the create account page, you are limited by your ability to provide valid email addresses, invoke the verification links we send, and defeat a captcha. None of those things is impossible. It’s totally possible to do all 3. But it significantly limits your ability to use the create account workflow as a high-volume password oracle. And it’s going to be really, really slow, no matter how much you automate it.

Standard Rate Limiting

After some number of duplicate passwords (maybe 10?) are attempted, we’ll rate limit you. E.g., “try again in 1 minute” followed by “try again in 2 minutes” and so on. Rate limiting is done at the application layer, based on the email address you’re supplying. It’s not based on some stupid thing like IP address.

We assume that we rate limit password changes in the same way. After some number of invalid new passwords (maybe 10?) are attempted, we’ll rate limit you. E.g., “try again in 1 minute” followed by “try again in 2 minutes” and so on.

Legitimate users will almost certainly have to try a few passwords before they find one not in use. But I’m asserting that virtually none will take more than 10 tries.

Some Assumptions

I think this security idea is only useful or appropriate when these assumptions are true. If one of these assumptions is false, then I probably agree with you that SWUP isn’t a good idea for that system.

AS1: You have 1M+ diverse, internet accounts
You have lots of accounts (1M or more) corresponding to diverse, random, unrelated internet users. This is a public web or mobile app, not a private or enterprise system. It is not 1000 people who all work for the same company, or 5 bloggers who all know each other, etc. Big numbers of users, minimal relationships with each other.
AS2: Getting a complete list of valid users is not a legitimate use case
Think about services like eBay, Netflix, Twitter, Yelp. Even government agencies like tax authorities and banks could do this. I assume you can get lots and lots of login IDs, but you can’t be sure you have even a majority of them, much less a complete list. Getting a list of users requires hacking or insider/administrative access. (Sometimes I relax this assumption)
AS3: You use username and password for authentication
Don’t comment “passwords are dead, use XYZ instead.” User names can be as weak as you like: email addresses, userids, student IDs, whatever. There have to be at least 1M of them, though. There’s no MFA. Assume that MFA isn’t necessary for the kind of system this is.
AS4: We do password storage right

We do PBKDF2 with a strong symmetric cipher. It’s reversible. If someone steals the password database but not the key, the passwords are strongly protected. Please don’t comment that people will store passwords wrong. The question is more interesting if we assume they don’t. I cover protecting the key among the disadvantages (see [DA1]).

AS5: You have an oracle for determining if a given userid is valid
But you have to invoke that API, and I can rate limit it some if I want to. I think this is a more interesting discussion if we allow this. It’s realistic.

Advantages

This is the goal of this blog post. Why is this worth doing? Did I miss an advantage? Let me know in the comments.

AD1: Reduce Impact of Dictionary-based and Random Password Guessing
All passwords across the whole system are unique. If you’re a hacker trying to brute force guess passwords, there’s at most one account that has the password you’re trying. You might have a dump of lots of passwords from other sites, but this limits their value. You have to brute force much much more to find a single vulnerable account. Now, if the user uses the same userid/password on my site as on some other site, and that other site gets compromised, there’s nothing I can do. This doesn’t make that worse or better.
AD2: Encourage use of Stronger Passwords
The top 50 crappy passwords will be taken by the first 50 users who pick them. This should harass the worst/laziest users who are prone to using crappy passwords. Those are precisely the people who deserve to be harassed into picking better passwords. I think it won’t trouble users who pick decent passwords that are unique to themselves. Instead of having 1000 users using 123456, I will have exactly 1.
AD3: Attacks on the users become noisier
You have to try a lot harder and a higher number of accounts before you can hope to succeed. The more you have to try, the easier you are for me to detect and respond to.
AD4: Trickle Down Password Improvement
Forcing people to pick better passwords on ONE system should have a ripple effect on other systems that these users use. This is a weak benefit. The idea that maybe, just maybe, it will cause people to start doing better things with their passwords.
AD5: Not the Slowest Zebra
The slowest zebra gets eaten by lions. If someone wants to brute force attack user names and passwords, they’ll have less success on a SWUP-enabled site than on another site. So they’ll spend their time attacking someone weaker than me. The harder I make brute force attacks (especially in wall-clock time) the more likely the attacker is to go elsewhere.

Disadvantages

It’s not flawless. I see some real disadvantages. That’s really what I’m trying to get at by blogging about it. Are the advantages worth the disadvantages? Did I miss a disadvantage? Let me know in the comments.

DA1: Symmetric Keys and Reversible Password Storage
I’ve never been a fan of using symmetric keys this way. Managing the key securely and separately from the password database is non-trivial. If the database of passwords is dumped/lost/hacked without losing the encryption key, we’re pretty safe. This absolutely can be implemented with the same level of security as PBKDF2 with a one-way hash and all the other best practices applied. If the password database AND the key are simultaneously compromised, we’re in deep shit and that’s my biggest worry here. This is not impossible to do right. It’s just complicated.
DA2: I’m worried about scale
I don’t know how time-consuming and practical it is to look up a new password in the password database and see if it’s in use. I worry about how slow and non-scalable this might be to implement in production on a sizeable, multi-region, distributed system. Having said that, we won’t do it often (except if hackers are messing with it). We only do this at account creation time and at password changing time. Those are comparatively rare user journeys and users aren’t expecting lightning speed on them, the way they expect lightning speed on more common journeys.
DA3: I’m worried about the user experience
Clearly some systems work this way, but I’m not sure we have much data on how user’s feel about being forced to keep trying passwords until they get one the system likes.
DA4: You can’t convert to this easily
If you already have a strong, secure password storage system, you can’t easily change how your passwords are stored. You could gradually migrate by updating the password storage each time a user logs in. But it still is a lot of work to migrate to this, if you found the benefits compelling.
If you’re starting off fairly green-field, this is probably easier to do from the beginning. Having said that, in the early days of systems, many of the mature defences I have assumed (rate limiting, etc.) are not present. Without them, this isn’t as safe as I suggest it is.

The Attacks

The main attacks that people seem to worry about on Twitter have centred around confirming a real password on the system. Did I miss an attack? Let me know in the comments.

AT1: Making Brute Force Easier

You can figure out that someone uses 123456 (or ‘AG298/dk’ or whatever strong password) as their password on the system. I think this is no big deal. If the system normally allows 123456 as a password, and it has 1M+ users, then it’s a safe bet that the system has many users with the password 123456. It’s one of the top 50 crappy passwords. So we don’t need an error message telling the attacker that someone has 123456 as their password. It’s a safe assumption. So if enumerating users and trying the password ‘123456’ on all users is a practical attack, we’re not making this attack easier or higher impact. In fact, we reduce the impact because we limit the number of accounts you can find. We might confirm for you that ‘AG298/dk’ is currently in use as a password, but you still have to find the one user that has it. If you learned somewhere else that bob@example.com uses ‘AG298/dk’ as his password, SWUP hasn’t made this easier. You’re not gonna go through some roundabout, indirect test. You’re gonna try to login and see what happens.

“Just Try All the Users”

This is an important point. Christian is not the only person saying that it’s trivial to try all accounts with a given password. I don’t think that’s easy or practical. Because if it was so easy and so practical, this would be a huge problem today, where every system in the world already has thousands of accounts that use the top 50 crappy passwords. It’s one thing to have a list of LOTS of accounts. It’s quite something else to have a list of 100% of the accounts. If knowing a legitimate password—but not what account it belongs to—is such a big deal, then we should see the users who use crappy passwords being consistently and constantly pwned. “Trying all the users” should work right now and it should work much better now than it would on a system with SWUP.


If, today, the system allows hundreds or thousands of people to use 123456 as their password, it will be hundreds or thousands of times easier to find one of those accounts. With a SWUP system, there is at most one user with 123456 as their password. Brute forcing the user base will yield exactly one account, and will require a LOT more brute force attempts than if there are 1000 accounts out of 1M+ who all use 123456 as their password.

So if you believe that brute forcing all accounts is easy, you should be in favour of SWUP. SWUP dramatically increases the amount of work an attacker has to do to find a single user account that has a known password.

Check my Maths

I think this is true, but I welcome someone who actually knows maths to help me here. Assume I have exactly 1M accounts. And (despite [AS2] above) my attacker has a list of my 1M accounts. They know that abcde12345 is a password in use by exactly one user.

Assuming they randomly try accounts with abcde12345 as the password, we expect them to find that one victim account after 500,000 attempts on average. (right?)

Without SWUP, I might have 100 accounts using abcde12345. In that case they would find a victim account after 5,000 attempts on average, right?

So if we assume 10% of accounts (i.e., 100,000 out of 1M) use one of the top 50 crappy passwords, how many attempts do we need to do on average before we hit our first valid victim? And if only 50 out of 1M accounts have one of the top 50 crappy passwords, because of SWUP, how many attempts do we have to do before we hit our first victim?

AT2: Pruning Your Attack Dictionary

One Twitter user commented that this would allow a potential attacker to tune the dictionary of possible passwords. He could use the oracle to eliminate words from his password dictionary that weren’t actually being used as passwords on the system. If your brute force dictionary contains only passwords that are definitely in use on the system, the brute force attack will be much more effective. This is true in theory. In practice, I think it would be ineffective.

Remember that SWUP will rate limit your ability to attempt to change passwords. You’ll have to either use your own legitimate account, or use some automation to create and use lots of sock puppet accounts. Your bandwidth for using SWUP to verify passwords will be limited by the number of sock puppet accounts you have on my system times the amount of attempts I let you do with the rate limiting in place. That might be 15/hour per sock puppet account. So if you have 1000 sock puppet accounts, you can verify something like 15,000 passwords per hour. If your dictionary is millions of potential passwords, you’re not going to eliminate a significant number by first testing them against the SWUP oracle.

Using the oracle this way is also a really noisy attack that’s easy to detect and throttle. After all, you have to be logged in, or you have to do several steps of the new account workflow before you get to the oracle. That’s really easy to rate limit because I do the limiting on real application-layer session IDs or application-layer user IDs, not something stupid like IP address. And it’s pretty easy to detect a sock puppet account if the only function they ever call is the change password function. So it’s easy to write a job that sweeps through the user database deleting or locking suspected sock puppet accounts.

It’s also easy to make the normal, happy path use case slow on purpose. That will discourage abuse, but won’t bother real users because they rarely create accounts or change passwords. Legitimate users won’t care if I deliberately introduce a 2 second sleep into the new account or change password process. But that delay will severely limit an attacker’s ability to script and use this function as an oracle.

AT3: Dumped Credentials from A Breach Elsewhere

If you have a list of dumped credentials from Adobe or Yahoo! or whatever, you’re not going to use the create account workflow or change password workflow to see if those credentials belong to some user on my SWUP system. You’re just going to try logging in with the leaked user name and password and see what happens. The SWUP mechanism is irrelevant to protecting from a credential dump on someone else’s system. That’s not an attack it addresses, and SWUP doesn’t make that attack easier, harder, more effective, or less effective.

AT4 Targeting a User

Kenan Bölükbaşı (@kenanbolukbasi) hypothesized an attack where you know your victim well enough that you can think up a unique password that only that particular victim would use. You could try to set your password to this unique password, and if you discover that password is in use, you suspect your victim is probably the account using the unique password. Let me give an example. Let’s say your university gives each student a userid composed of their initials and a few random digits. Ignoring [AS2] above, you get a list of users. You think “all the students entering in 2016 might set their password to 2016 plus their userid”. So you find a user named abc123 and you try setting your password to “2016abc123”. If you’re denied, you figure user abc123 must be the user who’s using 2016abc123 as their password, and you go try it on their account. Any structured situation where userids are systematically generated with potentially guessable passwords is a candidate for this attack.

I think this is an unlikely edge case that isn’t particularly interesting. In the case that you know your target well, you presumably only have a handful of passwords you’re going to try. The fact that you can leverage this oracle without recording a failed login on the target account doesn’t make your attack faster, more effective, or particularly stealthier. You still leave a big ole trace in the logs because you had to either login or create an account to use the oracle function. It’s obvious which account is the attacker, even if it isn’t obvious who their intended victim is.

AT5: Targeting Users Without Logging In As Them

Alys commented that this allows me to try passwords without registering a failed login for my victim. Let’s say I figure out that example.user@gmail.com uses ABC123xyz as their password. I try to change my password to ABC123xyz. If I’m denied I conclude that it’s probably in use by example.user@gmail.com. Now I go try to login as that victim with that password.

I don’t think this is important. I think if you’re a hacker who’s trying to figure out whether your stolen credentials work, you’re just gonna try them. This whole mechanism for using SWUP as an oracle is too much of a pain in the ass. It doesn’t give you an interesting advantage. You wouldn’t do the programming work necessary to automate this because it doesn’t really help you enough.

Your ability to attempt passwords without producing failed login attempts is limited by the number of sock puppet accounts you use and the normal rate limiting I put into the function.

Conclusion

First and foremost let me reiterate that I’m exploring this idea. Not saying “everyone must rush out and do this now!” I’m interested in it.

The main benefit to SWUP is reducing the impact of random/dictionary brute-force guessing, and making it harder and noisier to attempt. Those who try to brute force guess will be forced to make orders of magnitude more guesses to find a single hit. That makes them easier for our security operations to detect and easier to respond to. If they do find a valid userid/password pair, they’re guaranteed to find only one. This reduces the impact of successfully guessing. You have as much chance of finding the user whose password is 123456 as you do of finding the user whose password is something you found in a credential dump. It also makes users avoid many of the terrible passwords that are quite common.

What am I not accounting for? What am I missing? Let me know in the comments.