936: Password Strength

Explain xkcd: It's 'cause you're dumb.
Revision as of 14:41, 14 August 2013 by Markhurd (Talk | contribs)

Jump to: navigation, search
Password Strength
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.
Title text: 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.

Explanation

Ambox notice.png This explanation may be incomplete or incorrect:
Please include the reason why this explanation is incomplete, like this: {{incomplete|reason}}

If you can address this issue, please edit the page! Thanks.

Computer security consultant Mark Burnett has posted a good discussion and analysis of this comic on his blog.

This comic is saying that the password in the top frames "Tr0ub4dor&3" is easier for password cracking software to guess than "correcthorsebatterystaple". And this is absolutely true that people make passwords hard to remember because that means that they are "safer".

It is certainly true that length, all other things being equal, tends to make for very strong passwords and this can confirmed by using rumkin.com's password strength checker. 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.

Now, what is not clearly addressed:

  • Will these passwords have to be entered manually? And if so, how difficult is it, mechanically, to enter an each character of the password? On a keyboard it's easy, but on a smartphone or console... not so much.
  • How easy are these passwords to remember?
  • 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?

Steve Gibson from the Security Now podcast did a lot of work in this arena and found that this password D0g..................... (24 characters long) is stronger than PrXyc.N(n4k77#L!eVdAfp9 (23 characters long) because both have at least one uppercase letter, lowercase letter, number, and "special" character, so length trumps perceived complexity. Steve Gibson makes this very clear in his password haystack reference guide and tester:

"Once an exhaustive password search begins, the most important factor is password length!"

The important thing to take away from this comic is that longer passwords are better because each additional character adds much more time to the breaking of the password. That's what Randall is trying to get through here. Complexity does not matter unless you have length in passwords. Complexity is more difficult for humans to remember. Length is not.

Transcript

The comic illustrates the relative strength of passwords assuming basic knowledge of the system used to generate them. A set of boxes is used to indicate how many bits of entropy a section of the password provides. The comic is laid out with 6 panels arranged in a 3x2 grid. On each row, the first panel explains the breakdown of a password, the second panel shows how long it would take for a computer to guess, and the third panel provides an example scene showing someone trying to remember the password.

[The password "Tr0ub4dor&3" is shown in the center of the panel. A line from each annotation indicates the word section the comment applies to.]
Uncommon (non-gibberish) base word
[Highlighting the base word - 16 bits of entropy.]
Caps?
[Highlighting the first letter - 1 bit of entropy.]
Common Substitutions
[Highlighting the letters 'a' (substituted by '4') and both 'o's (the first of which is substituted by '0') - 3 bits of entropy.]
Punctuation
[Highlighting the symbol appended to the word - 4 bits of entropy.]
Numeral
[Highlighting the number appended to the word - 3 bits of entropy.]
Order unknown
[Highlighting the appended characters - 1 bit of entropy.]
(You can add a few more bits to account for the fact that this is only one of a few common formats.)
~28 bits of entropy
2^28 = 3 days at 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.)
Difficulty to guess: Easy.
[Cueball stands scratching his head trying to remember the password.]
Cueball: Was it trombone? No, Troubador. And one of the O's was a zero?
Cueball: And there was some symbol...
Difficulty to remember: Hard.
[The passphrase "correct horse battery staple" is shown in the center of the panel.]
Four random common words {Each word has 11 bits of entropy.}
~44 bits of entropy
2^44 = 550 years at 1000 guesses sec
Difficulty to guess: Hard.
[Cueball is thinking, in his thought bubble a horse is standing to one side talking to an off-screen observer. An arrow points to a staple attached to the side of a battery.]
Horse: That's a battery staple.
Observer: Correct!
Difficulty to remember: You've already memorized it

The caption below the comic reads: Through 20 years of effort, we've successfully trained everyone to use passwords that are hard for humans to remember, but easy for computers to guess.

External links

  • Some info was used from the highest voted answer given to the question of "how accurate is this XKCD comic" at StackExchange [1].
  • Similarly, a question of "how right this comic is" was made at AskMetaFilter [2] and Randall responded there.
  • Also the Wikipedia article on 'Passphrase' is useful [3].
  • In case you missed it in the explanation, GRC's Steve Gibson has a fantastic page [4] about this (and may have prompted this comic, as his podcast [5] about this was posted the month before this comic).
Comment.png add a comment!

Discussion

You still have to vary the words with a bit of capitalization, punctuation and numbers a bit, or hackers can just run a dictionary attack against your string of four words. Davidy²²[talk] 09:12, 9 March 2013 (UTC)

No you don't. Hackers cannot run a dictionary attack against a string of four randomly picked words. Look at the number of bits displayed in the image: 11 bits for each word. That means he's assuming a dictionary of 2048 words, from which each word is picked randomly. The assumption is that the cracker knows your password scheme. 86.81.151.19 20:17, 28 April 2013 (UTC) Willem

Sometimes this is not possible. (I'm looking at you, local banks with 8-12 character passwords and PayPal) If I can, I use a full sentence. A compound sentence for the important stuff. This adds the capitalization, punctuation and possibly the use of numbers while it's even easier to remember then Randall's scheme. I think it might help against the keyloggers too, if your browser/application autofills the username filed, because you password doesn't stand out from the feed with being gibberish. 195.56.58.169 09:01, 30 August 2013 (UTC)

The basic concept can be adapted to limited-length passwords easily enough: memorize a phrase and use the first letter of each word. It'll require about a dozen words (you're only getting 4.7 bits per letter at best, actually less because first letters of words are not truly random, though they are weakly if at all correlated with their neighbors -- based on the frequencies of first letters of words in English, and assuming no correlation between each first letter and the next, I calculate about 4 bits per character of Shannon entropy). SteveMB 18:35, 30 August 2013 (UTC)

Followup: The results of extracting the first letters of words in sample texts (the Project Gutenberg texts of The Adventures of Huckleberry Finn, The War of the Worlds, and Little Fuzzy) and applying a Shannon entropy calculation were 4.07 bits per letter (i.e. first letter in word) and 8.08 bits per digraph (i.e. first letters in two consecutive words). These results suggest that first-letter-of-phrase passwords have approximately 4 bits per letter of entropy. --SteveMB (talk) 14:21, 4 September 2013 (UTC)

Addendum: The above test was case-insensitive (all letters converted to lowercase before feeding them to the [frequency counter]). Thus, true-random use of uppercase and lowercase would have 5 bits per letter of entropy, and any variation in case (e.g. preserving the case of the original first letter) would fall between 4 and 5 bits per letter. --SteveMB (talk) 14:28, 4 September 2013 (UTC)

I just have RANDOM.ORG print me ten pages of 8-character passwords and tape it to the wall, then highlight some of them and use others (say two down and to the right or similar) for my passwords, maybe a given line a line a little jumbled for more security. 70.24.167.3 13:27, 30 September 2013 (UTC)

Remind me to visit your office and secretly replace your wall-lists by a list of very similar looking strings ;) --Chtz (talk) 13:53, 30 September 2013 (UTC)

Simple.com (online banking site) had the following on it’s registration page:

“Passphrase? Yes. Passphrases are easier to remember and more secure than traditional passwords. For example, try a group of words with spaces in between, or a sentence you know you'll remember. "correct horse battery staple" is a better passphrase than r0b0tz26.”

Online security for a banking site has been informed by an online comic. Astounding. 173.245.54.78 21:22, 11 November 2013 (UTC)

The Web service Dropbox has an Easter egg related to this comic on their sign-up page. That page has a password strength indicator (powered by JavaScript) which changes as you type your password. This indicator also shows hints when hovering the mouse cursor over it. Entering "Tr0ub4dor&3" or "Tr0ub4dour&3" as the password causes the password strength indicator to fall to zero, with the hint saying, "Guess again." Entering "correcthorsebatterystaple" as the password also causes the strength indicator to fall to zero, but the hint says, "Whoa there, don't take advice from a webcomic too literally ;)." 108.162.218.95 15:17, 11 February 2014 (UTC)

The explanation said that the comic uses a dictionary[6]. In fact it's a word list, which seems similar but it's not. All the words in the word list must be easy to memorize. This means it's better not to have words such as than or if. Also, it's better not to have homophones (wood and would, for example). The sentence dictionary attack doesn't apply here. A dictionary attack requires the attacker to use all the words in the dictionary (e.g. 100,000 words). Here we must generate the 17,592,186,044,416 combinations of 4 common words. Those combinations can't be found in any dictionary. At 25 bytes per "word" that dictionary would need 400 binary terabytes to be stored. Xhfz (talk) 21:37, 11 March 2014 (UTC)
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox

It seems you are using noscript, which is stopping our project wonderful ads from working. Explain xkcd uses ads to pay for bandwidth, and we manually approve all our advertisers, and our ads are restricted to unobtrusive images and slow animated GIFs. If you found this site helpful, please consider whitelisting us.

Want to advertise with us, or donate to us with Paypal or Bitcoin?