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

Filed Under: Cryptography, Featured

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 (28).

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!

, , ,

You might like

18 Responses to Anatomy of a brute force attack - how important is password complexity?

  1. To crack an online password, you cannot approach 1/2 of 1% of the attempt rate used in the theoretical brute force examples you use. If it would take a fast array of machines several hours to crack, it would take years online. By then the target would more than likely have moved.

    • Paul Ducklin · 250 days ago

      Indeed. Online logins are usually rate-lmited - just like mobile phone SIMs give you only three goes at your PIN before they lock.

      Sometimes they are not, as happened to Twitter in days of old, before it got serious about security, and a Twitter staffer's admin password was cracked. (Admittedly, this was a dictionary attack, and a poor password choice.)

      http://nakedsecurity.sophos.com/2009/01/14/breaki...

      But this is academic if the password database itself is breached and exfiltrated.

      That's rather depressingly common, and it's what happened in the Philips example I mentioned above. The password database contained hashed passwords, so an attack was still required to work out each password. But with the password hashes on your own computer, *you* get to choose how fast your cracker runs, and how many CPU cores (or PCs in your botnet) you throw at the task.

  2. wolsonjr · 250 days ago

    Actually it was the early 19th. I was just reading it last week from Gutenberg. Still a great magazine and just shows how nothing changes.

    • Paul Ducklin · 250 days ago

      My Oxford Dictionary of American English gives the etymology of "curate's egg," explicitly dating the article to 1895. (The magzine in which it appeared, Punch, didn't appear until 1841, and the cartoon's author, George du Maurier, wasn't born until 1834.)

  3. Karen G · 250 days ago

    I use KeePass all the time. It allows me to make a randomly generated password (I go with 16 characters) and I can add upper case, lower case, numbers, and some special characters as well. I store all my passwords on KeePass, and just have one random password to remember for my master password. Makes remembering easy, and all of my passwords are very hard to crack.

    If you MUST use something simpler, Steve Gibson of grc.com did something called password haystacks. Basically, you have a simpler password, but you pad it with some "random" pattern that you can remember. A long simpler password (NOT DICTIONARY) with some punctuation or special character padding, is harder to crack than a simple 8 character password.

  4. I have a 16 character password that is a cinch to remember. It's random, contains capitals, numeric, and special characters. More than likely immune to a "brute force" attack. The reason it's easily remembered is that it's a pass-phrase. As a former IT Security Officer, we always recommended our users build passwords from a pass-phrase..

    A quick brown fox jumped over the lazy dog 4 times

    AQbfJ!oTLd4T?

    Just a bit of helpful info

  5. Techno_M · 249 days ago

    Experience has led me to settle on 15 characters, a combination of upper and lower case letters and numbers, excluding letters and numbers that look similar (0 and O, 1 and I etc.)

    This is because 15 characters is often the maximum on websites, many also do not allow special characters. I got fed up of making several attempts to find out what the rules are.

    Also, if a website uses the system where you only enter specific digits ("Enter the 1st, 8th and 12th character from your password") the above characters are easy to read from my password manager.

  6. Andre Marcil · 249 days ago

    Actually before choosing a password, you should be asking yourself the same questions as in real Life...

    Is this really important enough that it needs to be protected by a password ?

    + Password for Web site...

    What will happen if someone steals the password for this site ?

    +++ But mostly the only question you should really answer with a DEFINITE NO is...

    Do I use the same password everywhere ? ? ?

  7. protectvietworkers · 248 days ago

    I am just curious: If you are allowed only a few times to enter passwords before lockout, then what do you do?

    • Paul Ducklin · 248 days ago

      As I suggested above in reply to @Robin Blinn, a brute force attack can't be done against a website that prevents you guessing passwords over and over again.

      (It can lock you out completely, or it can simply slow you down by making you wait several seconds or minutes to try again, so that you can try no more than, say, 1000s of passwords per day, instead of 1,000,000s every second.)

      But in many password cracking attacks, the hackers have already got hold of the password database. Even if they still need to crack the hashes stored in the database, there is no web server blocking their way or slowing them down.

      They can crack the database directly, at any speed they want.

      Of course, a web server shouldn't let the hackers steal its password database in the first place. But in case it happens, you may as well choose something long and "mixed up" for your password, to avoid making it easier for the crooks.

  8. Sylvester · 248 days ago

    I have a question. I understand that we would need strong passwords in the case the hackers get a hold of the password database of websites and try to crack it.

    I just read elsewhere in this site about how powerful computers can find out passwords using brute force surprisingly soon. And like you mentioned in the case of Philips, the hackers did manage to find out the passwords after getting the password database, right?

    Do you think some of the strong passwords in the database could have managed to avoid getting cracked? I don't know much about tech stuff. But my impression is this: In the case of a brute attack after the password database is acquired by the hackers, they will find out my password in the end no matter how strong my password is since they can use powerful machines to do the brute attack. Is my impression right or wrong? I got the impression judging by the thousands of passwords that hackers have found out through brute force over the years. I hope my impression is wrong. If it's wrong, why is it wrong? Thanks a lot in advance! :D

    • Deramin · 247 days ago

      Given time, all password hashes will be hacked. So the idea is not to have a password that's impossible to break once stolen, but rather a password that buys you time to change your password between the time the database was stolen, the time it takes the company to get around to disclosing it, and the time it takes you to get around to changing it. I assume it will take the hacked company between 4-6 months to tell me anything and fix there systems, and I assume I'll be equally useless for at least another month after that. So I need my passwords to be sufficiently complex to survive 7 months of attack.

      • Sylvester · 246 days ago

        Hmm... That's a good point. So my long complex passwords genuinely are useful! Thanks for answering my question :D

  9. Shane · 247 days ago

    I'm surprised the Rainbow Table concept was not mentioned.

    If anyone needed overwhelming proof that 8 characters are not enough, a demonstration of Ophcrack breaking 14 character non-dictionary random characters passwords in just minutes ought to do it!

    Yes a password such as qJzc.Dj}O8x:%U can be broken in minutes, thanks to pre-computed password-hash databases that are available.

    • Steely · 247 days ago

      Someone please correct me if I am wrong, but I believe that properly salting the password hash will defeat current rainbow tables. Wikipedia (for what it's worth), in discussing 48 bit and 128 bit salt values, says "These larger salt values make precomputation attacks for almost any length of password infeasible against these systems for the foreseeable future."

      Otherwise, yeah, they can crack passwords with amazing speed.

    • Paul Ducklin · 247 days ago

      I declined to mention rainbow tables on purpose - because then I would have had to spend time explaining why they often aren't relevant.

      Rainbow tables are a space/time tradeoff for a specific hash algorithm run *from a set of specific starting conditions.* If you salt your hash (i.e. mix some randomly-chosen bytes into it at the start), you need a rainbow table *for each salt* for each password. So only with unsalted hashes are rainbow tables practicable.

      If you use an 8-byte salt, for example, you would need 2^64 different rainbow tables, one for each possible salt. (Which is why you should salt your password hashes, like UNIX has been doing since the 1970s.)

      I am going to guess that the Ophcrack wizadry you saw was an old-school Microsoft LANMAN password being cracked. Those were implemented, IIRC, by splitting one 14-byte bit string into two 7-byte halves and hashing each half separately. So really you watched two 7-character passwords getting cracked.

      Having said that, 8-character NTLM passwords are nowhere near enough either - the $20,000 "cracking rig" shown above can churn through all of those in six hours. But not minutes.

      That's because NTLM hashes are a straight, unsalted, single-iteration hash using MD4. That cracking rig can compute 400 thousand million MD4s per second! (Ironically, although rainbow tables would work here, they aren't needed...it's faster just to compute every password's hash "from scratch," the cracker is so quick.)

      Salt your passwords and use PBKDF2, bcrypt or scrypt properly...then rainbow tables won't work and even Ophcrack won't be cracking a 14-character password in just minutes...

  10. thecoppicer · 247 days ago

    my password's bigger/better/prettier than yours?

  11. panzerxiii · 247 days ago

    http://xkcd.com/936/

    XKCD kind of sums up this whole issue.

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