Hardware Assisted Brute Force Attacks: Still For Dummies

blog
41

Mike has a good point earlier on about adding a 30 second lock out period, it shifts responsibility away from the user to the designer. Honestly, what good security designer would allow brute force attacks to even be possible?

Let’s assume you have a web application. Let’s also assume that you log all login attempts. Why not implement a simple method that prevents any user from trying to log in more than once every 2-3 seconds (if (time = lastLoginAttemptTimeStamp+3) /* allow login / else / error page */), about the delay you’d expect an online refresh to take and nothing the average user would get pissy about because they would never even notice. However, crackers would notice because even a distributed password cracking attempt would be slowed to a crawl with every login attempt on a user being checked synchronized to a moderated login schedule.

The point is: it is up to security designers to make sure that brute force is a waste of time no matter how short or long the required password length is. The password is an authentication token, not the length and measure of all computer security.

42

I think they mention 8 char passwords because of NTLM limits. It’s been many years since I last looked at NTLM, but I remember they truncated your password and split it into two pieces (2x 8 chars), so it doesn’t matter how complicated and long a password you use, it will still be easy to break.

The hardware assisted cracker may therefore simply reduce the upper bound for the time required to break and make cracking more convenient.

43

My passphrase:

“I’ve ridden in a 1998 Ford Contour with Wumpus on front”

http://www.codinghorror.com/blog/archives/000515.html

44

@james

Brute force is already impractical against most webapps:

First, bandwidth already limits the number of attempts per second, and any production service should take your advice at the very minimum.

Further, it’s the server that takes the load in this case, so unless you were planning on breaking into google hq so you can install a couple gpu’s…

Finally, all of this still only targets one account at a time. Such an approach isn’t very efficient, unless the attacker has a particular target in mind.

Presuming of course that the app doesn’t simply crash from the load :stuck_out_tongue:

The vulnerability for most sites is what happens when the password database somehow is compromised. It happens all the time. And if the designer didn’t take that properly into account, then the database might be vulnerable to all sorts of attacks.

Granted that any particular user can take steps to lower his exposure (presumably his account is just as compromised as the password database itself), but the fact is that most people reuse passwords. But just because they’re gonna be bit by some site’s poor practices doesn’t mean they should be bit by your site’s poor practices.

When my password database is stolen, I want to be the guy who can respond with a press release including my code together with an audit that states that my clients should consider changing their passwords some time in the next few years.

45

Some above have mentioned using lockout periods for login retries, or 2-3, or 30 seconds. Why not use some sort of binary backoff (a la collision avoidance)? No maximum tries before lockout, but brute forcing a login becomes infeasable.

Also, all my logins are perl one liners. It’s hard to get a higher entropy than that!

46

Quick points:

Eam It is easy for a user to make a password 20x better. 20 26, which means you only have to add 1 random lowercase letter to a password to do that. Or, 20 2^5 which means you need less than 5 extra bits of entropy, which is going to be only 3-4 letters (worstcase) in a passphrase.

Mike What Eam said - never use a custom hash function. Use an off the shelf one. (Look up Schneier’s law. This applies to hash functions as much as crypto algorithms. Anything custom is almost certainly going to be much worse than a published, peer-reviewed and well-attacked algorithm.)

Jeff, I don’t know of an existing tool to do this, but…

Take a good size corpus of English text and generate a Markov model of it.

As you create the model, if you come across a word that matches a name in your Cracker’s Name Database (e.g. “John” or “Smith”), or just a word starting with a capital letter that is not at the beginning of a sentence, tag it somehow in the model with “name”. Do the same for numbers - tag them so you can easily tell they’re a number. Dates would be good too. If you can grab “January 15 2005” as a single token and mark it as a date, brilliant! Ditto times.

Create indices for your Markov model for previous word and order of probability. You want to be able to look up by previous word in O(1), and by order of probability in O(1).

That can be done beforehand.

Then, to generate passphrases, go through all one-word passphrases, starting with the word most likely to appear at the start of a sentence, and finishing when you get to the word least likely to appear at the start of a sentence (but still non-zero possibility) Then two-word passphrases; Start with the most common word, and it’s most common successor, etc…

When you hit a “name” token, first try that name, but then try all the other names in your Cracker’s Name Database. Ditto numbers - try the number first, and then numbers “close to” that number, and/or round numbers near that number. Ditto dates.

Add leet. Try the, say, 10 most common leet substitutions on words. Say for an average 4 letter word, 2 of those could be leetable, giving you 4 possible combinations. Try the, say, 16 most likely leet substitutions for each word? Then ALL-UPPER, CaMeL1, cAmEl2 and Initial Caps.

You could also try replacing_spaces_with_underscores and removingspacesaltogether.

16 leet substitions + all those gives me an extra 1024 combinations per word to try, but meh. There aren’t that many words.

Let’s say we’ve got a vocabulary of 10,000 words. How many of them are valid (p 0.001?) at a given point? Um - I’m going to guess at 1,000 here. I’ve no idea how accurate that might be.

So, that’s:

1,000,000 1-word phrases (negligible)
1,000,000,000 2-word phrases (5 seconds)
1,000,000,000,000 3-word phrases. (5000 seconds ~ 1.4 hours)
1,000,000,000,000,000 4-word phrases (5,000,000 seconds ~ 57 days)

Hmmm…and cracking your 6-letter passphrase will take a million times longer than that.

OK, that’s starting to take a long time. Maybe moving on to longer passphrases before exhausting all shorter ones might help. Or maybe there are less than 1000 valid words at any given point. But that’s the idea. But it will certainly get your passphrase before a brute-force alphanumeric would. 63^28 (~10^50) tests by my calculation, using upper, lower, numbers and space, compared to 10^24 tests for mine.

47

How about ‘malformed’ passphrases?
“1 drive a l998 Ford Cotnour!”

48

All fine and good until someone finds a weakness in the hash and then everything cracks in seconds.

Security is like a wall - only as good as the weakest point, be that your password or the hash or the hardware to crack it on.

And just like walls, eventually all security falls.

And hey, if someone really wanted to see what is on your computer, it would probably be easier to add in a cheap keylogger behind the computer where the keyboard plugs in. Not a lot of security there.

And hey, if the person has a wireless keyboard, why even bother with that!

49

nobody seems to have realized that besides ASCII there are international caracters that crackers dont take into account. In Spain it’s quite common to use our beloved “enye” (can’t write it from this iphone, dammit) that for example is used on our country’ local name. And I guess other special letters are used in countries such the escandinavian ones… not a bad practice IMHO.

Great, great blog Jeff. Congrats!

50

What about using CAPTCHAs beside the password? with CAPTCHAs brute force attacks would take a very long time (assuming you have a very efficient OCR application).

51

As some have mentioned, you might use markov models to reduce the search space for passphrases and really the only ultimately secure way to avoid that is to add real entropy. I have combined both of those to automatically create secure passwords. I generate random words using a markov model of the target language and calculate the entropy of the resulting word(s). This way I know the search space size for even the attacker with perfect knowledge. Thanks to the language model the words are reasonably easy to memorize and not too long. If I control the hashing then as already has been mentioned, always use a random salt with the length of the IV of the hash and raise the cost of the hash function to reduce brute force speed. (I use PBKDF2 for this, see RFC 2898) For the markov chain word generation example see Yould, allthough this is dead simple to implement yourself, you just need a sizeable corpus of text to get good results.

52

It’s one thing to generate millions of passwords per second. Quite another, time wise, to enter them into the program requesting the password. Or comparing (string compare?) the generated hash with the password hash.

If we generate a list of hashes, do we sort the generated list and do a binary search? If not sorted, we’ll have to do a linear search. There goes the timing benchmark.

Are we almost done hashing :slight_smile: this out?

53

The reason we’re not seeing any (or lots of) tools to crack passphrases is the extremely simple: you can’t use them that many places where a brute-force attack would apply, and furthermore, where brute-force attacks do apply they’re typically quite optimized.

If the world was using passphrases you’d see tools to crack those. Just like you’re seeing dictionary attacks on passwords now.

@Charles Darke: WinXP and below using default passwords will split them into 2 groups of 7 characters. Not 8.

Kind regards
Fake

54

Karellen, your rough time estimates are missing a crucial factor: the search will pick the most likely words first in each position.

‘I’ and ‘a’ are so common that they’ll be among the first words it tries, especially at the start of the sentence. The search will probably be significantly faster than your worst-case time.

55

Nobody has mentioned Enhanced Authorization/Two Factor, authorization. You probably already see it on most of your banking websites. The site recognizes a single PC as your primary machine, and if you access from a different machine it asks you a personal question, like mothers maiden name. With that additional level of security brute force attacks are irrelevant.

56

I often train, on a very basic level, older people (60+) to use a computer.

“If it’s stored on a computer, and someone wants it badly enough, they are going to get it.”

That’s the phrase I use when a novice computer user asks me if they should store sensitive information on their home computer.

I always follow up with a brief lecture on pass phrases and the importance of splitting a word with a number(s) if the host limits the number of characters a password can contain.

I also remind them that they are “small potatoes,” and to not be too frightened by using services like Ebay or any Bank-from-home as long as they use caution.

Is this, roughly, a good way to go about things?

I really enjoy this blog because it addresses a lot of usability issues that I encounter when dealing with older people. So thanks, Jeff, for helping to help old people!

57

The problem with passphrases is generally they are usually succeptible to dictionary attacks. The problem with 14 character passwords is no one can remember them, and everything has different standards so you can’t meet them all with one password. One suggestion is to have a good base password - like f0Rk$ - then add 5 letters of the place requiring the password, if it is amazon.com add amazo - password is now f0Rk$amazo.

If you always use the same firefox instance, there is an extension that generates a random password within the limits of the website, and remembers it. That way you get an extremly complex password you don’t have to remember. Set a good master password, and even local access won’t give you all the passwords free. The only problem is sites that firefox won’t store passwords for (like wellsfargo.com) or sites that use alternate passwords (like hsbc.com point click passwords).

Since you don’t even know your password, to protect against loss, either

  • store a backup of these passwords in a truecrypt volume somewhere else (use another ff extention - password exporter) OR
  • don’t worry about it - if you lose your PW just do the PW reset to have it sent to your email.

Which brings up another point, make certain you set a unique password for your email. Don’t store it locally, and make sure your provider locks out attempts after a few failed password attempts. If someone gets into your email, you are sunk.

58

I agree with Ira - any mass market end user security can easily be broken by someone who wants it badly enough. It’s like that old BIOS password, or nowadays Windows login passwords: People feel it protects their PC, but all you needed was a screwdriver, or nowadays even only a bootcd and you could get to the data within seconds. And just as easily you could beat the vast amount of security systems today with a tiny little keylogger. Bam, there goes your super secure password.

His (?) other point is very valid too: IS someone going to invest time and effort into trying to crack your password ? The answer is likely going to be “no”, and instead of discussing pass phrases and numbers in passwords, I feel it would be much more effective to teach people how to not become a target: Don’t put your email address on shady web pages. Don’t click on spam. Don’t fall for those phishing sites.

When Granny walks through a bad part of the town at night after withdrawing money, all the security and care when choosing a combination for her bank password won’t help her.

Practically all the getting screwed people experience works via social engineer or (physical!) brute force. I doubt there has been a reasonable number of people been screwed over because someone brute forced their 5 letter passwords, and I doubt there ever will be. It’s simply not the most effective way, because despite all flaws, even bad passwords are still way harder to crack than sending out phishing emails to a million morons. Passwords are not and never have been the weak link in security.

59

also, if you get the password wrong 3 times you get permanently locked out of the system or until an admin unlocks the account. surely that makes any of these attempts futile?

60

The numbers listed are the absolute worse case right? So statistically, the time to crack the password is actually going to be roughly half the time listed on average.

It’s kind of a meaningless distinction though, as 5,000 years to crack a password is not really any less safe than a password that takes 10,000 years to break – the MTBF of the equipment is going to be the limiting factor after some point.