0936: "Password Strength"

[arbyd]

So I want my kids' computers to be set up so that each reboot restores them to a pristine state from read-only media, with nothing saved except bookmarks and passive data. I can't do that with Windows in a reasonable time.

To be honest that's probably a bit too paranoid. But you could still do that in Windows through a Windows VM, say, or outside Windows by having an OS run from a DVD.

With Windows 8 you can virtually do what you're looking for though:

You can do this with XP if you can still find a copy of Microsoft SteadyState. Set up a second partition for the Documents and Settings folder, set disk protection on the system volume, and all is good. This has dramatically reduced the amount of time I spend supporting computers belonging to friends with kids.

[project2051]

During a recent password audit by Google,
it was found that a blonde was using the following password:

"MickeyMinniePlutoHueyLouieDeweyDonaldGoofySacramento"

When asked why she had such a long password, she rolled her eyes and said:
"Hello! It has to be at least 8 characters long and include at least one
capital."

[Kit.]

"Hello! It has to be at least 8 characters long and include at least one
capital."

That's almost as strong as Randall's password. Maybe even stronger (especially if Sacramento is not the only capital the blonde knows).

[Webzter]

For a while, one of my passwords was 'This is a really, really long password!' I'm not sure how secure it is, but that password-checker site says it'd take a desktop computer about 353 octodecillion years to crack.

I used to use a bank that required your online password be between 6 and 8 characters with no special characters. That one really didn't give me warm fuzzies... because you know that's not being stored encrypted (likely in some ISAM database on some mainframe somewhere)

[gmalivuk]

that password-checker site says it'd take a desktop computer about 353 octodecillion years to crack.

As previously discussed, those sites base their calculations on absolutely nothing but the length of the password. You could just type the 26 letters, in order, lowercase and then uppercase, followed by 0-9. That site would probably say it's the most secure password anyone had ever tested, despite that being obvious bullshit.

[J Thomas]

that password-checker site says it'd take a desktop computer about 353 octodecillion years to crack.

As previously discussed, those sites base their calculations on absolutely nothing but the length of the password. You could just type the 26 letters, in order, lowercase and then uppercase, followed by 0-9. That site would probably say it's the most secure password anyone had ever tested, despite that being obvious bullshit.

I find this all confusing. Somebody wants to guess your password at random, without knowing anything much about you. Presumably they will check 1111 and 11111 and asdf and some things like that. They will check permutations of your name and the site name. They will check things that lots of people use. Hello thankyou thegreatest etc. How likely will they check:

abcdefghijklmnopqrstuvwxyz0123456789?

If they check that then they're likely also to check

abcdefghijklmnopqrstuvwxyz123456789 &
abcdefghijklmnopqrstuvwxyz1234567890

Are they likely to get on a kick that way and also check

abcdefghijkmnopqrstuvwxyz234567890 ?

no l and no 1. noel and no-one. Are they going to suppose people will use variations on this 36-letter code and check every 2-letter deletion? What are the odds? How can we begin to calculate the odds?

Randall's original point was that human beings don't want to memorize collections of random strings. So we make patterns. The challenge is to make patterns that crackers will not choose to try. Since they are patterns there is always the chance that somebody will use that pattern and cut down the odds. But there are lots of patterns available, and getting something we can remember ourselves is primary.

So if you can easily remember a combination of 4 words out of 50,000 words you commonly use, and the context where that combination is appropriate, and if an attacker knows the right 50,000 words, his chance of getting them in the right order is 50,000^4.

625*10^16.
6.25*10^18

That's pretty good, and if it's easy to remember that's a great big plus.

Meanwhile some of the attackers will be trying variations on

abcdefghijklmnopqrstuvwxyz1234567890

instead. What really makes one password pattern weak is when everybody does it, so the attackers all concentrate on that one.

[gmalivuk]

that password-checker site says it'd take a desktop computer about 353 octodecillion years to crack.

As previously discussed, those sites base their calculations on absolutely nothing but the length of the password. You could just type the 26 letters, in order, lowercase and then uppercase, followed by 0-9. That site would probably say it's the most secure password anyone had ever tested, despite that being obvious bullshit.

I find this all confusing. Somebody wants to guess your password at random, without knowing anything much about you. Presumably they will check 1111 and 11111 and asdf and some things like that. They will check permutations of your name and the site name. They will check things that lots of people use. Hello thankyou thegreatest etc. How likely will they check:

abcdefghijklmnopqrstuvwxyz0123456789?

However unlikely that may be, it's still orders of magnitude more likely they'll check that before they check a truly random 36-character alphanumeric sequence. And the problem with most password checker sites is that they only look at the length and the likely set of characters from which it was drawn. It assumes you have a random password (because if it doesn't recognize a dictionary word in there somewhere, it assumes it must be completely random) from a set of 36^36 passwords. But you don't. You just have all the letters in order and then the digits in order.

If they check that then they're likely also to check

abcdefghijklmnopqrstuvwxyz123456789 &
abcdefghijklmnopqrstuvwxyz1234567890

Are they likely to get on a kick that way and also check

abcdefghijkmnopqrstuvwxyz234567890 ?

no l and no 1. noel and no-one. Are they going to suppose people will use variations on this 36-letter code and check every 2-letter deletion? What are the odds? How can we begin to calculate the odds?

They'll still probably start with the first one (with all the letters and numbers in order), and my point was merely that such a password would be incorrectly reported as extremely secure by a dumb algorithm that merely makes sure it's not from a dictionary.

But to answer your question, if I know you started with this sequence and then deleted two letters from it, I've narrowed down your password to being one of 630 possibilities, or between 9 and 10 bits of entropy. If I know you deleted *some* number (possibly zero) of characters from it, I've still narrowed it down to only 2^36 possibilities, or 36 bits of entropy. For that level of security, you'd be far better off just memorizing three words from a list of 4096, as it's probably a hell of a lot easier to do that than to remember where all the gaps are for your some-number-of-deletions system.

[ahammel]

Sorry if this has been addressed before (I read through the thread and didn't catch it), but I was wondering about the theoretical problem with the random passphrases approach. Say you're drawing words at random from a list of 4096 words. That gives you ~2.8e14 possible passwords = 48 bits of entropy (by my count). But when I do this, I don't always choose the first password that I get. Something like "prove laugh deal piano" isn't very memorable, so I'll try again until I get something that sounds like a phrase. If that takes me four tries per password on average then the real number of possible passwords ~7.0e13 = 46 bits of entropy.

Ok, so maybe that's not such a big deal, but how would J. Random Attacker take advantage of it? Even given the worst-case-scenario assumption that he has my word list and knows how I use it, how could he trim the password space by rejecting all the non-memorable ones?

[cjmcjmcjmcjm]

Remember, if the passwords are properly hashed, the cracker won't know how long the password is.

[Yakk]

Ok, so maybe that's not such a big deal, but how would J. Random Attacker take advantage of it? Even given the worst-case-scenario assumption that he has my word list and knows how I use it, how could he trim the password space by rejecting all the non-memorable ones?

This would require modelling "how memorable a password is", which is often harder than simply checking all 4 passwords.

In general, on defence, you should assume that the attacker can read your mind -- when you pick 1 password out of 4, the attacker gets to determine what you'd pick 'for free', simply because you don't know how bad your choice is. So if you examine 1000 passwords and pick one, your password is 1000x weaker.

On the attacker side, this kind of attack happens (where you take something the other person did "at random" and realize it is actually pretty predictable) -- you bias your attacks to replace i with 1, or whatever else you gather from statistical analysis of huge password data sets, and bias your search to attack those kind of passwords. This makes it more likely to reach the password, and you don't even have to always know the ways in which this saves you time.

In short: don't assume you are creative when trying to work out how hard it is to crack your password. Assume a myriad of others are using the same type of password. Because you really don't know how creative you are, and you will almost certainly over estimate how creative you are. Rely on reasonably strong random number generators only, and don't assume your creativity ads anything to your password strength.

[dllthomas]

I tried to set my password here to

mimics ponies jibbed fresh Crimea

but the board said it was too long.

This saddens me, first because it means I have to use ugly passwords, and second because the check is unnecessary, and/or (weakly) implies that passwords are being stored unhashed (which is bad).

It makes me happy because I get to share the string, though, which amused me.

[J Thomas]

If they check that then they're likely also to check

abcdefghijklmnopqrstuvwxyz123456789 &
abcdefghijklmnopqrstuvwxyz1234567890

Are they likely to get on a kick that way and also check

abcdefghijkmnopqrstuvwxyz234567890 ?

no l and no 1. noel and no-one. Are they going to suppose people will use variations on this 36-letter code and check every 2-letter deletion? What are the odds? How can we begin to calculate the odds?

They'll still probably start with the first one (with all the letters and numbers in order), and my point was merely that such a password would be incorrectly reported as extremely secure by a dumb algorithm that merely makes sure it's not from a dictionary.

But to answer your question, if I know you started with this sequence and then deleted two letters from it, I've narrowed down your password to being one of 630 possibilities, or between 9 and 10 bits of entropy.

Sure, but if you know that much you probably know the password. Why would you know that I started with a particular sequence and then deleted two letters from it? Did somebody tell you that much?

You might guess

abcdefghijklmnopqrstuvwxyz1234567890

but you'll be right more often if you guess

111111

or

12345

or

asdfg

. If you don't know the pattern I'm working from then there are lots of patterns and they all count toward the entropy, except the ones you guess first are the weakest.

If I know you deleted *some* number (possibly zero) of characters from it, I've still narrowed it down to only 2^36 possibilities, or 36 bits of entropy. For that level of security, you'd be far better off just memorizing three words from a list of 4096, as it's probably a hell of a lot easier to do that than to remember where all the gaps are for your some-number-of-deletions system.

If you don't know which words are in my list of 4096 words, then it's a lot more secure than if you do.

So if you have 1000 of my passwords for other sites, that would give you something less than 3000 of the words on my list, which would give you a fighting chance at cracking this one. But that requires you to guess *my* password. You can't just guess random users' passwords because I'm the only one who uses that system. By the time you make 2^20 wrong guesses for my account, there's a good chance something will happen. I hope.

[TheGrammarBolshevik]

This saddens me, first because it means I have to use ugly passwords, and second because the check is unnecessary, and/or (weakly) implies that passwords are being stored unhashed (which is bad).

Just for the record, phpBB stores passwords hashed.

[gmalivuk]

If you don't know which words are in my list of 4096 words, then it's a lot more secure than if you do.

Sure. It's always more secure if the attacker knows less. But to make a good password, you should make one that's still secure even from someone who knows the method you used to generate it. More specifically, assume your attacker knows everything about your password except for the results of your random number generator.

[Yakk]

If you don't know which words are in my list of 4096 words, then it's a lot more secure than if you do.

You do not know that it is "a lot more secure".

Maybe the words you picked are quite common, and used in as the only words in over 50% of passwords. Then not knowing the words adds an entire bit of entropy to your password security (or less).

If you rely on vague things like "you don't know how I picked blah", then you are relying on what (in the experience of people looking at password algorithms) is a stupid thing to rely on.

Security through obscurity has a long tradition of seeming far stronger than it actually is to the fools who rely on it -- I say fools, first because the odds are that a given person is a fool about how strong security is (security is hard), and recursively because experience has shown that obscurity is foolish to rely on. And security through "having a bunch of people figure out how I screwed up by being transparent in what I'm doing" ends up being ridiculously stronger past a certain scale.

Your best bet is to make your password secure even if they know everything about it besides the random number generator portion, and use a technique that is secure even through it is famous -- that way, people will have checked that your security is actually strong.

Hence the advantage of the correct horse battery staple algorithm. It is famous enough that a bunch of people with clues have attacked it and found it strong. The only gotcha is making sure that your selection of words is actually strongly random.

[J Thomas]

Your best bet is to make your password secure even if they know everything about it besides the random number generator portion, and use a technique that is secure even through it is famous -- that way, people will have checked that your security is actually strong.

Well, yes. Once you throw out everything that contributes to security except the random number generator, and you assume that the attacker does not know the RNG seed you used, then you can calculate how secure it is and figure your estimate is a good one.

But when you need multiple passwords, then you have to somehow store them and any place you store your passwords outside of your own head is another weakness.

Hence the advantage of the correct horse battery staple algorithm. It is famous enough that a bunch of people with clues have attacked it and found it strong. The only gotcha is making sure that your selection of words is actually strongly random.

I agree it's a good one, not least because it provides reasonable security while allowing easy mnemonics. If you have a secure password that you can't retrieve yourself, what good is it? That's too secure.

Anyway, Randall pointed out an excellent way to get passwords, in a comic I can't easily track down now. Set up a website that a lot of people will register for. Many of them will use the same password for your site that they use for everything else. No matter how crypto-secure that password is, nobody can keep the owner from handing it to you.

Of course, the more total passwords you get the better you can estimate how many users are using each different password strategy, assuming the strategy is visible from the password. You can estimate the frequency of leet-speak in passwords, and some other things.

[gmalivuk]

and any place you store your passwords outside of your own head is another weakness..

Something like KeePass adds so little weakness that determined attackers would still be best off going for the pipe wrench method. Or a strong hashing algorithm if you want to be able to access your passwords from more than just the computer where you installed KeePass.

But of course the whole point of the comic was that this is a way to generate easily remembered strong passwords.

[cjmcjmcjmcjm]

http://gizmodo.com/5881010/dont-change- ... ts-Poopery

You're most likely not Jack Bauer or a national president, so people really won't want to steal your password for much else than free money. If you aren't stupid with your info, mandatory password changes every 6 weeks are unnecessary.

[willpellmn]

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

The short answer is that it turns out that Entropy is a measure of information.

How many digits are there from 0 to 9? How many bits does it take? How about for 3 digits? See how a digit is about 3 bits of information?

There are ~2k common words. So it takes ~11 bits to describe which common word you are using. (If your selection isn't uniformly random, you can huffman encode your "which word is it" and get the average number of bits of entropy below 11 bits.)

Afraid I still don't follow. I'm not in college or anything, so most of the science articles on Wikipedia are way over my head; I can't fathom the jargon involved (and sadly the Simple English version, when one exists at all, is a serious overcorrection). As far as I can tell, there is a 1/10 chance of guessing a given digit, a 1/26 chance of guessing a number, a 1/36 chance of guessing an alphanumeric character, etc. So I don't see how 3 digits is "three bits of information"; I see it as about 36 to the 3rd power possible outcomes, of which the password-cracker is equally likely to hit any one on any given attempt. Thusly, the "average" length of time would be the middlemost value of that range; if it can test 100 guesses a second and is looking for only numbers in a 3-character string, it guesses all 1000 possible values in 10 seconds, and the "average" is 5.5 seconds, but it's equally likely to take 2 seconds or 8.7 or any other value in the range. (This is why I don't put a lot of stock in averages.)

[gmalivuk]

See how a digit is about 3 bits of information?

So I don't see how 3 digits is "three bits of information"; I see it as about 36 to the 3rd power possible outcomes

No, each digit (0-9) has about 3 bits of entropy, so three of them have about 9 (closer to 10, really, since 3 digits has 1000 possibilities and 2^10 is 1024).

If you're talking about all alphanumeric characters, you're right that you have 36^3 possibilities. 36^3 is between 2^15 and 2^16, so we can say this has 15 or 16 bits of entropy. Adding one bit of entropy is equivalent to doubling the number of possibilities, so 15 bits isn't just 50% more possibilities than 10 bits, but actually 32 times as much.

[Yakk]

A digit from 0 to 9 can be represented as one of the following bit patterns:
0000: 0
0001: 1
0010: 2
0011: 3
0100: 4
0101: 5
0110: 6
0111: 7
1000: 8
1001: 9

As you can see, you distinguish between all of the digits from 0 to 9 using 4 bits of information. In reality, it only takes a smidgin more than 3 bits (3.32 to be more exact -- you can encode 3 digits in 3*3.32 = 9.96 bits, aka 2^10 =~ 1000).

The Physics concept Entropy, as it turns out, can be modeled as Information "Entropy" (aka, Shannon Entropy), which can be measured in bits. So in information theoretic land, bits of entropy refers to how many bits you'd require to describe the cases. If we talk about the average entropy of a given distribution, we allow the encoder to bias the selection of the space such that more common elements require fewer bits, thus lowering the average amount of entropy that a given distribution of possibilities requires to describe.

This concept ends up being arithmetically useful, because the cross product of possibilities (or, everything that the distribution of possibilities A and everything that the distribution of possibilities B allows, concatenated with a separation mark) ends up corresponding to adding entropy values of the two distributions, assuming that the distributions are uncorrelated. Naturally it has other nice properties above and beyond this.

Making sense?

[gmalivuk]

To more clearly connect the last two posts, saying one digit has three bits of entropy assumes a uniform random distribution, so each digit is equally likely. This means that we can't save any space by using information about what digits are more likely.

If, instead, we're talking about groups of 5 letters, a completely random (uniform) distribution allows for 26^5 cases, which is between 2^23 and 2^24, so we say a random 5-letter password has 23.5 bits of entropy. But if you want it to be an actual English word, you've got only a bit more than 2^14 to choose from (from a Scrabble list, anyway). So if I have the additional information that this string of 5 letters is legal to play in Scrabble, we can encode the information differently (say, by numbering the list alphabetically) and encode the entire space of possibilities with 14 bits.

[Yakk]

For more fun, imagine if we know there is a 90% chance it is a scrabble-legal word, and a 10% chance it isn't.

We then encode the first bit to say "is it scrabble legal". If it is, we encode the next 14 bits as the scrabble word. If isn't, we use the next 24 bits to encode the exact word.

This has an average entropy of 1+(.9 * 14 + .1*24) = 16, much better than the 24 average entropy of an utterly random word.

You'll note that this average entropy is an average number of bits, and does not correspond to any naive average "length of time to crack it" or the like, because we are taking an average on an exponential scale... 2^16 checks is neither the mean, mode or median number of passwords we'd check to crack that password. (Median is about 2^14 or so, assuming we pick bits at random until we have a valid encoding -- in comparison, the scrabble word would require an median of 2^13 passwords to check).

[rektide]

hi xcase forum goers. i built a random-word password picker[1] for Scrabble players. it picks four words from the three[2] and four[3] word dictionaries at http://www.scrabble.org.au.

LamsBitNeukSous may not exactly be instantly familiar, but i figure any aspiring scrabble players will get regular and helpful practice our of typing it. this of course means you l33t need to leave your 1Password/LastPass/&all juju at home. yet to come is a web-page form of the code that opens iframes against Onelook or some such dictionary portal to tell you wtf the words you're looking at mean, cause that was kind of the point of -0936, human comprehension.

my impl is in Node.JS and uses some a'right promises stuff.

it looks to have just under 51 bits of entropy:

Code: Select all

wc -w threes.txt fours.txt;echo;echo $((6746**4)) $((2**51))
 1292 threes.txt
 5454 fours.txt
 6746 total

2071025028522256 2251799813685248

[1] http://cgit.voodoowarez.com/wordspassed ... ordspassed
[2] http://www.scrabble.org.au/words/threes_f.htm
[3] http://www.scrabble.org.au/words/fours.htm

[dllthomas]

This saddens me, first because it means I have to use ugly passwords, and second because the check is unnecessary, and/or (weakly) implies that passwords are being stored unhashed (which is bad).

Just for the record, phpBB stores passwords hashed.

Good to know. Any reason you can think of for the length check, then?

[clockworkbookreader]

16 pages of geek mental masturbation.

I'm so glad I joined this forum!

[faeastflip]

The only downside would be how long this would take to type on an iPhone, especially if you miss one letter and have to do it all over again.

[Yakk]

Yes, iPhone software that doesn't let you examine password fields as you type sort of sucks.

[Fire Brns]

The perfect password is thi-ASSUMING DIRECT CONTROL-

[ahammel]

The only downside would be how long this would take to type on an iPhone, especially if you miss one letter and have to do it all over again.

Speaking as an iPhone owner who's implemented this, it's not so bad. I think I made more mistakes with my weak "change out some letters for symbols" password. With the four words approach you get to stay on the qwerty keyboard instead of spending a lot of time thinking "dammit, where the hell is the # key?".

Not that I, uh, have any passwords with a # in them.

[runnerup]

In case anyone is interested, the "horse battery staple" example from comic #936 is used in this weeks issue of The Economist (article: "A security patch for your brain").

I don't know how much of an overlap there is between the XKCD audience and the Economist audience, though.

[spi]

In case anyone is interested, the "horse battery staple" example from comic #936 is used in this weeks issue of The Economist (article: "A security patch for your brain").

When I saw that I chuckled as I immediately remembered this comic. The article is available here which also links to another article in this issue about recent research in password usage that was pretty interesting.

[willpellmn]

As you can see, you distinguish between all of the digits from 0 to 9 using 4 bits of information. In reality, it only takes a smidgin more than 3 bits (3.32 to be more exact -- you can encode 3 digits in 3*3.32 = 9.96 bits, aka 2^10 =~ 1000).

Ahah! Thank you. (Lol, it only took me what, 6-8 months to get an answer. The printout of the comic is still on my cubicle wall, though I've largely stopped paying attention to it, as I now have a photo of a very happy dog which is more eye-catching.)

[MichaelRpdx]

Are you sad or glad correcthorsebatterystaple was not among the LinkedIn stolen passwords?

[JudeMorrigan]

Slate wrote an article on phrase-based passwords that explicitly references the XKCD comic:

http://www.slate.com/articles/technolog ... ique_.html

The comments section, unsurprisingly enough, has some ... interesting logic in it. My favorite was the lady said that she was inspired by the XKCD comic to base her passwords on misspelled l33tified words.

[slogmeister]

When I used the formula given in Wikipedia (http://en.wikipedia.org/wiki/Password_strength), I came up with the following:

Formula: H=Log2 N^L
Where H is entropy, N is typable characters on keyboard or number of symbols, and L is length of password

Tr0ub4dor&3
N=94
L=11
H=72 (not 28)

correcthorsebatterystaple
N=94
L=25
H=164 (not 44)

correcthorsebatterystaple (using Diceware)
12.9+12.9+12.9+12.9=51.6 (not 44)

Am I missing something? It doesn't seem logical that you can add up the entropy for each individual symbol within its own subset of all symbols (i.e. T is 1 of 26 vs. 1 of 94) to get the total entropy of the password. Doesn't the password have to be considered as an atomic entity for entropy calculation?

[ahammel]

Am I missing something?

Yes. The entropy calculation you use is for random strings of characters, which "Tr0ub4dor&3" is not. A password like "0[l;/O`QKMj" has 72 bits of entropy, but "Tr0ub4dor&3" has much less—and is much easier to crack—because it's based on a dictionary word.

[ConMan]

When I used the formula given in Wikipedia (http://en.wikipedia.org/wiki/Password_strength), I came up with the following:

Formula: H=Log2 N^L
Where H is entropy, N is typable characters on keyboard or number of symbols, and L is length of password

Tr0ub4dor&3
N=94
L=11
H=72 (not 28)

correcthorsebatterystaple
N=94
L=25
H=164 (not 44)

correcthorsebatterystaple (using Diceware)
12.9+12.9+12.9+12.9=51.6 (not 44)

Am I missing something? It doesn't seem logical that you can add up the entropy for each individual symbol within its own subset of all symbols (i.e. T is 1 of 26 vs. 1 of 94) to get the total entropy of the password. Doesn't the password have to be considered as an atomic entity for entropy calculation?

There are two things that you're missing - one is that Randall's calculations here are quite approximate - he's willing to drop decimal points on numbers in favour of using lower bounds that are easier to calculate (and to draw as little boxes). The second is more important, and it's in terms of what the underlying values are in the calculation.

The entropy of the password is dependent on the system used to choose the password. So if you got, say, correcthorsebatterystaple from a program that spits out random strings of lower case alphanumeric characters, then the size of its "keyspace" is 26 and its length is 25, giving an entropy of about 116. If the keyspace includes upper case letters as well, that doubles its size to 52 giving an entropy of 142. Including the full set of basic ASCII characters to get the N=94 you're using results in the 164 you had, but if you can produce "correcthorsebatterystaple" from a uniformly random selection of 25 ASCII characters then can I please get you to try for Shakespeare next because that's just not going to happen. But this password wasn't produced from that, it was produced from a keyspace of about 2000 dictionary words, from which we've picked 4, so N=2000 and L=4 giving H=43 or so as per the comic.

Now let's look at "Tr0ub4dor&3". The fact is, hackers *know* what systems people use to produce passwords these days. So yes, again, if the means of producing this password was from a random selection of characters, then your entropy value is just fine. But it's not. Here's how people select their supposedly strong passwords, and how many bits of entropy each step gives:

1. Pick a word from the dictionary. For fairness, let's use the same dictionary we got correcthorsebatterystaple from, so it's got 2000 words or about 11 bits of entropy.
2. Decide whether to capitalise the first letter or not. That's a simple "yes/no" choice, so it adds 1 bit of entropy (practically no-one capitalises a random letter, and in some cases you can probably remove this bit because the password is required to have a capital letter in it).
3. Make some l33t-style subtitutions. In the comic, Randall seems to suggest that this adds about 3 bits of entropy, which would depend on which letters in the word could be substituted and whether there are multiple choices for each substitution, so I'd probably add an extra bit there myself but that doesn't make a massive impact on the final result.
4. Add a symbol and a digit. Where do you add them? Almost certainly at the end. The digit adds another 3 bits of entropy, and the symbol 4, plus 1 more bit for deciding which one to put first.

As I said, hackers these days have a deep understanding of how people choose passwords, and they know that the above system covers probably about 90-95% of all passwords, even those that allegedly meet the requirements for a "strong" password. Again, if they were trying to attack the password by throwing every possible string of 11 characters, then they'd have to try 2^72 different combinations, a pretty crazy amount. But by only using passwords generated from the above 4 steps, their search drops down to 2^28, which as Randall points out is crazily easy for modern cracking methods.

As for the Diceware entropy, it looks like they're using a bigger dictionary than Randall, at 7,500 words, which gives their bigger value for the entropy.

[Yakk]

Another way of looking at it. If "Tr0ub4dor&3", or anything like it, was actually produced by a random alpha-symbolic-numeric password generator, you'd be extremely surprised.

How surprised? Well, your bits of entropy for an 11 character long string was 72. The bits of entropy that the algorithm Randall presumed generated the string is 28. 72-28 = 44, or the odds that the random string generator would generate anything that looks like a relatively common english word with that kind of subsitution and extra characters is about one in 2^44, or one in 16 Trillion. Or, if you ran the random character generator at 1000 passwords per second for 60,000 years, approximately one of them would look like a common English word with that kind of substitutions.

When you look at the bits of entropy in the generated space for a password generator, it is true that it could generate a really easy to guess password. The random password generator could generate "1234567890". But the degree of unlikeliness that this actually happens is so ridiculously high that you can neglect it.

Similarly, if you see such a highly patterned password, you can be nearly absolutely certain that it was generated by a really simple password generating algorithm. If someone swears that they used a strong password generator to make it, you can be nearly absolutely certain that they lied or are mistaken, or they cherry picked it from a huge list of generated passwords. The odds really are that far against it.

The same goes for "correct horse battery staple".

The safe (and correct) way to deal with password generation algorithm security turns out to be to presume that the attacker has your password generation algorithm (or, in in most cases identically, your password generator algorithm generator algorithm), and from that show that despite this advantage, the attacker still cannot guess your password. This both gives a practical lower bound (while you could generate a password that they guess randomly the first time as above, you can quantify how unlikely that is), and it reflects the fact that people who have used "clever" trickses have time and time again proven to be less clever than they thought they where.

So you give up the password generator algorithm. The algorithm consists of picking 4 words from the 10k most common English words, and arranging them in that order. 10k^4 =~ 53 bits. We then allow the user to generate say 4 passwords, and reorder the words, which trims off 6.6 bits, leaving 46.5 bits of entropy. If we use the 1k most common English words and don't allow rearrangement and multiple tries, we get 1k^4 =~ 39.8 bits.

We could allow introducing connections between the words. Ie, "The Correct Horse sees a Battery with a Staple in it". This makes the password no weaker -- but quantifying how "clever" and "unique" the extra words are is difficult, so we simply say that they add at least 0 bits of entropy, and we get a pass phrase that might be easier to remember than the raw words.

[J Thomas]

There is something wrong with a system in which a single user generates 2^28 wrong passwords, and there are no consequences.

Just saying.

I'm not sure what a system would look like that didn't have anything wrong with it, but this is wrong.