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.

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.

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.

The comic says "four random common words". It must take some creative reading to interpret that as "four non-random common words".

When the comic first came out there was a bunch of analysis 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.

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.

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.

There's a little box for each bit of entropy (this is consistent throughout the comic). There are 11 little boxes by each word.

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.

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?

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.

Typical vocabulary is smaller than that.

And pass phrases will tend away from words like perspicacious.

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

ok... so what's the message?

Maybe the author just didn't think of Kolmogorov complexity and thought it was a good idea.

The message is pretty much the punchline of the comic.

The other message is: stop posting XKCD #936 for the bazillionth time, you assholes.