Is "the oft-cited XKCD scheme [...] no longer good advice"?

Question

I was stumbling around and happened onto this essay by Bruce Schneier claiming that the XKCD password scheme was effectively dead.

Modern password crackers combine different words from their dictionaries: [...]

This is why the oft-cited XKCD scheme for generating passwords -- string together individual words like "correcthorsebatterystaple" -- is no longer good advice. The password crackers are on to this trick.

The attacker will feed any personal information he has access to about the password creator into the password crackers. A good password cracker will test names and addresses from the address book, meaningful dates, and any other personal information it has. [...] if your program ever stored it in memory, this process will grab it.

His contention seems to be that because it's known that people might construct their passwords in such a way that it makes it amenable to attack, but it seems like the strength lies purely in the power of exponents. I assume he's alluding to people not choosing the words truly randomly, which perhaps isn't totally disingenuous, as I've rerolled a couple times to get something that isn't all adverbs and adjectives. However, I assume that lowering the entropy by a factor of 2-10 isn't really significant (if the word list is doubled to 4000, not that hard, the loss is more than recovered).

The other quip about "if your program ever stored it in memory" is a bit disconcerting though...aren't all passwords stored in memory at one time or another? That seems a bit overbroad; what is he actually referring to?

Answer 1

The Holy War

I think you will find that the correct way to generate passwords could start a holy war where each group thinks the other is making a very simple mathematical mistakes or missing the point. If you get 10 computer security professionals in a room and ask them how to come up with good passwords you will get 11 different answers.

The Misunderstanding

One of the many reasons there is no consistent advice about passwords is it all comes down to an issue of threat modeling. What exactly are you trying to defend against?

For example: are you trying to protect against an attacker who is specifically targeting you and knows your system for generating passwords? Or are you just one of millions of users in some leaked database? Are you defending against GPU based password cracking or just a weak web server? Are you on a host infected with malware[1]?

I think you should assume the attacker knows your exact method of generating passwords and is just targeting you.[2] The xkcd comic assumes in both examples that all the details of the generation are known.

The Math

The mathematics in the xkcd comic is correct, and it's not going to change.

For passwords I need to type and remember I use a python script that generates xkcd style passwords that are truly random. I have a dictionary of 2^11 (2048) common, easy to spell, English words. I could give the full source code and a copy of my list of words to an attacker, there are still going to be 2^44 possible passwords.

As the comic says:

1000 Guesses / Sec Plausible attack on a weak remote web service. Yes, cracking a stolen hash is faster, but it's not what the average user should worry about.

That strikes a nice balance between easy to remember and difficult to crack.

What if we tried more power?

Sure 2^44 is ok, but GPU cracking is fast, and it's only going to get faster. Hashcat could crack a weak hash[3] of that size in a number of days, not years. Also, I have hundreds of passwords to remember. Even xkcd style it gets hard after a few.

This is where password managers come in, I like KeePass but there are many others that are basically the same. Then you can generate just one longer xkcd pass-phrase that you can memorize (say 10 words). Then you create a unique 128-bit truly random password for each account (hex or base 64 are good). 128-bits is going to be strong enough for a long time. If you want to be paranoid go larger, it's no extra work to generate 256-bit of hex passwords.

---

[1] This is where the memory thing comes in, if you're on a compromised host you have lost. It doesn't matter if you type it or use a program like KeePass to copy and paste it if an attacker can key-log / read memory.

[2] Rather than the weaker (but more likely) assumption that the attacker has just torrented a dictionary called "Top Passw0rdz 4realz 111!".

[3] Sure we should all be using PBKDF2, etc... but lots of sites are still on SHA1. (and they are the good ones)

Answer 2

Schneier writes this:

This is why the oft-cited XKCD scheme for generating passwords -- string together individual words like "correcthorsebatterystaple" -- is no longer good advice. The password crackers are on to this trick.

but the key to understanding what he is really after is a little further in his essay:

There's still one scheme that works. Back in 2008, I described the "Schneier scheme"

so that's it. Ole' Bruce wants to assert that his scheme is the One and Only, the best, the winner, the ultimate scheme. Therefore, he needs to say disparaging things about the "competitors", regardless of whether such assertions are scientifically sound or not.

In this case, it has always been assumed that the password generation method is known to the attacker. That's the whole point of entropy computations; see the analysis. That attackers are "on to this trick" changes nothing at all (when an attacker knows the password generation method, the entropy computation describes exactly the password strength; when the attacker is incompetent and does not know the password generation method, the password strength is only higher, by an amount which is nigh impossible to quantify).

The quip about "passwords in memory" is just more incoherent ramblings. Passwords necessarily go to RAM at some point, whether you type them or copy-paste them from a password safe, or anything similar.

My guess is that Bruce was drunk.

Update Schneier was specifically asked to comment about his passphrase condemnation in a Reddit AMA (via archive.org, original link) that took place August 2, 2016. He continued to advocate for his password creation system as a superior alternative to random word passphrases. Schneier did say his scheme "gives you more entropy per memorizable character than other methods" which is true when compared to characters making up words. But this is also irrelevant when a system relies on memorizing words rather than characters, and you're allowed to combine enough words to generate adequate 'entropy' for your passphrase as a whole.

Answer 3

[Disclosure: I work for AgileBits, the makers of 1Password]

One of the reasons why I advocated for an XKCD-like scheme (before it got called that) in Toward Better Master Passwords back in 2011 is precisely because its strength does not rely on the attacker knowing what scheme you used. If I may quote myself

The great thing about Diceware is that we know exactly how secure it is even assuming that the attacker knows the system used. The security comes from the genuine randomness of rolling the dice. Using four or five words should be sufficient against the plausible attacks over the next few years given observed speed of password crackers [against 1Password Master Password]

What the XKCD comic does not effectively communicate is that the selection of words must be (uniformly) random. If you ask humans to pick words at random, you get a heavy bias for concrete nouns. Such biases can and will be exploited.

How much strength you want

In a perfect world we would want to strength of our password to be as strong as the keys we are protecting with it. Say 128 bits. But despite these techniques, humans aren't going to achieve that. So let's look realistically at attacks and what we can have our puny little brains do.

With the original Diceware word list of 7776 entries, you get approximately 12.9 bits per word that you use. So if you want at least 64 bits for your password, then five words will do it.

Guessing passwords is slower than guessing keys

In this section I arrive at a very rough back of the envelope estimate that for a constant amount of dollars it is 2^13 times slower to test a password than it is to test an AES key.

Note that testing a password is a lot slower than testing a key. If the right sorts of password hashing schemes are used, it is possible to keep most attackers down to under 100000 guesses per second. So while we might never want to use 50 bit keys, using 50 bit passwords might still make sense.

If we aren't going to limit ourselves to rolling dice as in Arnold Reinhold's original Diceware scheme from 1995, then we can use a longer list of words. The Strong Password Generator in 1Password for Windows uses a list of 17679 English words between 4 and 8 letters inclusive (stripped of taboo words and words that involve an apostrophe or hyphens). This gives about 14 bits per word. So four of these gives you 56 bits, five gives you 70.

Again, you do need to pay attention to cracking speeds. Deep Crack back in 1997 was able to run 92 billion DES tests per second. Assuming that a high end specialized PC can perform one million guesses per second against a reasonably well hashed password could do 1 million guesses per second, then passwords today are about 16 bits harder to crack than DES keys were in 1997.

So let's look at this Stack Exchange estimate for a dual core 3.8GHz processor: 670 million keys per second. If we were to assume $5000 in hardware, we can easily exceed 10 billion keys per second. So at a similar hardware cost, key cracking is still more than 2^13 times faster than password cracking.

Revised password strength goals

Working on my estimate that it is 2^13 times more expensive to test a well-hashed password than it is to test an AES key, we should consider a reasonably well hashed password as being 13 bits stronger than its actual entropy with respect to cracking. If we want to achieve 90 bits of "effective strength" then 77 bits of password strength should do it. That is achieved with a six word Diceware password (77.5-bits) from the original list and 84.6 bits with six words drawn from a list of 17679 words.

I don't expect most people to use passwords that long. I expect people will use things that are 4 or 5 words long. but if you are genuinely worried about the NSA going after your passwords, then six words should be sufficient assuming that you use a decent password hashing scheme.

Very rough estimates only

I didn't spend a lot of time researching costs and benchmarks. There are lots of things in my estimates to quibble with. I attempted to be conservative (pessimistic about the scheme I'm advocating). I've been vague about "well-hashed passwords" as well. Again, I'm being very conservative with respect to the password hashing in 1Password. (For our new data format, attackers have been kept to under 20,000 guesses per second and for our older data format they've reached 300,000 guesses per second for multi-GPU machines. In my estimates here, I've picked 1 million guesses per second for a "reasonably well-hashed password".)

A few more historical notes

The overall idea for "XKCD-like" passwords goes at least as far back as the S/Key one time passwords from the early 1980s. These used a list of 2048 one through four letter words. A six word S/Key password got you 66 bits. I don't know if this idea of using randomly selected words from a list for a passphrase predates S/Key.

In 1995, Arnold Reinhold proposed Diceware. I don't know whether he was aware of S/Key at the time. Diceware was proposed in the context of developing pass phrases for PGP. It was also before most computers had cryptographically appropriate random number generators. So it actually involves rolling dice. (Although I trust the CSPRNGs on the machines that I use, I still enjoy "rolling up a new password").

In June 2011, I revived interest in Diceware in Toward Better Master Passwords with some additional modification. This resulted in my 15 minutes of fame. After the XKCD comic came out, I produced a geek edition that walked through some of the math.

In July 2011, Randall Monroe had picked up on Diceware-like schemes and published his now famous comic. As I am not the inventor of the idea, I don't at all mind being upstaged by the comic. Indeed, as I said in my follow-up article

What took me nearly 2000 words to say in non-technical terms, Randall Monroe was able to sum up in a comic. This just shows the power of math ...

But there is one thing about how the comic has been interpreted that does worry me. It is clear to me and people who already understood the scheme that the words must be chosen through a reliably uniform random process. Picking words "at random" out of your head is not a reliably uniform process.

Answer 4

The XKCD password scheme is as good as it ever was. The security doesn't derive from it being unknown, but from it being a good way to generate memorable passwords from a large search space. If you select the words to use rather than generate them randomly, though, this advantage is lost -- humans aren't good at being random.

The bit about memory is poorly stated, but it is a concern: if password-stealing malware ever gets on your computer, it'll sweep up everything text-like from RAM and the hard drive to use in a directed attack on your accounts.

Answer 5

As others have said, the attack Bruce Schneier describes is effective when the user chooses multiple words him/her-self, not using a tool. Schneier usually writes to a general public audience, which is unlikely to grasp the difference between self-chosen "random" words and program-chosen random words.

I'll add that even if you use a script or other tool to randomly choose words from a dictionary, you have to use the first sequence it gives you. If you decide, "I don't like that one," and run it again until you do like it, it is no longer a random passphrase, it is human-chosen.

Also, even if you use a script, and even if you don't damage the randomness by choosing your favorite of multiple sequences, there is still the possibility that an attacker could exploit your PRNG (pseudo-random number generator). If the attacker can learn when you created the password, and what PRNG you used, and maybe other information about your PRNG such as network traffic that was produced using your PRNG around the same time, that could reduce the effective entropy of your random passphrase.

Perhaps a bit esoteric, but if your PRNG is exploitable, the 2^44 figure will not be fully realized. (And if you assume "no one will try to exploit my PRNG", why do you care about using a truly secure passphrase?)

Answer 6

It depends. One thing you need to understand is that this is not security-by-obscurity: the entropy values used in the comic assume that the attacker already knows you're using this method. If the attacker doesn't know how you're generating the passphrase, then the entropy goes up massively.

The trick to the XKCD method is that you need to actually use a random number generator and a good word list: never pick the words yourself, not even "randomly" (in quotes because humans are actually really bad at picking things randomly, which is why you shouldn't do it). Diceware has tools to help you do this, and even takes the random element out of the computer's reach by using ordinary dice.

Against a broad-based attack -the sort of thing where an attacker got a list of passwords from a Website and doesn't know anything about whose passwords are in the list- this is as strong as it ever was. Just as you say, its strength comes from the power of exponents (and a good word list).

Schneier's attack can work, but only in an entirely different context. His attack assumes that you are being specifically targeted, by an attacker who already knows a great deal about you. This might not seem especially worrisome at first, because the stereotypical determined attacker is an intelligence agent behind a screen, and most of us don't have to worry so much about those: there are only so many of them, and each one can only afford to care about so many people. But it's actually more of a problem than it might first seem, thanks to the advent of sophisticated malware. A malware installation can afford to care about you even though the attacker does not, and so you still wind up facing an extremely determined attacker. Even more determined than a human could be, in fact, though far less creative.

Malware that compiles information on you will give words that seem important to you very high priority in the word list. It does this because most people pick the "random" words themselves, but in so doing, they actually bias quite strongly toward the words that are most important to them: it may still "feel" random, but some words are much more likely to come up than others. For that reason, giving these words high priority often results in relatively quick hits, and this is the "trick" that Schneier is talking about.

However, you can still thwart Schneier's attack by using real randomness. The catch is that this requires discipline: all decisions about what words to use in your passphrase (aside from choosing a good word list) must be taken completely out of your hands. This is where things like Diceware can help you.

Answer 7

The strength math is quite simple if word choice is at random: (number of words in dictionary)^(number of word in the sentence), assuming the attacker knows the number of in the dictionary. So a 5 word phrase using a known (by the attacker!) 7776 word Diceware dictionary: has 7776^5=2.8E19 or 64 bits of entropy.

There is one item that is not mentioned in the scheme: by adding just 1 (random) character at a random place in the whole phrase, the strength is up by about 10 bits, see Diceware, Optional stuff.

The above math also does not account for separator symbol between the words. That can add another 5 bits.

Answer 8

I'd also like to add a yes answer also, but for other reasons. It's not a good advice [in general] because of length constraints:

• Sites like Skype, ING, eBay, and in my country Binckbank ans KPN limit passwords to 20 characters. (That bank limit is 15, but it used 2 factor authorization)
• With an average length of 4.5 characters/word for a short 3000-8000 word dictionary, that allows for using 3-4 word phrases only.
• When using large dictionaries the average may be 6-7: 3 words only
• If the site insists on using a symbol and a number in the password, only 18 characters are available for the phrase.

Those lengths only protect against online attacks. For Off-line attacks is depends on the key derivation and hash function, iteration counts and cracking hardware used by the site of app, whether a 3-4 word phrase offers sufficient protection.

Answer 9

No, I don't think so.

The actual advice in that xkcd comic are to use mnemonics that are easy for you to remember and generate password as long as you can remember them. Those are basic password advice anywhere, and will always stand true (even the quoted Schneier's method uses these two basic facts). Indeed, the comic makes use of common English words, but your implementation doesn't have to be, nor did the comic implies that you should.

Of course, the most secure passwords are totally random strings like how an MD5 string looks, and you probably can use a password manager to store all those passwords, but then what password are you going to use for that manager? ¯\ (ツ) /¯

Answer 10

It's important to have the right context. The xkcd comic compares Tr0ub4dor&3 at an assumed 28 bit entropy (though I calculate it as 34.6) to correcthorsebatterystaple and its assumed 44 bits of entropy (a four word diceware code is 51.7 bits … but one of those words isn't diceware. Using a simple 100k-word spelling dictionary, I calculate it to be 66.4 bits).

First, let's make this easier to understand. There are 94 printable characters. A one character password has log₂(94) = 6.55 bits of entropy. Two characters have log₂(94²) = 13.10 bits of entropy. You can divide the final entropy of a password scheme by 6.55 in order to determine the equivalent complexity of a purely random password as measured in characters.

Therefore:

• 28 bits of entropy ≈ 4.3 character password (very bad!)
• 44 bits of entropy ≈ 6.7 character password (also bad)
• 66.4 bits of entropy ≈ 10.1 character password (okay for 2016)

Trusting xkcd's numbers, you can see why Schneier was concerned. This seems a bit overblown, as most attackers will still give up after ten or so characters ^{[citation needed]} —it should take a few years for a big cluster to break a 10-char MD5 hashed password— though obviously if a good attacker knows your scheme, absolute character length isn't an issue.

The total complexity of the scheme is most important. You must assume the worst case (that the attacker knows your exact scheme). It's a great idea to additionally ensure your password is 11+ characters (when permitted), but that's a secondary priority (and it comes for free with pass phrases).

 

Create pass phrases with four words plus a passcode

Here is my passpharse creation advice (with entropy estimates):

• Make a nonsensical "sentence" of 4+ words of 4+ characters each (100,000⁴)
• None of these words can be connected to you –or each other– in any way
• Use case, spaces, and at least two symbols or punctuation marks (32²)
• At least one word should fail spell check (e.g. leetspeak, foreign words, 64 each)
• Include at least one other "error" (spelling/grammar/syntax, entropy unknown)
• Between two words, add a traditional "random" 7+ char passcode (92⁷)

This should be at least log₂(100000⁴ × 32 × 3 × 64 × 92⁵) = 112 bits of entropy (which is very strong, ≈17 chars). I skipped capitalization (I assume only the first char is uppercase) and one symbol (I assume it ends in ., !, or ?, so the second symbol has a complexity of 3) and I also assumed that "random" isn't quite random and calculated the code as a five character equivalent (strict adherence to the above formula would give you 128+ bits of entropy at ≈20 chars).

 

That final point is worth repeating:

Humans are very bad at generating randomness

Very very few human-generated "random" character passcodes even approach true randomness. There will be patterns in the code related to the person's keyboard, favorite numbers, and/or an assumption that a certain obscure word is unguessable.

I designed this scheme to be robust against people's inherent lack of randomness; assuming a limited vocabulary (say the 2600 words in Basic English), use of related words (penalized by counting only three words), and a passcode limited to just the entropy of six alphanumerics, log₂(2600³ × 62⁶) itself is still strong at 70 bits (≈10.6 characters).

Don't let this water down your passphrase! This section is present to demonstrate that this scheme has some resistance to the limited entropy of human choices, not to encourage poor choices.

The only real trouble comes from people who take quotes or lyrics as their four words. These pass phrases are trivially defeated if the quote or lyric can be guessed (say by looking at your Facebook likes) or would otherwise have an entropy of around 6 random characters at a crack time of 30 seconds (MD5) to 17 days (PBKDF2).

 

You can use my entropy table to calculate the entropy of your passphrase scheme.

_{(Don't concern yourself with the fact that passwords briefly live in memory unless you're a developer)}