15
$\begingroup$

When I calculate entropy for the xkcd Password Strength (comic 936) I don't get nearly the amount of entropy stated in the comic.

So why doesn't the the first password "Tr0ub4dor&3" have an entropy of around 50 bits? And why doesn't the passphrase sentence "correcthorsebatterystaple" represent over 100 bits of entropy?

Improve this question
$\endgroup$
8
  • $\begingroup$ this article might be a good place to begin $\endgroup$
    – hunter
    Sep 24, 2018 at 12:46
  • $\begingroup$ I've reformatted your question, but note that "I don't get nearly the amount" assumes that you calculate less entropy rather than more entropy. Please fix that if that isn't the case and your entropy calculation seems to overshoot. (2) Please try and format any followup question to the best of your abilities and include enough info so that it doesn't rely on external resources (even if that external resource is xkcd, which presumably will survive another 100 years or so). $\endgroup$
    – Maarten Bodewes ♦
    Sep 24, 2018 at 13:21
  • $\begingroup$ This comic was discussed on security.stackexchange.com; in particular, this answer contains a detailed analysis of the entropy calculations. $\endgroup$
    – Thomas Pornin
    Sep 24, 2018 at 13:52
  • 4
    $\begingroup$ Now I am suddenly terribly curious whether Munroe actually flipped coins or rolled dice to get "correct horse battery staple." Our entire password security system could be flawed! $\endgroup$
    – Cort Ammon
    Sep 24, 2018 at 16:30
  • 2
    $\begingroup$ Of course, due to that widely publicized comic the actual password strength of "correcthorsebatterystaple" is now at most about 4 bits, because if you hypothetically imagine someone saying "okay, let's try brute force to see if it is one of these $2^4$ passwords" it is eminently plausible that the list that follows might include "correcthorsebatterystaple". $\endgroup$
    – hmakholm left over Monica
    Sep 24, 2018 at 21:15

2 Answers 2

Reset to default
23
$\begingroup$

I don't get nearly the amount of entropy stated in the comic.

Interestingly enough the reasoning for the entropy rating are actually justified in the comic by the little boxes which each represent 1 bit of uncertainty.

This means for Tr0ub4dor&3

  • It's estimatated that the word itself "Troubador" comes up in dictionaries which contain about $2^{16}$ words
  • It adds one bit for each of o,a,o of the word to encode whether the letter was replaced or not
  • It adds one bit to decide whether the word was capitalized or not
  • It adds one bit for the ordering of the trailing numeral and special character
  • It adds 3 bits for the unknown numeral, approximating $10$ with $2^3$ instead of $2^4$ which is more accurate
  • It adds 4 bits for the unknown punctuation, ie which of the approximately 16 standard ones it is

This sums up to $16+3+1+1+3+4=28$

For correct horse battery staple the reasoning is that each of the four words is drawn from a dictionary of size $2^{11}$ which means $4\times 11=44$ bits of entropy.

In both cases it can be assumed that the attacker knows the possible choices influencing the entropy estimation and that it's actually a uniformly random decision which word / pick is done.

If you want an even more thorough explanation of this comic, I can only recommend you read the bear's answer on this over on InfoSec.SE.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Also not explicit in the comic: How difficult is it to remember each part of the password? (Versus how much entropy that thing to remember adds.) The "troubador" part is pretty easy and gets you more entropy than other parts. That's 16 bits. The capitalization of the first letter is one more thing to memorize. The 1337-ness of the third is another. Then the fourth is one more. Than the sixth is another. Then wait, was it "or" or "our"? That's a lot to remember for... less than 4 extra bits of entropy. And that makes you way more likely to need a reset or get locked out. Not exactly economical. $\endgroup$
    – Future Security
    Sep 24, 2018 at 14:22
  • 1
    $\begingroup$ "approximating $10$ with $2^3$ instead of $2^4$ which is more accurate" ... 10 seems to be nearer to 8 than to 16, isn't it? $\endgroup$
    – Paŭlo Ebermann
    Sep 24, 2018 at 17:43
  • 4
    $\begingroup$ Ah, I misread your text as saying $2^4$ would be more accurate. $\endgroup$
    – Paŭlo Ebermann
    Sep 24, 2018 at 17:46
  • 5
    $\begingroup$ @KamilDrakari That is indeed the point of the comic. However the overwhelming majority of internet commenters whenever this comic comes up seem to "understand" a different point. A good number believe the 1337speak makes a password one bajillion times stronger. Others say "Ah, but the second method use dictionary words, which are weak. You should try "k0rr3ct ǝsɹoɥ b4TT3ry Zszywka 1235". $\endgroup$
    – Future Security
    Sep 24, 2018 at 18:18
  • 2
    $\begingroup$ @PaŭloEbermann It's also a good idea to make a pessimistic estimate of entropy, too. Plus 3 bits might be too generous, since '1' and '2' are probably a lot more common than the rest. $\endgroup$
    – Future Security
    Sep 24, 2018 at 18:24
2
$\begingroup$

One official way to estimate the strength of a user selected password such as "Tr0ub4dor&3" is to look at NIST recommendations. Granted that this is now deprecated, but the relevant publication was NIST Special Publication 800-63 Version 1.0.2, Electronic Authentication Guideline.

Table A.1 (reproduced below in case of link rot):-

Table A.1

The reasoning behind this table is within the document at $\S$ A.2.1 Guessing Entropy Estimate. NIST therefor estimates that the entropy is 33 bits if we interpolate for 11 characters and use dictionary and composition rules.

The difficulty of assessing the entropy of short sequences, particularly human produced ones is the take away from this question. The two current answers diverge in strength by a factor of 32. If we compare NIST's estimate to Blafasel's original query on 50 bits, the entropy diverges 131,072 times. NIST says of the above, "Readers are cautioned against interpreting the following rules as anything more than a very rough rule of thumb method". True.

Another take away is that very few sites will allow the stronger and easier to remember technique of choice from a word list, such as "correcthorsebatterystaple". The on-line version of the UK government doesn't, no bank I'm aware of does, and stackexchange.com doesn't.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.