What is your mother’s maiden name? How about your pet’s name? Questions like these were a dark corner of security systems for quite some time. Most security researchers instinctively think they aren’t very secure. But they still have gained widespread deployment as a backup to password-based authentication when email-based identification isn’t available. Free webmail providers, for example, may have no other choice. Unfortunately, because most websites rely on email when passwords fail, and email providers rely on personal knowledge questions, most web authentication is no more secure than personal knowledge questions. This risk has gotten more attention recently, with high profile compromises of Paris Hilton’s phone, Sarah Palin’s email, and Twitter’s corporate Google Documents occurring due to guessed personal knowledge questions.
There’s finally been a surge of academic research into the area in the last five years. It’s been shown, for example, that these questions are easy to look up online, often found in public records, and easy for friends and acquaintances to guess. In a joint work with Mike Just and Greg Matthews from the University of Edinburgh published this week in the proceedings of Financial Cryptography 2010, we’ve examined the more basic question of how secure the underlying answer distributions are to statistical guessing. Put another way, if an attacker wants to do no target-specific work, but just guess common answers for a large number of accounts using population-wide statistics, how well can she do?
Answering this question first required developing the right mathematical model for resistance of a question to guessing. Entropy (specifically Shannon entropy H1) is commonly thrown around as the measure of resistance to guessing, but it was never intended for this purpose and is not appropriate for measuring guessing of non-uniform distributions. Guessing entropy G, the expected number of guesses if answers are guessed in decreasing order of likeliness, is better, but still highly skewed by low-probability events which wouldn’t be guessed in practice. We’re concerned with a trawling attacker, who will guess values like “Smith,” “Jones,” and “Johnson” for a target’s mother’s maiden name, and then move on to other accounts if these don’t work. The frequencies of uncommon names like “Zabielskis” are irrelevant because a trawling attacker will never try them, yet they inflate the values of both H1 and G. Entropy can be very misleading for real-world security, and we hope a contribution of our paper is to encourage the use of “marginal” guessing metrics instead. We even provide a few theorems that prove in a strong way that high entropy (H1 or G) can give you no security at all against a trawling attacker in the real world.
Using these new metrics, we examined a range of statistics on answer distributions to common personal knowledge questions. It turns out the majority of personal knowledge questions ask for proper names of people, pets, and places, and the rest are trivially insecure (eg “What is my favourite day of the week?”). We collected government census data, pet registration records, and also completely crawled Facebook’s people directory. Incidentally, we believe this Facebook names corpus, consisting of 269 M full names, is the largest such dataset ever assembled and may have many uses outside of security research, which we are happy to provide it for.
Analysing our data for security, though, shows that essentially all human-generated names provide poor resistance to guessing. For an attacker looking to make three guesses per personal knowledge question (for example, because this triggers an account lock-down), none of the name distributions we looked at gave more than 8 bits of effective security except for full names. That is, about at least 1 in 256 guesses would be successful, and 1 in 84 accounts compromised. For an attacker who can make more than 3 guesses and wants to break into 50% of available accounts, no distributions gave more than about 12 bits of effective security. The actual values vary in some interesting ways-South Korean names are much easier to guess than American ones, female first names are harder than male ones, pet names are slightly harder than human names, and names are getting harder to guess over time.
Still, there is a strong result that anything named by humans is dangerous to use as a secret. Sociologists have known this for years. Most human names follow a power-law distribution fairly close to Zipfian, which we confirmed in our study. This means every name distribution has a few disproportionately common names—”Gonzalez” amongst Chilean surnames, “Guðrún” amongst Icelandic forenames, “Buddy” amongst pets—for attackers to latch on to. Combined with previous results on other attack methods, there should be no doubt that personal knowledge questions are no longer viable for email, which has come to play too critical a role in web security.
As I see you are dealing with statistical research: I have put one of the most comprehensive link lists for hundreds of thousands of statistical sources and indicators on my blog: Statistics Reference List. And what I find most fascinating is how data can be visualised nowadays with the graphical computing power of modern PCs, as in many of the dozens of examples in these Data Visualisation References. If you miss anything that I might be able to find for you or if you yourself want to share a resource, please leave a comment.
I have been saying that security questions are not secure because of how easy it would be to figure out the answers, especially when it sometimes is a matter of public record and anyone can look it up. As a tip, I generally produce a ‘random’ set of characters as the answers so it’s not easily guessable.
The reason that such questions have had traction is fairly easy to answer 😉
“The failings of humans in general”
We lose things easily including our memories and we also have difficulty remembering anything except by association.
And it is this that in all likely hood gives rise to Zipf (linear on log log axis) behaviour.
However the real question after “proving the and quantifying common knowledge” (ie it’s a broken system only more broken than we guessed) is what do we do about it…
And the answer I suspect will be bassed on “live with it” or “work with it”.
Currently we are talking about one security question giving 2^8 bits of security, however what about 2 independent questions where both questions have to be answered before any indication of correctness or incorectness is given.
I would guess that most humans could stretch to 4 questions.
The question then arises what happens to the “trawl technique” and is there a more optimal attack on such a system.
The reason I say this is that it is a generaly held opinion (amongst security related practitioners) that a National ID is bad because although it can be seen as a strong authenticator (of it’s self) it is a single point of attack (1 bad apple human) and proof of ID is better established with a wide range of weak authenticators.
That is the law of diminishing returns can work in your favor.
This is most often seen in safety systems. For instance the effectivness of a seat belt increases linearly but at exponentialy increasing cost. Likewise the effectivness of an airbag increases linearly with exponentialy increasing cost. However you can beat the cost rise by putting an adiquate seatbelt and adiquate airbag effectivly in parellel and end up with a higher effectivness for less cost. Likewise adding sipps, crumple zones etc etc.
You can thus effectivly engineer a high safety value at a cost minima which is not possible any other way.
You see similar occuring with with high availability systems built with low reliability COTS systems worked in multiple redundancy to get availability figures up.
Any where you have a linear improvment for exponential cost increase on a single item is ripe for getting this sort of treatment, and these “security questions” are a prime example of where it might be brought to bare.
The downside of course is still humans who insist on putting their whole lives in the public record. But then there is “no helping some people” they will always “shoot themselves in the foot” even with an unloaded gun…
@Clive
Very good comments. I agree that requiring more than one question is a nice improvement, though I’ve rarely seen this done. One problem is that it can be hard to come up with a large number of questions (since many don’t apply to some individuals), and users pick terrible questions when left to their own devices. An interesting idea is to pick dozens of yes/no questions like “do you like country music?”: http://www.ravenwhite.com/files/quantifying.pdf
Even in our paper we recommend some simple fixes if we can’t change the current system-the answer distribution can be proactively shaped by the server by probabilistically rejecting the most common responses.
I’m not sure the security increase is quite exponential though. Certain attacks (research and social engineering) don’t get much harder to pull off for multiple questions than for one. Also, people’s likelihood to forget the answer to one of the questions will go up exponentially.
There are a boatload of other problems as well: privacy of giving these answers away, and the fact that it’s very hard to give different answers to different sites. Personally I think the whole personal knowledge approach is always going to be problematic. I’d prefer vouching-based authentication (http://portal.acm.org/citation.cfm?doid=1180405.1180427) or using alternate channels like text message.
Someday maybe we’ll combine all three, and add a few more in. It depends on how serious people care about webmail security, but the trend is that it’s getting more and more important and protecting it with just one basic question seems like a relic of the early days of the internet.
The weakness of that scheme is not surprising. When faced with that type of system I use a workaround to avoid the security risk. Essentially, I use a randomly generated answer that is totally unguessable. So, that will make a trawling attack fail on my accounts. More importantly, since you must supply an answer, any other way of answering decreases the security of the account. That type of measure is a security weakness tolerated for economic reasons, we may not be able to refuse using it but at least it is possible to avoid it’s inherent risk.
@ Joseph Bonneau,
Sorry I’m a little late replying I’ve had my time tied up a bit at this end.
The main problem I see with all authentication systems is not in “finding” alternatives but in “replacing” existing systems.
Forty years ago we knew that passwords where a bad idea, yet here they still are alive and causing problems major problems.
The only improvment in passwords has been asking users to use complex password scheams that fail for various reasons to do with “human failings”.
[And yes I’m a “sinner” I’ve a couple of online accounts I cannot get into because I cannot remember my “clever” passwords and answers. Now if I’d put in the real name of my first pet…]
Worse of all the alternatives that are practical sugestions in most cases they will all fail to human weakness (we forget/break/lose/have stolen/etc things and move on without full consideration).
So unfortunatly we have these systems not just because they are simple to build, but because they do work with falable humans (except for that reset password button that emails to an email account you nolonger have as you’ve moved on to a new employer/ISP/etc).
The obvious solution is of course the easy “universal unique identifier used as an authentication token”, but then… That has a whole host of issues it’s self not least of which are “who pays” and an individuals “roles in life” that realy should be seperate otherwise the anonymity that is required for our current societies to function is broken…
So if we cannot “replace” such pasword etc systems the best we can do is “augment” them.
Which then brings up,
“how do you augment without effectivly replacing”…
Hence my sugestion of two or more questions.
Which you quite correctly show does have it’s failings (those pesky humans again 😉
It is without doubt a very very hard problem simply because of “human failings”.
And I for one am most definatly not in favour of the “Government Soloutions” of National ID’s etc because in the long term their use to society is detrimental to the extream.
Slightly OT, but I did enjoy Lucy Porter’s subversive take on this:
http://www.youtube.com/watch?v=q3ALAjwuO1M
While I realize this is an academic site I do wonder just how much of a real problem this weak security actually represents. The example of celebrities is not persuasive as an attacker has a strong incentive to devote time and resources to the problem. But if you told me out of the blue that someone had a 1/84 chance of stealing my account data I’d take it in a flash. I think those odds are wonderful! I can’t imagine any attacker spending that amount of time to get the $100 in my bank account.
And that’s a real critical point. Names might be “good enough” security. Unless there is a real and honest evaluation of the cost of the attacking the account compared to the benefit accruing to the hacker, this research remains non-compelling.
Daniel you’re missing the point.
If some unscrupulous person is attacking a wide range of accounts to get at $100 in each account, the statistics say they will get approximately 1 success for every 84 account attempts. For rounding sake say they try 840 accounts, that’s 10 success = $1000. Keep increasing by powers of 10 & then think about how much time it would take to try all those accounts given even a relatively low power laptop & a coffee shop WiFi connection.
Also if you’ve only got $100 in your account right now, once they’ve gained access to your account whats to stop the unscrupulous type looking at your history, seeing when your salary or other regular payments arrive in your account & waiting until then to empty it?
I recently reset the password for two of my Apple accounts (I think both date to before they did SSO; I also have records of a third account which I can’t log in to). It’s a bit surprising when it says “Your account has been locked for security reasons.” but you can still unlock it with an insecurity question.
If I care about reproducing an insecurity question answer should my password storage mechanism fail, the question is something like MAC(k,”FooWebsiteQuestion1″) and the answer is the MAC (I usually paste the shell command as the question so I get the right hex/base64/truncated/etc answer). It’s not that secure, but I’m reasonably sure that all existing copies of k are under my control.
If I don’t care that much, I use a slightly different method:
• If I need to give an answer over the phone, use a few random words with something like
python -c 'import random,math;l=list(set(map(str.lower,open("/usr/share/dict/words","rb").read().split())));print "%r, %f bits"%(random.SystemRandom().choice(l),math.log(len(l),2))'• If not, I generate it the same way I generate passwords:
dd if=/dev/random count=1 | openssl sha1 -binary | openssl base64 | sed -e's/.==*//' | tr /+ -_(thesedremoves the characters without 6 bits of entropy).If I get to pick the question, my latest choice is “random1” and “random2”.
Permit me to suggest a model for “mere mortals,” to invent a reasonably secure password which, I believe, will confound hackers AND be easy to remember:
Pick a favorite tune and the last 4 digits of your mother’s phone number. i.e. My Country Tis Of Thee and Mom’s # 7856
The password uses the first letter of each word and adds Mom’s number, BUT hold the shift key when typing the numbers. The password becomes:
MCTOT&*%^
@Harold:
No – that’s dumb. It’s an exercise for you to figure out why.