Windows Picture Passwords – are they really as “easily crackable” as everyone’s saying?

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.