Do four random common words make a stronger password than passwords like "Tr0ub4dor&3"?

Question

In xkcd comic #936, Randall Munroe claims that passwords like "Tr0ub4dor&3" (uncommon base word, caps, common letter substitutions with a number and punctuation suffix) has ~28 bits of entropy, while taking four random common words, like "correct horse battery staple", has ~44 bits of entropy, and is therefore much much stronger.

I am confused because I've always been told that having numbers, cap/non-cap letters and special characters was essential for a strong password...

Is XKCD right on this?

Answer 1

It is true that you do not need numbers, special characters, etc for a strong password. If you instead increase the length of the password, the entropy will increase as well. See for example this entropy table. To get 64 bit of entropy, you could have a 14 character lowercase password, or you could have a 10 character password with all printable ASCII characters, or you could have a passphrase with 5 words randomly selected from a list of 7776 words (Diceware).

The XKCD approach is also called a passphrase or - if done correctly, ie randomly selected words in the passphrase - as Diceware.

The math was checked at security.SE and is approximately correct if we assume a small word list for diceware (~2000 words) and - and this is crucial - randomly selected words. Do note that the XKCD comic assumes randomness for the words in the diceware passphrase, but assumes a pattern for the password (which is a fair assumption and also the point of the comic, as nobody remembers a truly random 11 char password).

Note that people are bad at random selection, so the actual difficulty to guess the password when not using dice to generate it - and accepting the first result - will be lower.

The claim about memorability was examined in the paper Correct horse battery staple: Exploring the usability of system-assigned passphrases (note that the paper uses correctly generated passphrases instead of relying on users "randomly" choosing passphrases):

Contrary to expectations, system-assigned passphrases performed similarly to system-assigned passwords of similar entropy across the usability metrics we examined. Passphrases and passwords were forgotten at similar rates, led to similar levels of user difficulty and annoyance, and were both written down by a majority of participants. However, passphrases took significantly longer for participants to enter, and appear to require error-correction to counteract entry mistakes. Passphrase usability did not seem to increase when we shrunk the dictionary from which words were chosen, reduced the number of words in a passphrase, or allowed users to change the order of words.

Answer 2

There is no single right answer to how much entropy a password has: the result will depend on the assumptions the attacker will make about it, and these are unknown. More or less reasonable guesses can be made about these assumptions, giving more or less reasonable entropy values.

This article at explainxkcd covers the comic in question. It explains the assumptions which were made to justify the calculations in the comic. These calculations are rather pessimistic (i.e. the attacker is supposed to know the exact password layout beforehand), and assume passwords based on dictionary words, so they are underestimating the entropy of both passwords a little.

For the reference, password strength test finds that "Tr0ub4dor&3" has 52 entropy bits (instead of 28 in the comic), while "correcthorsebatterystaple" has 94 bits (instead of 44). This estimation assumes that the attacker will use the letter pair combinations dictionary of the English language. As you can see, the results are quite different, but the claim made in the comic holds for this calculation method too - having a longer common-word password is better than having a shorter password with special characters.

Answer 3

Your problem is with this assumption:

I am confused because I've always been told that having numbers, cap/non-cap letters and special characters was essential for a strong password...

This statement is theoretically true, but false when it comes to how people actually create passwords. Simply replacing an o with a 0 and an a with a 4 does not make your password stronger. At best, the new password has equivalent strength. In reality, it is likely weaker because these substitutions are so popular that an attacker may try 0 and 4 before even trying o and a. Similarly, capitalizing the first letter is so natural that it doesn't add anything to the security. And adding a digit at the end is also a popular choice that increases the password complexity just a tiny bit, even with the extra & character added. Even typos (such as troubador vs troubadour) don't throw off a dictionary attack by more than a tiny bit.

As an aside, NIST has recently moved away from this recommendation (as well as from regularly changing passwords and a number of other common password policies). In the real world, both served to undermine rather than enhance security.

Having digits and special characters only enhances security if you choose each character individually at random, simply because an attacker has to guess each character among 90 or so characters. If you only use letters, an attacker has to guess only guess among 26 or 52 characters (depending on if you use a mix of upper and lower case).

In the case of Tr0ub4dor&3, those characters aren't random. This password is likely trivial to crack with a dictionary attack. Most people have an active vocabulary of around 1000 words or so, educated people of around 6000 or so (in English). These 6000 words would likely include troubadour. An attacker with a dictionary attack will of course try all the permutations of the word. So that's maybe 100 different versions of the word "troubadour".

Further, an attacker would try the most likely permutations first.

So an attacker may well try "Tr0ub4dor" before even trying the base word "troubadour". This word may be number 3000 in the password dictionary an attacker would try (although after the XCKD, it probably moved to number 20), so an attacker would have cracked your password in a few thousand to a few hundred thousand attempts - which may be a few minutes to a few hours with a decent computer.