A group of researchers consider popularity over-rated and have come up with a novel approach to make password guessing much more difficult.


I have previously reported on the work of Dr Cormac Herley, a researcher for Microsoft. His papers on why users should reject security advice and why userIDs may be more important than passwords were groundbreaking to say the least.

Dr. Herley; along with Dr. Stuart Schechter, also of Microsoft Research and Dr. Michael Mitzenmacher from Harvard University have stepped outside the box once again. The introduction to their new paper, “Popularity is everything” (pdf) foretells why:

“We propose to strengthen user-selected passwords against statistical-guessing attacks by allowing users of Internet-scale systems to choose any password they want so long as it’s not already too popular with other users.”

That grabbed my attention. Apparently, the team has found a better way to combat statistical-guessing attacks, or dictionary attacks, to us IT types. It involves:

  • Limiting the number of guesses an attacker gets.
  • Minimizing the number of accounts that use the same password.

Popularity oracle

The last bullet is a hint at what they’re trying to do. The team wants to create what they call a popularity oracle. If I understand correctly, it’s a web application where we would test our password choices, with the oracle advising us on our choice’s popularity.

You have to admit, the concept has merit. Then, I realized how difficult it would be to get something like this off the ground. Also, what if the bad guys gained control of the popularity oracle? Things would be worse than they are now.

Has the research team thought about this? I felt obligated to ask and here is what they had to say:

TechRepublic: Dr. Herley, you and the other researchers came up with an interesting hypothesis. Could you share a bit about how the idea came about?
Dr. Herley: Sure. Our starting point is that password policies (must be a certain length, include upper, lower, special chars etc) can be very frustrating for users. But web sites feel they must use them to prevent users from gravitating toward obvious and common passwords.

So we stepped back and asked ourselves: What are we really trying to accomplish here? It’s not that we desperately need everyone to stick an ‘&’ or ‘}’ in their password. What we want is to make it hard for an attacker to guess passwords. And attackers guess passwords by trying the obvious and more common ones first. We want to make that attack work less well.

Our idea is that password rules are an indirect and inefficient way of achieving this goal. They make it hard for users, and it’s not clear if they make a guessing attack difficult.

Suppose you have a website with 100 million users, and the 10 most popular passwords are used collectively at 1% of the accounts. That’s a potential 1 million accounts an attacker can get by trying this short list. Now suppose, instead, that no password can be used at more than 100 accounts. In this case, any list of ten gives an attacker only 1000 possible accounts. That’s what our scheme is aiming for.

TechRepublic: Is your contention that even though a password is strong. Being popular, makes it weak and highly guessable?
Dr. Herley: Yes. If a password is used by, say, 0.1% of all hotmail users then I can break 0.1% of the accounts if I know the usernames. It doesn’t matter if the password is ‘snoopy’ or ‘6g$9_35sd.’ Being common is a real problem, whether the password satisfies any definition of being strong or not.
TechRepublic: You mention that existing password-strength meters are less than adequate due to inconsistencies in how they measure strength. Could you explain that in more detail?
Dr. Herley: To be fair, measuring strength is a really hard job. It’s easy to check the length and whether it contains special characters, but it’s not so simple to check if it’s based on a dictionary word. So many strength meters will classify ‘P@$$w0rd’ as strong and ‘hdgopw’ as weak, while you’re probably a lot safer with the latter than the former.
Dr. Schechter: Password-strength meters use heuristics – simple rules -to guide users to supposedly stronger passwords. For example, some will report that a password is strong if it contains uppercase characters, digits, and special characters. As with any heuristic, there are times when they will come to the wrong conclusion.
TechRepublic: You suggest using a count-min sketch as the data structure to track password popularity. Your reasoning it seems is that it would be more efficient than just listing the passwords in a database. I have been trying to understand how a count-min sketch works, unsuccessfully I might add. I would appreciate your insight as to what they are and how they would be better than just a simple database of passwords.
Dr. Herley: Our approach is to rule out passwords that become too popular, so we need some way of keeping track of popularity. Now, we could just store a popularity table of passwords, but that would be insecure. If it leaks, it gives an attacker a roadmap of what to try first.

Of course we try to prevent it from leaking, but we don’t want to assume that. For example, an attacker could then just try all of the popular passwords on every username he can find. So we want to be more sophisticated than that.

You can think of the count-min sketch as an oracle that sometimes lies, but only in one direction. It keeps track of which passwords are popular and answers the question ‘is this password popular?’ If the password really is popular, it always answers truthfully, i.e., yes. But, if a password is not popular it sometimes, at random, answers yes.

These are the false positives. These are valuable, because now an attacker who has access to the count-min sketch doesn’t have an easy way figure out which passwords are truly popular, and which ones are not. He can’t just use it to compile a list of which passwords he should try first.

Dr. Schechter: If an attacker compromised a simple database of passwords, he would immediately know which passwords are in use by the systems users and which passwords were in use by the most users.

Our proposed data structure does not store the passwords themselves and tracks popularity only so far as to identify passwords that are too popular. It does not allow the attacker to determine which of the (large number of) passwords that we consider too popular are the most popular.

TechRepublic: The paper mentions:

“Replacing password creation rules with popularity limits has the potential to increase both security and usability.”

Could you explain why you feel that way?

Dr. Herley: The way things are, attackers can be confident that a lot of people gravitate toward the most obvious passwords allowed by a site. So a dictionary or list of the most common choices is what they try. Our scheme makes things more secure by ensuring that no short list covers too many accounts.

Our hope is that it’s less inconvenient to be told occasionally that a password is too popular than to deal with complex password rules users now face. This appears hopeful since, as I’ve said, the complexity rules are a very indirect way of making guessing attacks hard, so they needlessly forbid many choices that are probably perfectly fine passwords.

TechRepublic: Could you give us some idea as to when a password becomes dangerously popular?
Dr. Schechter: One might consider a password to be popular if more than one in a million people use it. For large systems with over a hundred million users, a password would become dangerously popular when over a hundred other people were already using it.
TechRepublic: In the paper, you were acutely aware of the leverage attackers would have if they had access to the password oracle. How would you make sure that would never happen?
Dr. Schechter: The password popularity oracle could be guarded in the same way that the existing password database is guarded. That said, we have designed the oracle expressly to minimize the consequences of compromise.

In fact, it does such a good job of hiding information that it may make sense to release the oracle for use by others, even if that means attackers could obtain a copy of it.

TechRepublic: The paper suggests a novel way to use a CAPTCHA application. Could you explain how it works?
Dr. Herley: A successful defense against statistical-guessing attacks requires not only the avoidance of popular passwords, but also mechanisms to limit the number of guesses an attacker can issue. Limiting guesses (using a CAPTCHA, for example) is especially important if users aren’t forced to avoid popular passwords, or if users with accounts that predate the no-popular-passwords policy have not been forced to select less-popular passwords.

If users knew that when a CAPTCHA appears, it means the password is too popular. It would be added incentive to change the password to a less-popular one, removing the need to fill in a CAPTCHA at every login.

TechRepublic: The concept of using a popularity oracle is interesting. What would it take to have a workable system on a scale that a significant number of people could use?
Dr. Schechter: The data structure itself is rather straightforward. The challenges of integrating such a feature into a larger system are usually dominated more by the specifics of the larger system than the feature itself.

Final thoughts

By definition, using a popularity oracle would reduce the bad guy’s odds of guessing correct passwords. Couple that process with using complex userIDs and bulk-guessing attacks become ineffective, a good thing.

I would be remiss if I didn’t take time to thank the researchers for helping explain the concept of a popularity oracle.