passphrases - lowercase and dictionary words

Question

Amid all the discussion about password length vs. complexity (summarized by the famous xkcd strip and the followup dicussion) I am trying to make up my mind about passphrases made up with dictionnary words.

I understand the various calculations for brute force attacks -- would you know of a reasonable study about passphrases which would be made from dictionnary words?

I was namely wondering about a policy with a minimal length of, say, 13 characters - all lowercase. I expect to end up with phrases like volleyballisfantastic. This is 3 words. If the phrase is in English or French, they would average at about 4 words.

Since one of the reasons to move to a passphrase would be to go away on some systems from throttling mechanisms (lock the account for 10 min after a failed login or exponentially change the time in between login prompts), I wonder if dictionnary attacks would not be way more successful on such passphrases.

Thanks for the thoughts or pointers to existing studies (I googled around and what I found are discussions about pure bruteforce).

Answer 1

I would say that this isn't strictly a dictionary attack, since you're not testing words in a dictionary, but strings of words. It's really a brute force with a different "character" set. That lets you use regular entropy calculations.

If the attacker brute forces the password it as if it were a string of lower case characters, then it's 13 long and each token is one of 26 choices. That's 61 bits of entropy.

If the attacker brute forces it as if it were a series of lower case words from the english dice ware list, then it's 4 long, 7776 choices, so 51 bits of entropy. Or, if the attacker brute forces it as lower case words from the OED, 4 long, 181,000 choices, which gives you 70 bits.

Since most people would not use obscure words, in your example, you'll be closer to 50 bits than 60, so a dictionary attack would give better results. 13 characters of random letters would be theoretically much stronger than four words.

(Non-theoreticaly, of course, a password rule requiring 13 characters of gibberish just means post-it notes on monitors.)

Answer 2

Since most people would not use obscure words, in your example, you'll be closer to 50 bits than 60, so a dictionary attack would give better results. 13 characters of random letters would be theoretically much stronger than four words.

@Graham,

It's true that most people don't use obscure words; however, wouldn't a simple use of the numerical substitution for a single letter be enough to then bump up the complexity? As an example, instead of houseonfire you'd write h0useonfire. It'd still be easy to remember and the dictionary would have to include the 'leet speak' in order to more effectively brute-force it.

Would this be accurate, do you think?

Answer 3

If you have a look through our question on that XKCD strip you will see a lot of discussion on the calculation of entropy, which is all that is important here, because a concatenation of 3 or 4 words requires either a normal brute force procedure, or a brute force using concatenations of dictionary words.

The problem you get into is this:

A standard brute force will break the passphrase. The only question is time. And if you make that time big enough, then you can treat the passphrase as unbreakable by this method.

A dictionary based brute force attack will only break the passphrase if all the words in the passphrase exist in the dictionary used, so you already start off with an uncertainty in outcome. Then you need to plan for every word in the dictionary in positions 1, 2, 3 and 4 in your passphrase (assuming you restrict to 4 words) and possibly all 4 positions.

Of course, a good throttling mechanism will make all online brute force attacks impossible, so all you need is a passphrase "good enough" to force an offline attack to take longer than your safety period (which could be twice your password expiry time, or 5 times, or whatever factor you require)

Answer 4

You should always implement some form of throttling on login attempts — even with the random words trick, it's not really practical for many people to memorize a passphrase with enough entropy to be secure against an unthrottled dictionary attack, especially if they need a separate one for each site they use.

(There are ways around that on the client side, like using a secure password wallet to store the per-site passwords, with a single strong passphrase to access the wallet, but for various reason they haven't caught on widely yet.)

It's also worth noting that a determined attacker can DOS your site just fine even without login throttling. The throttling, if carelessly implemented, just makes a particular kind of targeted DOS attack easier. To mitigate this effect, I'd suggest at least the following steps:

• Set up a fairly low per-IP login limit, as well as a higher per-site one. This means that an attacker must must employ multiple computers with different IP addresses to effectively DOS your site, which, while certainly possible, still presents a speed bump. (You may or may not also want a per-user limit; it makes sense if you expect dictionary attacks targeted at single users, but in many cases a typical attacker would be just as happy with the password to any account, in which case their best strategy is to attack them all in parallel.)

• When the limit is hit, log it. If it keeps being hit repeatedly, alert the site admins — whether it's a DOS attempt or a genuine dictionary attack, they'll want to know about it.

• Make sure you provide an alternative way for users to contact the admins if they can't log in due to throttling.

• Last but not least, require an anti-CSRF token on all login attempts. You'll want to do this anyway to protect against login CSRF, but as a useful side effect, it also stops certain kinds of simplistic distributed attacks (such as crafting a direct link to the login script and including it as an image URL in widely read forum posts).

Ultimately, IMO password length and form requirements are a red herring, at least from the site admin's viewpoint: if you let your users choose their own password, some of them will choose weak ones no matter what. If you require alphanumeric passwords with punctuation, some users will choose "abc&123"; if you require four-word phrases, they'll choose "I love my mom".

You can either accept that and find ways to live with it, or, if you can't or won't do that, take the choice away from your users and generate random passwords for them. In which case I'd very strongly suggest using the "four (or more) common words" method, since it yields much more memorable passwords for a given amount of entropy than, say, picking random characters or syllables.