Windows Picture Passwords - are they really as "easily crackable" as everyone's saying?

Filed Under: Cryptography, Featured, Microsoft, Privacy

If you've used Windows 8, or even just seen the ads for it, you'll know it has a feature called Picture Passwords.

You choose a picture, any picture, and then "annotate" it with three finger movements: you can tap a point, draw a stroke, or sweep a circle.

The picture helps you to remember where you made the gestures, so you can repeat them reliably enough to pass the test and unlock your device.

If you have a touch screen tablet, Picture Passwords are surprisingly handy. (Pun intended.)

But how safe are they?

One of the ads I've seen for Windows 8 made a pretty big deal out of the coolness of Picture Passwords, and illustrated their convenience with a login sequence to which my immediate reaction was, "Surely not?"

The ad showed a picture of someone's two young daughters, heads close together and looking at some distant object; the password involved circling their heads and then drawing a line in the direction they were looking.

That struck me as far, far too easily guessed; a bit like an ad showing someone choosing the keyboard password SECRET and implying that would be good enough.

→ The question of whether you should be using something as personal as your children's pictures as a background visible even on a locked device is another issue entirely. I advise against it, but we shan't consider that further here.

Others were concerned, too, including four security researchers from Arizona State University and Delaware State University.

They actually tried to measure the safety of Picture Passwords in a paper presented at last month's USENIX Security Symposium.

Click to read the paper [PDF]...

When the media got stuck into their work last week, the conclusions were often uncomplimentary, with headlines like Windows 8 picture passwords easy to crack and Windows 8 Picture Passwords Easily Cracked.

But what did the researchers really find?

How do you go about cracking Picture Passwords, anyway?

For text passwords, it's fairly obvious what you do: start at AAAAA and go to ZZZZZ (that's brute force, where you try all possibilities), or take some shortcuts and start at ABASH and end at ZESTY (that's a dictionary attack, where you try only the likely ones).

Will this work for pictures?

According to Microsoft's help page, even brute force attacks are impossible [my emphasis below] because there is no limit to the number of possible picture passwords:

Because you choose the picture and the shapes you draw on it, the combinations are infinite — a picture password is actually more secure from hackers than a traditional password.

Oh dear. That's the marketing department getting technical, I imagine.

Fortunately, wiser minds - the developers themselves, in fact - have published a much more sanguine (and well worth reading) paper on the design, implementation and likely strength of Picture Passwords, and they estimate that there are just over 1,155,000,000 (a billion-and-a-bit) possible Picture Passwords if three gestures are used.

→ You should read the Microsoft paper if you want to know the details of how Picture Passwords are calculated (the screen is chopped into a grid with 100 squares on the longer side), and how they are tested (various degrees of inaccuracy are tolerated when you repeat your gestures).

So a brute force attack is certainly possible, where you ignore the picture entirely and just try every possible tap-click-circle combination.

You'll have just over 230 passwords to try (that's a billion-and-a-bit).

That's only about four times as many as there are six-character passwords using the characters A to Z, and no-one is seriously suggesting six-character, letters-only passwords these days.

Furthermore, the equivalent of a dictionary attack is possible, too, if you can identify the most likely Points of Interest (PoIs) in the password picture.

The Microsoft team actually tried to evaluate what effect the complexity of the image had on passwords, and the results were quite dramatic.

With ten PoIs, such as heads, noses, dogs, cats, flowers and so forth, and with gestures based around those PoIs, they estimated that there are about 8,000,000 possible passwords; with five PoIs, you're looking at only about 420,000 different passwords.

That does indeed sound rather limited, equivalent to 23-bit and 19-bit keys repectively.

Online attacks

Of course, we already have an environment where we routinely use 13-bit or 14-bit keys in comparative safety: the PIN on a mobile phone SIM card is only four digits; on a credit card, usually five digits.

Such short passwords are rendered safe by strictly limiting the number of wrong attempts before you get locked out.

And that's what Microsoft has done with Picture Passwords: you can't use them remotely, only if you have physical access to the device, and after five mistakes, you have to switch to using your old-fashioned text password.

So, someone who has a copy of your password picture would have to pre-compute their five best guesses, based on what they know about PoIs and the most likely gesture sequences to go with them, like the "circle your daughter's heads and look where they are looking" password I described above.

Having done that, what's the chance they'll get in?

Groovily, the authors of the USENIX paper quantified that, using a realistic test set of just over 10,000 passwords that they constructed.

Very simply put, here's how well they did:

Automated PoI recognition, 1st guess: Correct  8 in 1000
Manual PoI recognition, 1st guess:    Correct  9 in 1000

Automated PoI recognition, 5 guesses: Correct 19 in 1000
Manual PoI recognition, 5 guesses:    Correct 26 in 1000

That's perhaps not "easily cracked," as the headlines proclaimed, but it's certainly cause for concern when compared against the less than three-in-10,000 chance of correctly guessing a randomly chosen four-digit SIM or credit card PIN.

More precisely, perhaps, it would be cause for concern if there really were just a 0.03% chance of guessing a four-digit PIN code.

But experience suggests that there will always be users who tilt the odds in the favour of the crooks, since not all four-digit codes are equally likely.

For example, Apple iPhone developer Daniel Amitay estimated in 2011 that a "five most likely" list of Apple iPhone lock codes (1234, 0000, 2580, 1111, 5555) would get you in more than 110 times out of 1000.

Against that measurement, the worst case of 26 times out of 1000 for guessing Picture Passwords doesn't sound quite so bad.

So, if you use Picture Passwords, don't make it easy for the crooks: choose pictures with lots of PoIs, and don't just "do the obvious" when you choose the gestures you're going to use.

In short, read the Microsoft developers' paper and treat their example image and gestures as excellent advice on what NOT to do!

Offline attacks

I'll conclude by mentioning something that the USENIX paper touches on, and which is perhaps the most important and as yet unquantified aspect of Picture Passwords: offline attacks.

How Picture Password data is stored, and how password attempts are tested against the database, is proprietary.

With an effective key size of just 30 bits, it is vital to set a very high cost for testing each potential password against an offline copy of the password database.

That requires a computationally expensive Key Derivation Function (KDF).

That's the algorithm by which you convert the digital representation of a password gesture (from a password space of 30 bits) into a unique and psuedorandom choice out of a much larger set of keys, say 128 bits' worth.

Doing this means that attacker can't predict which 230 out of the 2128 keys represent a picture password: they have to calculate the list first, even for a brute force attack.

You needn't inconvenience your users with a KDF, since the extra password validation effort only applies once to each login attempt, but you can make it computationally impractical to try all 230 possibilities.

So here's a free-of-charge technical and marketing suggestion for Microsoft.

Go public - heck, go open source! - with the way that Picture Passwords work, from how they're stored to how the KDF is calculated.

You'd let outside experts assess the risk of offline attacks, which would be technically valuable.

And you'd get great positive publicity for openness, considering the current brouhaha facing proprietary software vendors over the cryptographic influence of the world's intelligence services.

Just saying.

, , , , , ,

You might like

12 Responses to Windows Picture Passwords - are they really as "easily crackable" as everyone's saying?

  1. Nigel · 319 days ago

    The new math: 8,000,0000. (heh) Obviously a typo, but it gave me a bit of a chuckle.

    The paper is definitely worth reading. How cool that Microsoft's own developers did the analysis. And how typically uncool that the Redmond marketing dweebs embarrass themselves yet again...this time with claims of "infinite" combinations.

  2. Machin Shin · 319 days ago

    I'm kind of shocked that during this whole discussion you never pointed out the other flaw in these passwords.

    These "passwords" are being drawn onto the touch screen, most of the time with a finger, meaning that odds are high that your leaving a nice oily pattern behind on the screen. I'm willing to bet most laptops where the user uses the picture password, you can just tilt the screen to see the fingerprints left behind and trace their pastern.

    • Paul Ducklin · 319 days ago

      The Microsoft paper linked to above touches on "grease based recovery" analysis, if you're interested.

      It's a problem with other touch screen passwords, too, where the location of what you touch (keyboard, pattern, picture) to unlock is the same every time.

      You can "countersurveil" by drawing garbage every now and then. Or by *not* cleaning your screen :-)

  3. Metro Sauper · 319 days ago

    My concern is that the gestures are easy to observe. See three gestures, then look at the picture and alighn them to the image.

    • Deramin · 318 days ago

      It's a good concern. The bigger the screen the more of an issue it is, too. You barely have to be paying attention to notice what someone's picture password is. I can see picture passwords being used as a component of a multifactor authentication system, but I don't think I'd trust them by themselves.

  4. Bill Pytlovany · 319 days ago

    There could be 1,000,000,000,000 possible variations but users are still going to use the graphic equivalent of 123456. The majority of users will feel secure with a simple line or circle and based on the image it will often be obvious.

  5. njorl · 318 days ago

    Perhaps the system can be made a little stronger by requiring the user to pick out the relevant photograph from an album of several images, before he proceeds to wipe his paws over it, when trying to log in.

    In some operating systems, including premium editions of Windows, the user's password serves as necessary data for deriving the key used to decrypt (and encrypt) his private storage. Since, apparently, the picture rubbing is an alternative to typing the "old-fashioned text password", I presume it must be possible to "recover" the key, by means of an off-line attack on the gesture combinations. Thus, I would be concerned about how much more vulnerable having the picture log-in may make my privacy.

    The scheme might be very valuable, if it could be modified to require the gesturing and the password (instead of either). Many of us would be content to allow just gesturing to clear the screen lock (ideally, with control over for how long the screen can be locked before the password is also demanded), while retaining password entry as mandatory for logging in and decrypting our data.

    Of great appeal is, I assume, that neither the photograph nor the gesturing needs to be SFW.

  6. The KDF question becomes particularly interesting when you consider that "various degrees of inaccuracy are tolerated when you repeat your gestures" - suggesting either that some reversible hashing (unlikely - I hope) or that some form of lossy encoding is used. A combination lock will often accept numbers off by one (or a few) purely through engineering tolerances; what would you use to hash a text password if you wanted to accept "LETMIEN" and "LETMEIMN" for "LETMEIN" to account for minor keyboard fumbles?

    • Paul Ducklin · 314 days ago

      You could simply calculate the hash of the actual gestures *and all combinations of those near it* that would pass the allowed inaccuracy test, and check all of them against a stored hash...

      According to the docs, there are 37 (X,Y) co-ordinates that are considered close enough for a tap, and similar leeway for lines and circles.

      A mini-dictionary attack, if you like.

      The worst case would therefore be 37x37x6 possibilities to consider if you have three lines (six endpoints), and you'd deliberately do the same amount of work for simpler cases, like three taps, to prevent timing attacks. That's under 10,000 hashes to test. Not that big of a deal, as S. Jobs might have said...

      One reason why open sourcing that part would be doubly cool!

  7. With all this quantification, why not categorize picture passwords into categories (Strong, Weak, etc.) , like keyboard input passwords have been for decades? It would probably enable domain joined Windows 8 devices to use picture passwords. This feature would be an interesting addition to Windows Server 2012 R2 and Windows 8.1, adding another competitive advantage for Microsoft's solutions, specially for companies running Windows Server and considering purchasing mobile hardware for their employees - or even in BYOD cenários.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

About the author

Paul Ducklin is a passionate security proselytiser. (That's like an evangelist, but more so!) He lives and breathes computer security, and would be happy for you to do so, too. Paul won the inaugural AusCERT Director's Award for Individual Excellence in Computer Security in 2009. Follow him on Twitter: @duckblog