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.
ladies and gentlemen pic.twitter.com/F84ETL7Cwe
— Christian Westman (@westmaaan) 15 October 2016
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.
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.
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
— Spooky Convict (@andreuswolf) October 17, 2016
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]).
- 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.
AS5: You have an oracle for determining if a given userid is valid
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.
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 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
— undefined (@robertmain_) October 17, 2016
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 firstname.lastname@example.org 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”
@pacohope but enumerating users usually isn't regarded as a safety concern but combined with enumeration of passwords it's fatal
— Christian Westman (@westmaaan) October 16, 2016
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.
— Endless Mason (@EndlessMason) October 16, 2016
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.
— Alys (@Actuallyalys) October 16, 2016
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) October 16, 2016
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.
— Kenan Bölükbaşı (@kenanbolukbasi) October 16, 2016
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 (@Actuallyalys) October 16, 2016
Alys commented that this allows me to try passwords without registering a failed login for my victim. Let’s say I figure out that
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 email@example.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.
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.