Home » XKCD #936: Short complex password, or long dictionary passphrase?

XKCD #936: Short complex password, or long dictionary passphrase?

Solutons:


I think the most important part of this comic, even if it were to get the math wrong (which it didn’t), is visually emphasizing that there are two equally important aspects to selecting a strong password (or actually, a password policy, in general):

  • Difficulty to guess
  • Difficulty to remember

Or, in other words:

  • The computer aspect
  • The human aspect

All too often, when discussing complex passwords, strong policies, expiration, etc (and, to generalize – all security), we tend to focus overly much on the computer aspects, and skip over the human aspects.

Especially when it comes to passwords, (and double especially for average users), the human aspect should often be the overriding concern.
For example, how often does strict password complexity policy enforced by IT (such as the one shown in the XKCD), result in the user writing down his password, and taping it to his screen? That is a direct result of focusing too much on the computer aspect, at the expense of the human aspect.

And I think that is the core message from the sage of XKCD – yes, Easy to Guess is bad, but Hard to Remember is equally so.
And that principle is a correct one. We should remember this more often, AKA AviD’s Rule of Usability:

Security at the expense of usability comes at the expense of security.

Here is a thorough explanation of the mathematics in this comic:

The little boxes in the comic represent entropy in a logarithmic scale, i.e. “bits”. Each box means one extra bit of entropy. Entropy is a measure of the average cost of hitting the right password in a brute force attack. We assume that the attacker knows the exact password generation method, including probability distributions for random choices in the method. An entropy of n bits means that, on average, the attacker will try 2n-1 passwords before finding the right one. When the random choices are equiprobable, you have n bits of entropy when there are 2n possible passwords, which means that the attacker will, on average, try half of them. The definition with the average cost is more generic, in that it captures the cases where random choices taken during the password generation process (the one which usually occurs in the head of the human user) are not uniform. We’ll see an example below.

The point of using “bits” is that they add up. If you have two password halves that you generate independently of each other, one with 10 bits of entropy and the other with 12 bits, then the total entropy is 22 bits. If we were to use a non-logarithmic scale, we would have to multiply: 210 uniform choices for the first half and 212 uniform choices for the other half make up for 210·212 = 222 uniform choices. Additions are easier to convey graphically with little boxes, hence our using bits.

That being said, let’s see the two methods described in the comic. We’ll begin with the second one, which is easier to analyze.

The “correct horse” method

The password generation process for this method is: take a given (public) list of 2048 words (supposedly common words, easy to remember). Choose four random words in this list, uniformly and independently of each other: select one word at random, then select again a word at random (which could be the same as the first word), and so on for a third and then a fourth words. Concatenate all four words together, and voila! you have your password.

Each random word selection is worth 11 bits, because 211 = 2048, and, crucially, each word is selected uniformly (all 2048 words have the same probability of 1/2048 of being selected) and independently of the other words (you don’t choose a word so that it matches or non-matches the previous words, and, in particular, you do not reject a word if it happens to be the same choice as a previous word). Since humans are not good at all at doing random choices in their head, we have to assume that the random word selection is done with a physical device (dice, coin flips, computers…).

The total entropy is then 44 bits, matching the 44 boxes in the comic.

The “troubador” method

For this one, the rules are more complex:

  1. Select a random word in a given big list of meaningful words.
  2. Decide randomly whether to capitalize the first letter, or not.
  3. For the letters which are eligible to “traditional substitutions”, apply or not apply the substitution (decide randomly for each letter). These traditional substitutions can be, for instance: “o” -> “0”, “a” -> “4”, “i” -> “!”, “e” -> “3”, “l” -> “1” (the rules give a publicly known exhaustive list).
  4. Append a punctuation sign and a digit.

The random word is rated to 16 bits by the comic, meaning uniform selection in a list of 65536 words (or non-uniform in a longer list). There are more words than that in English, apparently about 228000, but some of them are very long or very short, others are so uncommon that people would not remember them at all. “16 bits” seem to be a plausible count.

Uppercasing or not uppercasing the first letter is, nominally, 1 bit of entropy (two choices). If the user makes that choice in his head, then this will be a balance between user’s feeling of safety (“uppercase is obviously more secure !”) and user’s laziness (“lowercase is easier to type”). There again, “1 bit” is plausible.

“Traditional substitutions” are more complex because the number of eligible letters depends on the base word; here, three letters, hence 3 bits of entropy. Other words could have other counts, but it seems plausible that, on average, we’ll find about 3 eligible letters. This depends on the list of “traditional substitutions”, which are assumed to be a given convention.

For the extra punctuation sign and digit, the comic gives 1 bit for the choice of which comes first (the digit or the punctuation sign), then 4 bits for the sign and 3 bits for the digit. The count for digits deserves an explanation: this is because humans, when asked to choose a random digit, are not at all uniform; the digit “1” will have about 5 to 10 times more chances of being selected than “0”. Among psychological factors, “0” has a bad connotation (void, dark, death), while “1” is viewed positively (winner, champion, top). In south China, “8” is very popular because the word for “eight” is pronounced the same way as the word for “luck”; and, similarly, “4” is shunned because of homophony with the word for “death”. The attacker will first try passwords where the digit is a “1”, allowing him to benefit from the non-uniformity of the user choices.

If the choice of digit is not made by a human brain but by an impartial device, then we get 3.32 bits of entropy, not 3 bits. But that’s close enough for illustration purposes (I quite understand that Randall Munroe did not want to draw partial boxes).

Four bits for punctuation are a bit understated; there are 32 punctuation signs in ASCII, all relatively easy to type on a common keyboard. This would mean 5 bits, not 4. There again, if the sign is chosen by a human, then some signs will be more common than others, because humans rarely think of ‘#’ or ‘|’ as “punctuation”.

The grand total of 28 bits is then about right, although it depends on the precise details of some random selections, and the list of “traditional substitutions” (which impacts the average number of eligible letters). With a computer-generated password, we may hope for about 30 bits. That’s still low with regards to the 44 bits of the “correct horse” method.

Applicability

The paragraphs above show that the maths in the comic are correct (at least with the precision that can be expected in these conditions — that’s a webcomic, not a research article). It still requires the following conditions:

  • The “password generation method” is known by the attacker. This is the part which @Jeff does not believe. But it makes sense. In big organizations, security officers publish such guidelines for password generation. Even when they don’t, people have Google and colleagues, and will tend to use one of about a dozen or so sets of rules. The comic includes provisions for that: “You can add a few more bits to account for the fact that this is only one of a few common formats”.

    Bottom-line: even if you keep your method “secret”, it won’t be that secret because you will more or less consciously follow a “classic” method, and there are not that many of those.

  • Random choices are random and uniform. This is hard to achieve with human users. You must convince them to use a device for good randomness (a coin, not a brain), and to accept the result. This is the gist of my original answer (reproduced below). If the users alter the choices, if only by generating another password if the one they got “does not please them”, then they depart from random uniformity, and the entropy can only be lowered (maximum entropy is achieved with uniform randomness; you cannot get better, but you can get much worse).

The right answer is of course that of @AviD. The maths in the comic are correct, but the important point is that good passwords must be both hard to guess and easy to remember. The main message of the comic is to show that common “password generation rules” fail at both points: they make hard to remember passwords, which are nonetheless not that hard to guess.

It also illustrates the failure of human minds at evaluating security. “Tr0ub4dor&3” looks more randomish than “correcthorsebatterystaple”; and the same minds will give good points to the latter only because of the wrong reason, i.e. the widespread (but misguided) belief that password length makes strength. It does not. A password is not strong because it is long; it is strong because it includes a lot of randomness (all the entropy bits we have been discussing all along). Extra length just allows for more strength, by giving more room for randomness; in particular, by allowing “gentle” randomness that is easy to remember, like the electric horse thing. On the other hand, a very short password is necessarily weak, because there is only so much entropy you can fit in 5 characters.

Note that “hard to guess” and “easy to remember” do not cover all that is to say about password generation; there is also “easy to use”, which usually means “easy to type”. Long passwords are a problem on smartphones, but passwords with digits and punctuation signs and mixed casing are arguably even worse.


Original answer:

The comic assumes that the selection of a random “common” word yields an entropy of about 11 bits — which means that there are about 2000 common words. This is a plausible count. The trick, of course, is to have a really random selection. For instance, the following activities:

  • select four words randomly, then remember them in the order which makes most sense;
  • if the four words look too hard to remember, scrap them and select four others;
  • replace one of the words with the name of a footballer (the attacker will never guess that !);

… all reduce the entropy. It is not easy to get your users to actually use true randomness and accept the result.

The same users will probably complain about the hassle of typing a long password (if the typing involves a smartphone, I must say that I quite understand them). An unhappy user is never a good thing, because he will begin to look for countermeasures which will make his life easier, such as keeping the password in a file and “typing” it with a copy&paste. Users can often be surprisingly creative that way. Therefore long passwords have a tendency to backfire, security-wise.

The two passwords, based on rumkin.com’s password strength checker:

Tr0ub4dor&3

  • Length: 11
  • Strength: Reasonable – This password is fairly secure cryptographically and skilled hackers may need some good computing power to crack it. (Depends greatly on implementation!)
  • Entropy: 51.8 bits
  • Charset Size: 72 characters

and

correct horse battery staple

  • Length: 28
  • Strength: Strong – This password is typically good enough to safely guard sensitive information like financial records.
  • Entropy: 104.2 bits
  • Charset Size: 27 characters

It is certainly true that length, all other things being equal, tends to make for very strong passwords — and we’re seeing that confirmed here.

Even if the individual characters are all limited to [a-z], the exponent implied in “we added another lowercase character, so multiply by 26 again” tends to dominate the results.

In other words, 7211 < 2728.

Now, what is not clearly addressed:

  1. Will these passwords have to be entered manually? And if so, how difficult is it, mechanically, to enter a each character of the password? On a keyboard it’s easy, but on a smartphone or console… not so much.

  2. How easy are these passwords to remember?

  3. How sophisticated are the password attacks? In other words, will they actually attempt common schemes like “dictionary words separated by spaces”, or “a complete sentence with punctuation”, or “leet-speak numb3r substitution” as implied by xkcd? Crucially, this is how XKCD justifies cutting the entropy of the first password in half!

Point 3 is almost unanswerable and I think personally highly unlikely in practice. I expect it will be braindead brute force all the way to get the low-hanging fruit, and the rest ignored. If there isn’t any low-hanging password fruit (and oh, there always is), they’ll just move on to the next potential victim service.

Therefore I say the cartoon is materially accurate in terms of its math, but the godlike predictive password attacks it implies are largely a myth. Which means, IMHO, that these specific two passwords are kind of a wash in practice and would offer similar-ish levels of protection.

Related Solutions

How to play YouTube audio in background/minimised?

Here's a solution using entirely free and open source software. The basic idea is that although YouTube can't play clips in the background, VLC for Android can play clips in the background, so all we need to do is pipe the clip to VLC where we can listen to it...

Why not use “which”? What to use then?

Here is all you never thought you would ever not want to know about it: Summary To get the pathname of an executable in a Bourne-like shell script (there are a few caveats; see below): ls=$(command -v ls) To find out if a given command exists: if command -v...

Split string into Array of Arrays [closed]

If I got correct what you want to receive as a result, then this code would make what you want: extension Array { func chunked(into size: Int) -> [[Element]] { return stride(from: 0, to: self.count, by: size).map { Array(self[$0 ..< Swift.min($0 + size,...

Retrieving n rows per group

Let's start with the basic scenario. If I want to get some number of rows out of a table, I have two main options: ranking functions; or TOP. First, let's consider the whole set from Production.TransactionHistory for a particular ProductID: SELECT...

Don’t understand how my mum’s Gmail account was hacked

IMPORTANT: this is based on data I got from your link, but the server might implement some protection. For example, once it has sent its "silver bullet" against a victim, it might answer with a faked "silver bullet" to the same request, so that anyone...

What is /storage/emulated/0/?

/storage/emulated/0/Download is the actual path to the files. /sdcard/Download is a symlink to the actual path of /storage/emulated/0/Download However, the actual files are located in the filesystem in /data/media, which is then mounted to /storage/emulated/0...

How can I pass a command line argument into a shell script?

The shell command and any arguments to that command appear as numbered shell variables: $0 has the string value of the command itself, something like script, ./script, /home/user/bin/script or whatever. Any arguments appear as "$1", "$2", "$3" and so on. The...

What is pointer to string in C?

argv is an array of pointers pointing to zero terminated c-strings. I painted the following pretty picture to help you visualize something about the pointers. And here is a code example that shows you how an operating system would pass arguments to your...

How do I change the name of my Android device?

To change the hostname (device name) you have to use the terminal (as root): For Eclair (2.1): echo MYNAME > /proc/sys/kernel/hostname For Froyo (2.2): (works also on most 2.3) setprop net.hostname MYNAME Then restart your wi-fi. To see the change, type...

How does reverse SSH tunneling work?

I love explaining this kind of thing through visualization. 🙂 Think of your SSH connections as tubes. Big tubes. Normally, you'll reach through these tubes to run a shell on a remote computer. The shell runs in a virtual terminal (tty). But you know this part...

Difference between database vs user vs schema

In Oracle, users and schemas are essentially the same thing. You can consider that a user is the account you use to connect to a database, and a schema is the set of objects (tables, views, etc.) that belong to that account. See this post on Stack Overflow:...

What’s the output of this code written in java?

//if you're using Eclipse, press ctrl-shift-f to "beautify" your code and make it easier to read int arr[] = new int[3]; //create a new array containing 3 elements for (int i = 0; i < 3; i++) { arr[i] = i;//assign each successive value of i to an entry in...

How safe are password managers like LastPass?

We should distinguish between offline password managers (like Password Safe) and online password managers (like LastPass). Offline password managers carry relatively little risk. It is true that the saved passwords are a single point of failure. But then, your...

Can anyone tell me why this program go to infinite times?

while (i <= 2) { while (i > 0) { a = a + b; i--; <- out the inner while loop when i = 0 } printf("%d", a); i++; <- at here, the i==0 each time, so infinity loop } Because your nested loop always restores the value of i to 0, And 0 <= 2 is always...