4 ms·

> Start with: You don't know the dictionary I used, but have to use one that seems 'good enough' (i.e. a superset of mine, if possible). People are likely to u

by ErrantX 15y ago

> Start with: You don't know the dictionary I used, but have to use one that seems 'good enough' (i.e. a superset of mine, if possible). People are likely to use a standard English dictionary. In my experience (which is exactly within this field) people use a fairly tight subset of the English vocabulary. So I would be quite happy to test for a dictionary of, say, 100,000 words and be hopeful of a good hit rate (note that XKCD says common words, which is easily missed) Our software has a test (which runs about third in its list of tests) which does dictionary combinations up to three words (two words is quite a commonly used password based on our statistics) with a dictionary size of <s>175,000</s>17,500. (Edit: sorry, apparently it is an order of magnitude smaller, I checked with one of the engineers :)) This includes English words plus a few commonly used foreign/slang terms. The hit rate on this is fairly high. (we crack document/windows passwords mainly) You could of course choose deliberately obscure words to invalidate this - but they aren't so easy to remember (so people will tend not to). If someone is going out of their way to secure a password, sure, you're going to hit a brick wall. But what every password scheme tends to forget is the "human factor" whereby people not concentrating on being secure will introduce attack vectors.

darklajid 15y ago
I actually didn't ignore the 'common' limitation (and didn't downvote you - I'm actually interested how you come up with that). Follow-up questions: - What are the first tests, before this 3rd that tests for words? I assume tests for passwords of the first/left variety in the comic? Aren't they cheaper? - 'Up to three words' is reducing the exponent of possible combinations by one. Length/number of words is relevant Edit: Another issue. You say 'people forget the human factor', while you, yourself, propose something like '4 times Hack News with substitutions' as better. How is that including the 'human factor'?
- ErrantX 15y ago
  <scrubbed answer> You know what; it's been so long since I played around with this stuff (it's even a separate company now, that we just consult for) that I'm way out of touch with my thought process :) You're right; there is nothing particularly wrong with the suggestion that makes it intrinsically very weak for most uses. I'd best stop commenting before I make a total mess :) Sorry.
- deleted 15y ago
  [deleted]
d0mine 15y ago
100,000 words x 4 words per password ~ 66 bits of entropy XKCD suggests 2048 words x 4 words per password ~ 44 bits of entropy It could be good enough depending on a use case.
demallien 15y ago
If the dictionary really has 100 000 words, you're looking down the barrel of 52 bits of entropy for a three word phrase In a more likely dictionary of the 5000 most commonly used words in the English language, you still get a three word pass phrase of about 40bits of entropy. Make that a four word passphrase, and you're back up around 52 bits.
- xkcdentropy 15y ago
  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 phrase you need to have at least 35 characters in your 3 word phrase, or about 12 per word. Your password is only as strong as the weakest link. In this case English is easier to brute force than your 100 000 character alphabet. It's simply false to assume that "yes no one three" has 44 bits of entropy because it got randomly selected out of a 2048 word dictionary.
  - demallien 15y ago
    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.
    - xkcdentropy 15y ago
      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%29 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.
bnegreve 15y ago
You can't test 175000^4 = 937890625000000000000 passwords.
- ErrantX 15y ago
  Ahem. This is why I should check my numbers, I'm told it is a 17,500 word dictionary (and we check 3 re-combinations). Sorry about that :S
  - bnegreve 15y ago
    Ah ! Now, I agree that if everyone follow this advice, it's going to be fairly easy to crack every password based on a small set of simple words.

by ErrantX 15y ago

darklajid 15y ago

I actually didn't ignore the 'common' limitation (and didn't downvote you - I'm actually interested how you come up with that). Follow-up questions: - What are the first tests, before this 3rd that tests for words? I assume tests for passwords of the first/left variety in the comic? Aren't they cheaper? - 'Up to three words' is reducing the exponent of possible combinations by one. Length/number of words is relevant Edit: Another issue. You say 'people forget the human factor', while you, yourself, propose something like '4 times Hack News with substitutions' as better. How is that including the 'human factor'?

ErrantX 15y ago
<scrubbed answer> You know what; it's been so long since I played around with this stuff (it's even a separate company now, that we just consult for) that I'm way out of touch with my thought process :) You're right; there is nothing particularly wrong with the suggestion that makes it intrinsically very weak for most uses. I'd best stop commenting before I make a total mess :) Sorry.
deleted 15y ago
[deleted]

d0mine 15y ago

100,000 words x 4 words per password ~ 66 bits of entropy XKCD suggests 2048 words x 4 words per password ~ 44 bits of entropy It could be good enough depending on a use case.

demallien 15y ago

If the dictionary really has 100 000 words, you're looking down the barrel of 52 bits of entropy for a three word phrase In a more likely dictionary of the 5000 most commonly used words in the English language, you still get a three word pass phrase of about 40bits of entropy. Make that a four word passphrase, and you're back up around 52 bits.

xkcdentropy 15y ago
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 phrase you need to have at least 35 characters in your 3 word phrase, or about 12 per word. Your password is only as strong as the weakest link. In this case English is easier to brute force than your 100 000 character alphabet. It's simply false to assume that "yes no one three" has 44 bits of entropy because it got randomly selected out of a 2048 word dictionary.
- demallien 15y ago
  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.
  - xkcdentropy 15y ago
    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%29 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.

bnegreve 15y ago

You can't test 175000^4 = 937890625000000000000 passwords.

ErrantX 15y ago
Ahem. This is why I should check my numbers, I'm told it is a 17,500 word dictionary (and we check 3 re-combinations). Sorry about that :S
- bnegreve 15y ago
  Ah ! Now, I agree that if everyone follow this advice, it's going to be fairly easy to crack every password based on a small set of simple words.