47

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.

XKCD Mouseover: To anyone who understands information theory and security and is in an infuriating argument with someone who does not (possibly involving mixed case), I sincerely apologize. 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?

  • 15
    I think this would be more on-topic for Math.SE or Security.SE. It needs to be answered with a mathematical calculation rather than empirical evidence. – Nate Eldredge May 27 '17 at 17:43
  • 69
    This would be a duplicate on Security.SE. – Brythan May 27 '17 at 18:45
  • 4
    @Brythan: Even better then, it means it's already been answered! – Matthieu M. May 27 '17 at 19:17
  • 65
    Not to mention it's the highest voted question on Security. -1 for serious lack of research effort (and low usefulness given how much higher quality the answers from the appropriate site are / can be). Probably the rare case for supporting this, too. – Jason C May 27 '17 at 20:29
  • 18
    I'm voting to close this - it is Security Stack Exchange's top voted question and all the specifics have been covered there by top cryptographers and security professionals. That should be the canonical post. – Rory Alsop May 28 '17 at 7:33
65

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.

  • 15
    I guess this shows that the simplest way to have strong individual passwords is to generate them randomly, and them promptly forget about them and count on your password manager to remember them for you... – Matthieu M. May 27 '17 at 19:20
  • 11
    @MatthieuM. Yes, a password manager is really the only good solution for web passwords, but it isn't practical in all situations (eg for full disk encryption). And you will of course also need to remember the password for the password manager as well as your OS user password (depending on your needs, it may - or may not - be a viable solution to write that down though). – tim May 27 '17 at 19:26
  • @tim Full disk encryption is not a problem. Accounts these days are shared between devices, so your master password database is stored in the cloud. The database's encryption, plus the service's like SpiderOak, protects it. You still need to remember two strong passwords, one of the cloud service and one for the password database, but that's much better than N strong passwords. Using a password manager in this manner means you don't lose your passwords if your disk fails or your device is stolen or you can't unencrypt the disk. And you always have a mirror on your devices if the cloud fails. – Schwern May 27 '17 at 22:26
  • 4
    @Schwern I meant it's a problem because you can't save your disk encryption password in the password manager. I don't see how cloud services would help here; they would just add a fourth password you need to remember (OS user, disk, password manager, cloud service). I guess you could save your disk encryption password in a password manager in the cloud and access it via other devices, but that would add new attack vectors. As protection against losing the password manager db, cloud services would help, but so would safely stored backups. – tim May 27 '17 at 22:34
  • @tim Yes, you save your disk encryption password in the password manager and get it via another device like a phone or keep a backup. The biggest risks here are not technical, but on the user: forgetting to backup, and not to using the password manager because it's inconvenient. The risk of the cloud is mitigated by the cloud password, the databases' own encryption, and using cloud storage with end-to-end encryption like SpiderOak. You gain being able to use a password manager conveniently for everything, and not being vulnerable to forgetting to backup, or your home-rolled backup failing. – Schwern May 27 '17 at 22:41
13

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.

  • 1
    Like you say, it depends on the assumptions the attacker will make. The zxcvbn strength calculator gives "Tr0ub4dor&3" only 36 bits of entropy, while "correct horse battery staple" gets 66 bits. – Mark May 31 '17 at 1:22
  • @Mark This still seems like an underestimation to me. For example, "correcthorsebatterystaple" is known to be a 4-word sentence. In reality, the attacker will probably check 3- ,2- and 1-word sentences, brute-force all passwords of 8 characters or less and try a few other common password schemes before they even start cracking 4-word passwords. – Dmitry Grigoryev Jun 7 '17 at 13:54
0

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .