5 ms·

https://www.schneier.com/blog/archives/2014/03/choosing_secure_1.html https://www.schneier.com/blog/archives/2014/03/choosing_secu... > This is why the oft-cit

https://www.schneier.com/blog/archives/2014/03/choosing_secure_1.html https://www.schneier.com/blog/archives/2014/03/choosing_secu... > This is why the oft-cited XKCD scheme for generating passwords -- string together individual words like "correcthorsebatterystaple" -- is no longer good advice. The password crackers are on to this trick.

andybak 11y ago
4 true random choices from a dictionary of 5000 words is 50 bits of entropy. All things being equal that is just as good as any other password scheme with 50 bits of entropy. I think that's about the same as a 10 character upper/lower/numbers/symbols password. That's your worse case scenario. Add to that the fact that: a) the attacker doesn't have your dictionary b) they can't be sure you're using this method c) you might add a minor extra step of your choosing then the attack becomes significantly harder than attacking a 'normal' password with 50 bits of entropy
- deleted 11y ago
  [deleted]
- imaginenore 11y ago
  The attacker will naturally start with a smaller dictionary, most common words, which reduces the search space greatly. So unless you're using some of those SAT words, it's even less secure.
  - contravariant 11y ago
    5000 words is pretty small for a dictionary. Of course if you're using really simple words to make your passwords then you're out of luck, but choosing random words from a 5000 word dictionary is reasonably secure. Language contains a surprising amount of entropy, not as much as random characters, but still enough that I can be reasonably sure that this sentence is unique.
- creshal 11y ago
  > a) the attacker doesn't have your dictionary How many truly unique sources for dictionaries are there? My own password generator simply uses `/usr/share/dict/words`, which is not that hard to guess (and documented in the generator's source code).[0] Add to this that not all languages lend themselves to this algorithm – while my native language is German, you'd need a word stem dictionary, as opposed to a regular dictionary, for this, so I stick to English dictionaries.[1] [0] I actually made it configurable, but lacking a better source, it'll probably remain at this default: https://github.com/creshal/yspave/blob/master/config.json.example#L25 https://github.com/creshal/yspave/blob/master/config.json.ex... [1] cf. http://creshal.de/News/?id=59 http://creshal.de/News/?id=59 , where I rambled on it a bit more.
  - omh 11y ago
    My own password generator simply uses /usr/share/dict/words On my system /usr/share/dict/words has ~45k words. That's 15 bits of entropy per word, significantly more than XKCD (which assumes 11 bits). So I'd agree that there probably aren't many unique dictionaries. The strength of this password scheme is that it works even assuming the attacker knows your dictionary. In practice, I guess that an attacker will use a concatenation of all popular dictionaries. This will make things slightly harder for them (e.g. if they have 50k words vs the 30k in your dictionary) but not by a huge factor.
    - creshal 11y ago
      > The strength of this password scheme is that it works even assuming the attacker knows your dictionary. Indeed. Arguing about whether or not your dictionary is "unique" enough is a red herring. Whatever generator you use should accounts for the dictionary's word entropy, not for the theoretical per-byte entropy.
- mrmcd 11y ago
  I just looked at some of the hashcat benchmarks and they are clocking MD5 on one of their test machines at 115840 Mh/s. (2^50)/(115840*10^6) = 9719.43 seconds, or about 2-3 hours to break one correct horse style password. I think the point is that 50 bits of entropy is not enough when you consider the speed of GPU hashing. Obviously you shouldn't use MD5 for hashing passwords, but since you often have no control over what algo a site uses (or even information about which one they did pick), assuming they will do something common and bad like unsalted MD5 isn't a bad starting point for this kind of analysis.
  - orblivion 11y ago
    Maybe so, but then that doesn't say much about the usual alternative which has even less entropy. EDIT: Actually I was going by xkcx's claims, which start with a dictionary word and adda random tweaks to it. I don't know off hand how long a random password would have to be to match 50 bits. But ultimately, that is the question; is this method at least as good as the alternative.
    - mrmcd 11y ago
      Assuming 80 possible characters (A-Z,a-z,0-9 + 18 punctuation symbols), log2(80^8) ~= 50. So a correct horse password would be about the same as a random 8 character alpha-numeric entropy wise. The XKCD argument is that correct hose style is way easier to remember. It's possible Schneier thought Munroe was arguing that a correct horse was as much entropy as a 20 character random password, even though he isn't. This is the first I've heard of this argument though so I'm not even sure how much of a controversy it is.
  - creshal 11y ago
    IMO, there are two kinds of passwords relevant nowadays: • Password used to encrypt your password database, whichever it is • Everything else Since the idea of a password database is that you can give each website unique passwords without having to memorize it, you can go full ASCII printable range 20 digits for site passwords. Those will not be brute forced any time soon – at 128 bit entropy –, and the damage of having them leaked will be minimal. Your password database, on the other hand, should use a painfully slow algorithm for its PBKDF. If that's not using at least scrypt, you indeed have a problem. But assuming a good password database design, 50 bits shouldn't be too bad.
ascorbic 11y ago
Far be it from me to contradict Bruce Schneier, but he doesn't actually give a good reason why the XKCD or diceware scheme is bad. He seems to be saying that it's not as good as a 25 character random string, which is true, but that's not what is claimed. Even if the attacker knows your word list, and knows that you've chosen four of them, if you've chosen them randomly then there's still easily enough entropy to make it unrealistic for them to crack it.
- digi_owl 11y ago
  And that seems to be an ongoing issue with -sec debates. That the people "inside" are so focused on "perfect" protection, that they see anything else as worthless. There was someone here on HN just the other day that basically decried a scheme for using multiple user accounts to "sandbox" programs as useless because it would be ineffective against "state actors" (aka NSA and their equivalent). This even though it would likely foil, or at least reduce the impact of "drive by" attacks aimed at accessing personal information for identity theft etc.
- danesparza 11y ago
  Well, he does explain it: "Modern password crackers combine different words from their dictionaries" And then he goes on to give his advice (of using a password manager or a piece of paper, etc). Is it that advice that you're contradicting? You also said "..but that's not what is claimed". Are you referring to the implied claim in the original XKCD cartoon (https://xkcd.com/936 https://xkcd.com/936) or something else? I'm just trying to understand.
  - ascorbic 11y ago
    The whole point of this scheme is that it doesn't matter that password crackers know about it. It would matter if we were comparing them purely on the number of characters, but that's not the basis that either XKCD or this site calculates the entropy. Four words from a list of 5000 gives 49 bits of entropy. That means there are 2^49 possible passwords (~500 trillion) even if you know the wordlist.
  - omh 11y ago
gabemart 11y ago
That doesn't really address the XKCD. The XKCD was comparing schemes where the attacker has perfect information about the password scheme each user is using. Password crackers therefore cannot be "on to this trick" as it is assumed they already know in the initial calculations of entropy. Given that Bruce Schneier is Bruce Schneier, it seems likely that I am wrong somehow, but at present I cannot see in what way.
Tomte 11y ago
Schneier misunderstood the XKCD scheme and ranted. There's no shame in that, per se, but it was pointed out to him repeatedly in the comments, and he never corrected his mistake. Just one incident, where he lost a lot of credibility with me. I feel he should have stuck to the technical side of software security and cryptography instead of playing politics.
contravariant 11y ago
Can anyone explain how removing letters from a sentence increases it's (total) entropy? Edit: Okay, I can sort of see how it can increase entropy. Replacing characters with 'nothing' randomly does give some extra entropy, although you lose some as well (especially if you overdo it). Seems like it would be best to randomly remove about half of them, although that's also difficult to remember, and only adds 1 extra bit per character (assuming no entropy is otherwise lost). Overall I'm still not convinced.

andybak 11y ago

4 true random choices from a dictionary of 5000 words is 50 bits of entropy. All things being equal that is just as good as any other password scheme with 50 bits of entropy. I think that's about the same as a 10 character upper/lower/numbers/symbols password. That's your worse case scenario. Add to that the fact that: a) the attacker doesn't have your dictionary b) they can't be sure you're using this method c) you might add a minor extra step of your choosing then the attack becomes significantly harder than attacking a 'normal' password with 50 bits of entropy

deleted 11y ago
[deleted]
imaginenore 11y ago
The attacker will naturally start with a smaller dictionary, most common words, which reduces the search space greatly. So unless you're using some of those SAT words, it's even less secure.
- contravariant 11y ago
  5000 words is pretty small for a dictionary. Of course if you're using really simple words to make your passwords then you're out of luck, but choosing random words from a 5000 word dictionary is reasonably secure. Language contains a surprising amount of entropy, not as much as random characters, but still enough that I can be reasonably sure that this sentence is unique.
creshal 11y ago
> a) the attacker doesn't have your dictionary How many truly unique sources for dictionaries are there? My own password generator simply uses `/usr/share/dict/words`, which is not that hard to guess (and documented in the generator's source code).[0] Add to this that not all languages lend themselves to this algorithm – while my native language is German, you'd need a word stem dictionary, as opposed to a regular dictionary, for this, so I stick to English dictionaries.[1] [0] I actually made it configurable, but lacking a better source, it'll probably remain at this default: https://github.com/creshal/yspave/blob/master/config.json.example#L25 https://github.com/creshal/yspave/blob/master/config.json.ex... [1] cf. http://creshal.de/News/?id=59 http://creshal.de/News/?id=59 , where I rambled on it a bit more.
- omh 11y ago
  My own password generator simply uses /usr/share/dict/words On my system /usr/share/dict/words has ~45k words. That's 15 bits of entropy per word, significantly more than XKCD (which assumes 11 bits). So I'd agree that there probably aren't many unique dictionaries. The strength of this password scheme is that it works even assuming the attacker knows your dictionary. In practice, I guess that an attacker will use a concatenation of all popular dictionaries. This will make things slightly harder for them (e.g. if they have 50k words vs the 30k in your dictionary) but not by a huge factor.
  - creshal 11y ago
    > The strength of this password scheme is that it works even assuming the attacker knows your dictionary. Indeed. Arguing about whether or not your dictionary is "unique" enough is a red herring. Whatever generator you use should accounts for the dictionary's word entropy, not for the theoretical per-byte entropy.
mrmcd 11y ago
I just looked at some of the hashcat benchmarks and they are clocking MD5 on one of their test machines at 115840 Mh/s. (2^50)/(115840*10^6) = 9719.43 seconds, or about 2-3 hours to break one correct horse style password. I think the point is that 50 bits of entropy is not enough when you consider the speed of GPU hashing. Obviously you shouldn't use MD5 for hashing passwords, but since you often have no control over what algo a site uses (or even information about which one they did pick), assuming they will do something common and bad like unsalted MD5 isn't a bad starting point for this kind of analysis.
- orblivion 11y ago
  Maybe so, but then that doesn't say much about the usual alternative which has even less entropy. EDIT: Actually I was going by xkcx's claims, which start with a dictionary word and adda random tweaks to it. I don't know off hand how long a random password would have to be to match 50 bits. But ultimately, that is the question; is this method at least as good as the alternative.
  - mrmcd 11y ago
    Assuming 80 possible characters (A-Z,a-z,0-9 + 18 punctuation symbols), log2(80^8) ~= 50. So a correct horse password would be about the same as a random 8 character alpha-numeric entropy wise. The XKCD argument is that correct hose style is way easier to remember. It's possible Schneier thought Munroe was arguing that a correct horse was as much entropy as a 20 character random password, even though he isn't. This is the first I've heard of this argument though so I'm not even sure how much of a controversy it is.
- creshal 11y ago
  IMO, there are two kinds of passwords relevant nowadays: • Password used to encrypt your password database, whichever it is • Everything else Since the idea of a password database is that you can give each website unique passwords without having to memorize it, you can go full ASCII printable range 20 digits for site passwords. Those will not be brute forced any time soon – at 128 bit entropy –, and the damage of having them leaked will be minimal. Your password database, on the other hand, should use a painfully slow algorithm for its PBKDF. If that's not using at least scrypt, you indeed have a problem. But assuming a good password database design, 50 bits shouldn't be too bad.

ascorbic 11y ago

Far be it from me to contradict Bruce Schneier, but he doesn't actually give a good reason why the XKCD or diceware scheme is bad. He seems to be saying that it's not as good as a 25 character random string, which is true, but that's not what is claimed. Even if the attacker knows your word list, and knows that you've chosen four of them, if you've chosen them randomly then there's still easily enough entropy to make it unrealistic for them to crack it.

digi_owl 11y ago
And that seems to be an ongoing issue with -sec debates. That the people "inside" are so focused on "perfect" protection, that they see anything else as worthless. There was someone here on HN just the other day that basically decried a scheme for using multiple user accounts to "sandbox" programs as useless because it would be ineffective against "state actors" (aka NSA and their equivalent). This even though it would likely foil, or at least reduce the impact of "drive by" attacks aimed at accessing personal information for identity theft etc.
danesparza 11y ago
Well, he does explain it: "Modern password crackers combine different words from their dictionaries" And then he goes on to give his advice (of using a password manager or a piece of paper, etc). Is it that advice that you're contradicting? You also said "..but that's not what is claimed". Are you referring to the implied claim in the original XKCD cartoon (https://xkcd.com/936 https://xkcd.com/936) or something else? I'm just trying to understand.
- ascorbic 11y ago
  The whole point of this scheme is that it doesn't matter that password crackers know about it. It would matter if we were comparing them purely on the number of characters, but that's not the basis that either XKCD or this site calculates the entropy. Four words from a list of 5000 gives 49 bits of entropy. That means there are 2^49 possible passwords (~500 trillion) even if you know the wordlist.
- omh 11y ago

gabemart 11y ago

That doesn't really address the XKCD. The XKCD was comparing schemes where the attacker has perfect information about the password scheme each user is using. Password crackers therefore cannot be "on to this trick" as it is assumed they already know in the initial calculations of entropy. Given that Bruce Schneier is Bruce Schneier, it seems likely that I am wrong somehow, but at present I cannot see in what way.

Tomte 11y ago

Schneier misunderstood the XKCD scheme and ranted. There's no shame in that, per se, but it was pointed out to him repeatedly in the comments, and he never corrected his mistake. Just one incident, where he lost a lot of credibility with me. I feel he should have stuck to the technical side of software security and cryptography instead of playing politics.

contravariant 11y ago

Can anyone explain how removing letters from a sentence increases it's (total) entropy? Edit: Okay, I can sort of see how it can increase entropy. Replacing characters with 'nothing' randomly does give some extra entropy, although you lose some as well (especially if you overdo it). Seems like it would be best to randomly remove about half of them, although that's also difficult to remember, and only adds 1 extra bit per character (assuming no entropy is otherwise lost). Overall I'm still not convinced.