Live data from Hacker News

Xkcd Password Generator

preshing.com

281–290 of 299 posts

Re: Xkcd Password Generator

#281
post #119
post #104

Earlier quoted context omitted.

Yes, though the number of additional bits you get from increasing the size of the dictionary decreases fast. E.g. suppose English and German have the same number of words, then using both only gives you one more bit per word. (Actually, slightly less since some words exist in both languages. Like `hell'.)

>Yes, though the number of additional bits you get from increasing the size of the dictionary decreases fast. Well, sure -- but once you're at around two or three languages, you get to imagine that the attacker doesn't know what languages you're using. If I use English, Japanese, and Spanish, I can figure on the attacker needing to check the Germanic (English, Dutch, German), Romance (Spanish, French, Italian), and A…

>Jargon helps too, and proper names. "dijkstra bicycle entonces boojum daihinmin"

Instead of that, just add an extra common word: "correct horse battery staple bicycle".

Re: Xkcd Password Generator

#282

If you're bi-lingual in a non-european language, transliterating obscure phrases from the other language could work well. For example, the poetic title திரிகூடராசப்பகவிராயர் would transliterate to thirikUdarAsappaKavirAyar. Add some subs & punctuations and I'm done - very rememberable (at least for me) :).

Assuming there are 1024 languages in the world you added 10 bits of entropy. That can be achieved adding an extra common word.

Re: Xkcd Password Generator

#283
post #194

Watch out for sites that only use the first 8 characters of your password (no matter how long it is).

Or those that ignore case... I've come across a few popular ones that do that!

Case is only 8 more bits assuming you randomly assign case to all of your letters. More likely it will be only one more bit. Then requiring an extra character is equally good.

Re: Xkcd Password Generator

#284

It's a good idea, and would work well, if only websites would let me choose passwords longer than 12 characters!

Randall is saying exactly that: Through 20 years of effort, we've successfully trained everyone to use passwords that are hard for humans to remember, but easy for computers to guess

Re: Xkcd Password Generator

#285

Earlier quoted context omitted.

Any narrowing of the search space will most definetely reduce entropy.. by how much is calculatable but I don't have the time nor language statistics right now to do it.

I'm not sure the technical meaning of entropy in this context, but personally, I would offset the narrowing effect of "restrict to grammatical phrases" by adding uncommon words. "Besotted ophthalmoscopes gambol indicatively" forms a coherent, if silly, word picture for me, so I think I can remember it. As far as possible combinations, my vague memories of linguistics 1001 include the idea that this is one of the esse…

> I'm not sure the technical meaning of entropy in this context

Roughly, it's the logarithm (base 2) of the number of guesses that an optimal password guesser would have to guess in order to guess your password. It's a measure of how unknown your password is.

> it has so many possible combinations, that every speaker is continually creating sentences that have never before been uttered.

Yes, this is why all of the suggested alternatives like "choose a line from a popular song" are so much less secure.

Re: Xkcd Password Generator

#286

Earlier quoted context omitted.

Any narrowing of the search space will most definetely reduce entropy.. by how much is calculatable but I don't have the time nor language statistics right now to do it.

You can modify slightly your sentence without loosing entropy "married greatly snake battle" becomes "a married great snake will battle". "correct horse battery staple" becomes "correctly the horse inserted the battery staple" Note that the extra words add little or no entropy, at the cost of increased length.

This is a good idea!

You do lose a little entropy that way: you've merged "great" and "greatly", and "correct" and "correctly", suggesting that your modification process considers adjectives and their corresponding adverbs as equivalent. If those examples are typical, that removes one bit of entropy. But you've probably added more than that back in, if your choices of "a", "will", "the", and especially "inserted" are unpredictable. (Alternatives might include "the", "would/did/could", "a", and "removed".)

Re: Xkcd Password Generator

#287

Earlier quoted context omitted.

This is simply incorrect. If you assume you really do have 100 000 "characters" in your alphabet this is correct. However, your alphabet follows a certain pattern: It's English text. At that point its easier to brute force the individual characters. English text has about 1 to 2 bits of entropy per character. Lets assume 1.5 bits per character on average. That means that to really get 52 bits of entropy for a 3 word…

Yeah, no. If I have a dictionary of 100000 words, then each word represents about 17 bits of entropy. If I have three words, that makes 3 x 17 = 51 bits of entropy.

You deny the fact that English text can be attacked separately from your dictionary. English text is very predictable, for example e is much more common and q is almost certainly followed by u.

I'm not making this up on my own either. Please check out http://en.wikipedia.org/wiki/Entropy_%28information_theory%2.... Let me quote the important part: The entropy rate of English text is between 1.0 and 1.5 bits per letter,[1] or as low as 0.6 to 1.3 bits per letter, according to estimates by Shannon based on human experiments.[2]

Consider the following example: You have a wordlist of 100 000 words. It seems only normal that log(100 000)/log(2) is equal to 16.6 bits of entropy. Now consider you take three words out of that list completely at random. You get the words "a no we". Assuming 16.6 bits of entropy per word you do indeed have to search through a space of 49.8 bits but only if you attack that via the dictionary

It is clear that in this case you can do a different attack. Instead of brute forcing the words you can brute force the characters on their own with a search space of a-z and space. This equals log(27^7)/log(2) or 33.2 bits. A lot less than 49.8 bits estimated when only considering a dictionary approach. In reality English text is so predictable that you don't have to search even close to 33.2 bits of entropy if you brute force it with an algorithm that is aware of English text. Assuming Shannon's 1.3 bits per character estimate this password has 9.1 bits of entropy.

I understand that this is an edge case with very short words. But I choose that to try and show that there are other ways to attack the password by using a 27 character dictionary. This is cold hard math and therefore much easier to accept than the magic entropy estimation of englist text. Once you see that this way can reduce your entropy calculation it's not that hard to accept that there might be more ways to reduce the entropy ever further.

Re: Xkcd Password Generator

#288

Earlier quoted context omitted.

Yeah, no. If I have a dictionary of 100000 words, then each word represents about 17 bits of entropy. If I have three words, that makes 3 x 17 = 51 bits of entropy.

You deny the fact that English text can be attacked separately from your dictionary. English text is very predictable, for example e is much more common and q is almost certainly followed by u. I'm not making this up on my own either. Please check out http://en.wikipedia.org/wiki/Entropy_%28information_theory%2... . Let me quote the important part: The entropy rate of English text is between 1.0 and 1.5 bits per lett…

1) the predictability of the distribution of characters in the English language has nothing to do with this type of password - the symbols aren't characters, but words. 2) that figure of entropy per character of 1.3 bits per character only applies to English text, and the figure is low because there are a bunch of small words, like "and" and "the" that are regularly repeated. The entropy per character for words containing 6 letters or more, not arranged in sentences is a lot higher, like about double if I recall correctly. So sure, just as I can expect to get brut-forced if I choose a pin of 0000, I can get brute forced if I choose a passphrase of 'and the in'. Good luck forcing "queens examine faulty charges" though.

Re: Xkcd Password Generator

#289

Earlier quoted context omitted.

Yeah, no. If I have a dictionary of 100000 words, then each word represents about 17 bits of entropy. If I have three words, that makes 3 x 17 = 51 bits of entropy.

You deny the fact that English text can be attacked separately from your dictionary. English text is very predictable, for example e is much more common and q is almost certainly followed by u. I'm not making this up on my own either. Please check out http://en.wikipedia.org/wiki/Entropy_%28information_theory%2... . Let me quote the important part: The entropy rate of English text is between 1.0 and 1.5 bits per lett…

[deleted]

Re: Xkcd Password Generator

#290

Earlier quoted context omitted.

You deny the fact that English text can be attacked separately from your dictionary. English text is very predictable, for example e is much more common and q is almost certainly followed by u. I'm not making this up on my own either. Please check out http://en.wikipedia.org/wiki/Entropy_%28information_theory%2... . Let me quote the important part: The entropy rate of English text is between 1.0 and 1.5 bits per lett…

1) the predictability of the distribution of characters in the English language has nothing to do with this type of password - the symbols aren't characters, but words. 2) that figure of entropy per character of 1.3 bits per character only applies to English text , and the figure is low because there are a bunch of small words, like "and" and "the" that are regularly repeated. The entropy per character for words cont…

I am merely suggesting that the entropy can be less than what is estimated by looking only at the dictionary.

Re 1: words still consist of characters Re 2: Certainly correct, but to ignore the possibility of English words having less entropy than it appears at first is odd given the patterns English words often follow.

I'm interested in reading more about those entropy estimations, can you recall where you read about it? According to Applied Cryptography Shannon states that entropy per letter decreases as the text grows. Shannon estimates 2.3 bits per letter for chunks of 8 letters but it drops down to between 1.3 and 1.5 bits per character for 16 character chunks.

Applied Cryptography cites a paper by Shanon called "Predication and Entropy in Printed English" in the Bell System Technical Journal from 1951. I Have not personally read it yet but will try to find it in the near future.

Post reply on HN