Anatomy of a brute force attack – how important is password complexity?

You may have heard of the curate’s egg.

It comes from a wry Punch cartoon from the late nineteenth century in which a curate (a junior cleric) is having breakfast with with the Bishop (a senior cleric), when the latter offers an apology, saying, “I’m afraid you’ve got a bad egg, Mr Jones.”

Determined to salvage the situation by finding someting positive to say, the curate replies, “I assure you that parts of it are excellent.”

And it was in that vein that my friend, colleague and popular (though sadly only occasional) Naked Security writer, Ross McKerchar, waved in front of me a recent article on password security.

It was published on Redmondmag, a indepdent website about Windows that is well-read and reasonably influential, and it attempted to answer the question, “How Important Is Password Complexity?”

The good part of this curate’s egg is that the author, Brien Posey, took a hands-on approach, and came up with a realistic Spy-vs-Spy password recovery scenario.

His wife created a password protected file, with nothing more than “make it a strong password, but not to go crazy with the password length” as her guidelines; he then set about cracking it by brute force.

→ Brute force is the way you open those cheap bicycle locks with wheels numbered 0 to 9 if you forget the code. You turn the dials to 0-0-0 and then click round systematically, counting up digit by digit, until the lock pops open or you reach 9-9-9 and realise you need to start over and be more careful.

We hear about cracked passwords so frequently these days that you might imagine that Brien probably opened up the file in hours, or even minutes, but he did not.

Afer a while, he decided to throw more energy at the task, ramping up to 40 CPU cores operating in parallel for few hours, before settling back on eight cores after some overheating issues.

Fast forward two weeks, and he still hadn’t got anywhere.

→ When running a password crack, the algorithms involved usually give all-or-nothing solutions. Typically, you don’t recover the password character by character, which might give you just the sort of hint you need to cut corners by guessing correctly. An incorrect password that is off by one character returns an identical sort of “No” to one in which every byte is wrong.

At the rate he was able to churn through passwords, with eight CPU cores dedicated full-time to the task, he calculated he’d need more than five years to be certain of finishing, even limiting himself to an eight-character lower case password.

Allowing passwords to use both upper and lower case doubles the number of password possibilities for each of the eight characters, therefore multiplying the total guessing time by 256 (2⁸).

Now we need until the next millennium to be sure of cracking the file.

So Brien’s conclusion seems to be that eight characters might actually be OK for a password, while nine effectively builds an insurmountable barrier to cracking.

Why, then, will you read elsewhere, including on Naked Security, recommendations for yet-longer passwords?

My personal guidelines suggest to aim for 14, switching as arbitrarily as you can between UPPER, lower, d1g1t5 and \/\/@ckies.

Did Brien give us risky advice?

Ross and I decided that he did.

There are three main reasons:

• Not all password algorithms are made equal.
• Not all password choices are made equal.
• Not all password crackers are made equal.

Let’s look at these in turn.

Not all password algorithms are made equal.

Brien’s adversary (or in this case, his wife) used a ZIP file protected with WinZip’s AES-based encryption using a 256-bit key.

Its resilience isn’t so much because it uses 256-bit keys, but because the encryption system uses a technique called PBKDF2 (password-based key derivation function, version 2) to take the passphrase you enter and turn it into the string of bits that is actually used as the key.

For every password you want to check, e.g. aardvark, you first have to churn the characters in the password through a hashing algorithm that is repeated 1000 times; only then do you get the actual bit-for-bit key that was used.

That dramatically reduces the rate at which you can guess passwords.

But if Mrs Posey had needed compatibility, so she could open her passworded file with ZIP versions other than WinZip, she’d probably have ended up with the previous sort of ZIP encryption instead, called PKZIP.

Brien’s eight cores’ worth of server managed just 1200 WinZip passwords per second, thanks to PBKDF2; my Mac can try 25,000,000 PKZIP passwords in the same time.

Brien’s five years of cracking time for eight letters just turned into two-and-a-half hours; instead of waiting until next millennium to crack the nine-byte passwords, he only has to wait until next month.

Not all password choices are made equal.

When humans choose passwords, even if they make an effort at complexity, they just don’t choose from all possible combinations.

If you go for an eight-character lowercase password, history suggests you are more likely to choose password than qwertyuiop, and much more likely to chose either of those than exiflqae.

So, even when they are not being fed from a dictionary of known words, smart password crackers don’t just start at 0-0-0, like we did with the bicycle lock above, and march forward one by one.

They use a bunch of heuristic rules to produce candidate passwords in an order that tends to flush out poorer password choices much faster than truly randomly chosen ones.

You can see this in an image I produced when I had a go at a bunch of password hashes revealed in a database breach at Philips in 2012.

If humans chose passwords randomly, you’d expect a straight diagonal line from bottom left to top right in this cumulative graph.

But John the Ripper’s password generator, which deliberately tries to be as non-random as humans, managed to pick out 20% of the passwords in the first second of its run.

Not all password crackers are made equal.

If you have a 7kW power supply and $20,000, you can do what a chap called Jeremi Gosney did, and combine 25 off-the-shelf graphics cards into a cracking behemoth.

This can carry out some kinds of password cracking operations between thousands and hundreds of thousands of times faster than my Mac.

And if you had room for 200 PS3s, you could have created a fake digital certificate that would have let you authenticate yourself as any website in the world, until the offending certificate was cancelled, at any rate.

What to do?

Brien Posey showed us something useful: that a decent encryption system with a strong passphrase-to-key conversion function, like the PBKDF2 of Mrs Posey’s WinZip, can help to make even an eight character password safe.

So a lot depends on the willingness of the company that validates your password not to cut security corners in implementation.

But when it comes to websites, you may not be able to work out what algorithms are being used for password verification, so you often simply have no idea at all just how resistant your provider is to cracking attacks.

You have to assume the worst – that a determined adversary might be able to scan for passwords hundreds of thousands or millions of times faster than you thought feasible.

With that in mind, I’ll go back, admittedly without much science, to my personal guidelines for passwords: aim for 14 characters, switching as arbitrarily as you can between UPPER, lower, d1g1t5 and \/\/@ckies.)

T4Lf&unt,StSe!