Developer, tinkerer, thinker

Why Bruce Schneier is wrong about passwords

March 11th, 2014

Bruce Schneier had an interesting article about passwords and password hash cracking last week.

His characterisation of how password cracking can vacuum up relevant data and add it to a dictionary is excellent.

I hold Bruce Schneier in high regard, both for his technical work (I renewed Applied Cryptography about 6 times from our University library) and his sensible campaigning on security-related issues. However, there were a few points where I don’t think his analysis holds up.

Firstly, he criticises the xkcd password scheme, on the basis that crackers know about it and will search for multiple joined dictionary words. With the analysis below, we can see that this is not actually a problem.

Secondly, there are some issues with the scheme he describes for phrase-based passwords (the Schneier scheme). His description has a terrible mistake from a security usability point of view, which I hope he will fix. For the same entropy, it is harder to remember and type than the xkcd scheme. And the passwords it generates are probably of lower entropy than we might estimate, although attacking that is probably still infeasible.

Why the xkcd scheme works

This is why the oft-cited XKCD scheme for generating passwords — string together individual words like “correct horse battery staple” — is no longer good advice. The password crackers are on to this trick.

The issue here is that joining together several random words is not a “trick” for generating good passwords; it is a straightforward way to ensure there is a measurably safe amount of entropy in the password. By entropy, we mean the information content, as in the number of bits needed to identify this password if we had a complete list of possible passwords. And this is the same argument as for any security system that doesn’t use obscurity: the strength of the security comes from the amount of entropy in the keys (i.e. the output of the random number generators).

Because each word is chosen independently and randomly, the entropy of the password is equal to the entropy of the word list (log2 of the length of the word list) multiplied by the number of words.

If I run grep '^[a-z]\{4,7\}[a-rt-z]$' /usr/share/dict/words | wc I get 22350 words that are between 5 and 8 letters long, that aren’t plurals. If I use grep '^[a-z]\{4,7\}[a-rt-z]$' /usr/share/dict/words | shuf --random-source /opt/google/chrome/product_logo_128.png -n10 to quickly check these words are sensible (and I have nothing up my sleeve), the first ten I got were: nonzero sprouted vamoosed select jacket shaped chowing sprayed unwisest abashed. It’s not Finnegan’s Wake; these are reasonable words.

Okay, so we got 22350 words, how much entropy is that? Rounding down in case we need to trim the word list, we’ll call it log2(16384), or 14 bits per word. Four words is then 56 bits.

Is 56 bits enough? Well, Bruce quotes one cracker as being able to check 8 million passwords per second, and that this could be parallelized across multiple machines and run for months. 8 million is 23 bits, a thousand machines is 10 bits, so a thousand machines for a month (2592000 seconds, ~21 bits) can enumerate a space of about 54 bits.

That’s uncomfortably close; however, this assumes a very well-motivated and resourced attacker. If the passwords have even been salted, then this is almost certainly too much effort for one user’s website password — it would cost about 0.1*24*30*1000 = $72,000 to rent the required machines from Amazon. If the site owner has used bcrypt or similar, you are safe here.

If you are worried or need more security (e.g. for your primary e-mail account), adding one or two more words is enough to be safe against any feasible cracking attempt (of course, even at the four word mark, investing tens of thousand dollars in social engineering and/or breaking laws is more likely.)

Issues with the Schneier scheme

Choose your own sentence — something personal.

This little piggy went to market

Firstly, in Bruce’s written description, he says you should use a personally memorable sentence. He isn’t explicit that it should be made up by you, and two of his sentences are quotations (and famous ones at that.) This is a terrible idea, because crackers can and will index famous quotations to use them in scanning programs (a complete wikiquote dump is only 70MB compressed, and is going to have most of the quotes you think up).

This is mostly a problem in the presentation though; the described scheme is much better.

Memory vs entropy

The problem the xkcd cartoon highlighted is that these kind of password generation tricks with substitutions and special characters are harder for humans to remember than just a string of words, for a given information content.

In comparing the schemes, I would therefore ignore case and symbol scattering — they are hard to remember, most of the examples given do not vary case or use much punctuation, and if you are asking the user to remember special punctuation and substitutions on top of the base password, well, that can be used on the xkcd scheme just as easily.

So the overall scheme reduces to an English sentence (lower entropy than random words, both because of grammar, and because a person made it up and people are bad at random), and you throw away most of the characters, keeping just the starting ones. I don’t believe a sentence of about 8-10 words, keeping only the first letter of most words, can be more secure. Let’s test.

zxcvbn is a great tool made by dropbox to test password strength. It splits the password into sections and makes an entropy estimate for each section using a variety of entropy estimators (dictionaries of words and names, dates, repeated characters, brute force, and even leetspeak and patterns on the keyboard.) Let’s try it on the examples Bruce gives:

Password Entropy
WIw7mstmsritt 69
uTVMTPw55 59
utvmtpwstillsecure 51
Ltimeagoinagfaaa 46
Wowdoestcst 43
tlpWENT2m 40

That’s quite a range. The longer sentences, and the ones with numbers, do better, and arguably have more entropy than the xkcd scheme (although I have some theoretical reservations below). However, many of them do worse than the xkcd scheme. They also are harder to remember exactly, and more awkward to type than a few complete words. This is not a good scheme, and only achieves good security through hard to remember punctuation.

Low entropy content

Although the zxcvbvn meter is using bruteforce to estimate most of these passwords, the actual entropy content is likely lower for two reasons: English grammar, and poor human randomness.

Because we are taking a real sentence, rather than a set of random words, we have the redundancy of grammar, which could easily consume half of our entropy (consider, could you fill in the blanks in this sentence: “I _ walking _ dog _ it _ raining”?)

Also, and Bruce makes this point, a cracker will gather any relevant information like pets’ names, important dates, events attended, affiliations, and so on. All of these will give clues to the sentence the user might select.

However, even given the lower theoretical entropy content, a cracker also needs to generate candidate passwords very fast, so it is unlikely either of these is too much of a problem.

Passwords through obscurity

The overall problem with recommendations like Bruce’s (and the GRC Haystack method) is that they basically rely on the cracker not knowing the scheme you use — and this reliance is dangerous. Even if you use a different password for every site, are you going to use a different punctuation/padding scheme? Security through obscurity is, at best, only temporary.

In contrast, the xkcd scheme is simple to remember, and is still secure assuming the attacker knows how you generate your passwords. A quick:

if [ $(grep '^[a-z]\{4,7\}[a-rt-z]$' /usr/share/dict/words | wc -w) -lt 16384 ]; then echo "Failed to find enough words"; else grep '^[a-z]\{4,7\}[a-rt-z]$' /usr/share/dict/words | shuf --random-source=/dev/urandom -n4; fi

is generally enough.