Hacker News Reader

Comment by ravi-delia | Hacker News Reader

Grammatical English is an extremely restricted subset of all strings of characters. You can actually see for yourself that it's in the ballpark of a bit by going to a book, covering up a line, reading the context, and trying to guess the next letter one at a time. I get it 3/4 times, and would probably be down to 1/2 if I had to do it the right way.

Consider the difference in entropy between this totally randomly generated password, consisting of 4 words each from a pool of 100,000:

Correct Horse Battery Staple 4lg(100000) = 33

And this one of the same length where each character was chosen from a bank of 68:

VIW&jubiHZUgBrFA8PI9Vy1E(%G 28*lg(68) = 170

View on HN

French dude gets in trouble with the law and has his encryption cracked. Hackernews goes into an extended (and extremely interesting) thread about the entropy content of grammatical English. Probably not that different in terms of entropy content per character, though.

That being said I don't understand your calculation of 4lg(100000). That seems like it can't possibly be correct. For starters it is entirely independent of the entropy content of the words in the dictionary. I could have 100000 strong random passwords of 1000 characters each in my dictionary. Could you explain this a bit, please because there's obviously something I'm missing?

Edit: Aah I think I get it - the assumption is both me and the attacker know the dictionary so the entropy content of the words doesn't matter, the only thing that matters is the joint probability distribution of the combinations I'm choosing. Is that correct?

Oh yeah, my assumption is that it's 4 words chosen from a 100,000 word dictionary. I honestly have no idea if it's a reasonable estimate but it stuck in my head from XKCD's original correct-horse-battery-staple comic. Of course in real life an attacker won't know necessarily the distribution you've pulled your password from, but by using the exact distribution in your calculations you have an ironclad lower bound.

Diceware uses 7776 word dictionary, xkcd uses a shorter dictionary.

My God, where on Earth did I get 100,000? I mean that's a lot of words, plausibly more than I will ever hear. And how did it just cancel out anyway so I got roughly the right entropy? This will frustrate me until I understand how I fucked it so totally

> Correct Horse Battery Staple 4 lg(100000) = 33

I think you mean 66. More realistically, 52 for Diceware's 7776-word dictionaries, or 44 for XKCD's 2000 common words.

Yep, I somehow internalized that there were 100,000 words (on reflection, I couldn't name a tenth of that in one sitting), but also halved the result, and the error canceled out a bit. Terrible.

Reply on news.ycombinator.com