5 ms·

Most people who quote XKCD #936 miss the point. It has a decent message, but taking it literally is a grave mistake. This style of concocting passphrases (chai

Most people who quote XKCD #936 miss the point. It has a decent message, but taking it literally is a grave mistake. This style of concocting passphrases (chain dictionary words together) as a whole has a low Kolmogorov complexity, and can easily be imported by attackers through wordlist mangling or using some advanced software features, such as Hashcat's combinator attack. Finally, humans are fallible. They'll always go for certain predictable combinations, and certain permutations will be more widespread among those. If an attacker has any suspicion you're using the XKCD algorithm literally, it's trivial for them to make a move.

arielweisberg 13y ago
I think the comic is suggesting that the words are selected at random, and not by a human so the distribution is even. That is how you end up with the expected entropy.
- jimminy 13y ago
  The comic makes no expectation or assumption about how the words are selected. The expected entropy is derived from "correct horse battery staple", including the spaces, using NIST SP 800-63.
  - arielweisberg 13y ago
    When the comic first came out there was a bunch of analysis http://www.explainxkcd.com/wiki/index.php/936:_Password_Strength http://www.explainxkcd.com/wiki/index.php/936:_Password_Stre... "xkcd's entropy estimate of 11 bits per word assumes that the password is being brute-forced with a dictionary attack, and that the words are being chosen from a dictionary of 2000 words (log2(2000) ≈ 11). (For comparison, the entropy offered by Diceware's 7776 word dictionary is 13 bits per word.) If a dictionary attack were not used, the "common words" password would take even longer to crack than depicted. (25 random lowercase characters would have 117 bits of entropy, vs 44 bits for the dictionary words.)" So yeah maybe it is implicit in the comic, but the math is backed by a specific set of assumption on how the words were selected. Or I could be wrong, I haven't verified it personally.
    - jimminy 13y ago
      I've validated it myself for an argument when the comic was published for the phrase "correct horse battery staple". First character is 4 bits: c = 4 The next 7 chars are 2 bits/each: "orrect " = 14 Characters 9-20 are 1.5 bit/each: "horse batter" = 18 Charactes 21-n are 1 bit/each: "y staple" = 8 No bonus for including both upper and non-alpha chars. No bonus for passwords of length less than 20 chars, not containing dictionary words, because the password is longer than 20 characters. Total entropy: 4 + 14 + 18 + 8 = 44 bits of entropy.
      - maxerickson 13y ago
        There's a little box for each bit of entropy (this is consistent throughout the comic). There are 11 little boxes by each word.
      - arielweisberg 13y ago
        I think it is cool that both estimates of entropy come to the same number, but that still seems like the wrong way to look at the approach even if Randall didn't intend it that way. The NIST entropy estimation is based off of characters that aren't chosen at random (I think?) and it is a heuristic. For the approach I think Randall intended to describe they aren't really words, just glyphs chosen randomly from a set of glyphs. That these glyphs are easy to memorize and drop right into existing password interfaces is orthogonal.
  - weichi 13y ago
    While it's true that NIST SP 800-63 gives 44 bits of entropy for the comic's password, this is purely a coincidence. The comic certainly isn't using using NIST SP 800-63 to calculate the entropy. The "xkcd" method extended to, say, 10 words would give 110 bits per xkcd's calculations, but I think it's safe to say that very few of these passwords would qualify as 110 bits under NIST SP 800-63.
  - dTal 13y ago
    The comic says "four random common words". It must take some creative reading to interpret that as "four non-random common words".
leephillips 13y ago
Can anyone explain to me why he assings only 2^11 bits of entropy to a word? Doesn't that correspond to choosing from only about 2000 words? If we choose from the more typical adult vocabulary of 100,000 words, isn't that log2(100,000) = 17 bits? Or am I doing it wrong?
- bredman 13y ago
  I think he did this to show how even with a very restricted dictionary you could still build a relatively secure login system. Having a restricted dictionary could also help with the issues other people are discussing with humans being socially programmed to select certain word orders as their password under this scheme.
- jimminy 13y ago
  He's not assigning entropy per word. He's using NIST SP 800-63, based on the character-length of the phrase, to assign the entropy value. Proof: https://news.ycombinator.com/item?id=7163362 https://news.ycombinator.com/item?id=7163362
- maxerickson 13y ago
  Typical vocabulary is smaller than that. And pass phrases will tend away from words like perspicacious.
Dewie 13y ago
ok... so what's the message? Maybe the author just didn't think of Kolmogorov complexity and thought it was a good idea.
- vezzy-fnord 13y ago
  The message is pretty much the punchline of the comic. The other message is: stop posting XKCD #936 for the bazillionth time, you assholes.
tga_d 13y ago
The Kolmogorov complexity is almost identical to the entropy (Kolmogorov complexity is applied to a given string, entropy applies to the thing producing it). The entropy estimates in the comic, if you prefer to think of it this way, assume a "wordlist attack" (they actually assume the most efficient attack possible, though in this case I guess you could say that's a "wordlist attack"). It's also assumed that the words are chosen randomly (from the comic: "four random common words"), not "off the top of my head," so no, human fallibility is not an issue with the scheme itself, so much as the way many people interpret the word "random," when in respect to entropy, it has a very specific meaning. It's therefore an undeniable fact that attacking those passwords would require trying an average of half the possible combinations, or 2^(entropy-1). These passwords are just as strong as fully random character strings, so long as you ascribe the correct entropy values. If it helps, don't think of the words as words, but instead as random numbers. It just so happens that these random numbers are presented in a form that's easier to remember. And 4 random numbers between 0 and 2048 cannot be easily guessed.

arielweisberg 13y ago

I think the comic is suggesting that the words are selected at random, and not by a human so the distribution is even. That is how you end up with the expected entropy.

jimminy 13y ago
The comic makes no expectation or assumption about how the words are selected. The expected entropy is derived from "correct horse battery staple", including the spaces, using NIST SP 800-63.
- arielweisberg 13y ago
  When the comic first came out there was a bunch of analysis http://www.explainxkcd.com/wiki/index.php/936:_Password_Strength http://www.explainxkcd.com/wiki/index.php/936:_Password_Stre... "xkcd's entropy estimate of 11 bits per word assumes that the password is being brute-forced with a dictionary attack, and that the words are being chosen from a dictionary of 2000 words (log2(2000) ≈ 11). (For comparison, the entropy offered by Diceware's 7776 word dictionary is 13 bits per word.) If a dictionary attack were not used, the "common words" password would take even longer to crack than depicted. (25 random lowercase characters would have 117 bits of entropy, vs 44 bits for the dictionary words.)" So yeah maybe it is implicit in the comic, but the math is backed by a specific set of assumption on how the words were selected. Or I could be wrong, I haven't verified it personally.
  - jimminy 13y ago
    I've validated it myself for an argument when the comic was published for the phrase "correct horse battery staple". First character is 4 bits: c = 4 The next 7 chars are 2 bits/each: "orrect " = 14 Characters 9-20 are 1.5 bit/each: "horse batter" = 18 Charactes 21-n are 1 bit/each: "y staple" = 8 No bonus for including both upper and non-alpha chars. No bonus for passwords of length less than 20 chars, not containing dictionary words, because the password is longer than 20 characters. Total entropy: 4 + 14 + 18 + 8 = 44 bits of entropy.
    - maxerickson 13y ago
      There's a little box for each bit of entropy (this is consistent throughout the comic). There are 11 little boxes by each word.
    - arielweisberg 13y ago
      I think it is cool that both estimates of entropy come to the same number, but that still seems like the wrong way to look at the approach even if Randall didn't intend it that way. The NIST entropy estimation is based off of characters that aren't chosen at random (I think?) and it is a heuristic. For the approach I think Randall intended to describe they aren't really words, just glyphs chosen randomly from a set of glyphs. That these glyphs are easy to memorize and drop right into existing password interfaces is orthogonal.
- weichi 13y ago
  While it's true that NIST SP 800-63 gives 44 bits of entropy for the comic's password, this is purely a coincidence. The comic certainly isn't using using NIST SP 800-63 to calculate the entropy. The "xkcd" method extended to, say, 10 words would give 110 bits per xkcd's calculations, but I think it's safe to say that very few of these passwords would qualify as 110 bits under NIST SP 800-63.
- dTal 13y ago
  The comic says "four random common words". It must take some creative reading to interpret that as "four non-random common words".

leephillips 13y ago

Can anyone explain to me why he assings only 2^11 bits of entropy to a word? Doesn't that correspond to choosing from only about 2000 words? If we choose from the more typical adult vocabulary of 100,000 words, isn't that log2(100,000) = 17 bits? Or am I doing it wrong?

bredman 13y ago
I think he did this to show how even with a very restricted dictionary you could still build a relatively secure login system. Having a restricted dictionary could also help with the issues other people are discussing with humans being socially programmed to select certain word orders as their password under this scheme.
jimminy 13y ago
He's not assigning entropy per word. He's using NIST SP 800-63, based on the character-length of the phrase, to assign the entropy value. Proof: https://news.ycombinator.com/item?id=7163362 https://news.ycombinator.com/item?id=7163362
maxerickson 13y ago
Typical vocabulary is smaller than that. And pass phrases will tend away from words like perspicacious.

Dewie 13y ago

ok... so what's the message? Maybe the author just didn't think of Kolmogorov complexity and thought it was a good idea.

vezzy-fnord 13y ago
The message is pretty much the punchline of the comic. The other message is: stop posting XKCD #936 for the bazillionth time, you assholes.

tga_d 13y ago

The Kolmogorov complexity is almost identical to the entropy (Kolmogorov complexity is applied to a given string, entropy applies to the thing producing it). The entropy estimates in the comic, if you prefer to think of it this way, assume a "wordlist attack" (they actually assume the most efficient attack possible, though in this case I guess you could say that's a "wordlist attack"). It's also assumed that the words are chosen randomly (from the comic: "four random common words"), not "off the top of my head," so no, human fallibility is not an issue with the scheme itself, so much as the way many people interpret the word "random," when in respect to entropy, it has a very specific meaning. It's therefore an undeniable fact that attacking those passwords would require trying an average of half the possible combinations, or 2^(entropy-1). These passwords are just as strong as fully random character strings, so long as you ascribe the correct entropy values. If it helps, don't think of the words as words, but instead as random numbers. It just so happens that these random numbers are presented in a form that's easier to remember. And 4 random numbers between 0 and 2048 cannot be easily guessed.