4 ms·

I suppose this is a good place to ask this question. How much truth is there to the fairly famous XKCD comic "correct horse battery staple" in this scenario. I

by Kequc 9y ago

I suppose this is a good place to ask this question. How much truth is there to the fairly famous XKCD comic "correct horse battery staple" in this scenario. Isn't it possible that random word combinations, if they were common in passwords, could be guessed relatively early in a password hash brute force attack? Especially considering we are talking about apparently billions of attempts per second. Second question, is it true that placing restrictions on the password such as that it must include a capital letter, a special character, and be 8 characters long. Also reduces the time it takes to crack because the algorithm can simply dump a huge amount of possible answers?

rbanffy 9y ago
> correct horse battery staple Assuming a vocabulary of 16K words, it's 15 bits per word for a total of 60 bits for the four word password. Letters plus punctuation will give you about 60 symbols or 6 bits per position. At 60 bits, the four word password is as good as the 10 characters you generated by smashing your elbows on the keyboard and, hopefully, easier to remember. > Also reduces the time it takes to crack because the algorithm can simply dump a huge amount of possible answers? Yes. Knowing the password rules limits the space that'd need to be bruteforced.
- deleted 9y ago
  [deleted]
- thesz 9y ago
  Typical ASR vocabulary size for English is about 64K words. If you are unsatisfied with these, use Finnish or Turkish. The vocabulary there is unlimited, for all practical purposes. Even English can do better than 64K words - use suffixes, as Turkish people do. "Correctless horse batteryness staplenesslessness". Now you are in the 80 bits for 4 words territory.
  - zokier 9y ago
    > The vocabulary there is unlimited, for all practical purposes Don't know about Turkish, but for practical purposes Finnish dictionary is very much limited. Source: I'm a native (bilingual) Finnish speaker.
    - thesz 9y ago
      I am working with language modeling lately. For practical purposes (computing perplexity, etc, which is close to of password guessing), Finnish vocabulary is pretty much unlimited.
- FabHK 9y ago
  zxcvbn [1], the best simple password strength estimator I'm aware of, gives "correct horse battery staple" around 62 bits, and "Tr0ub4dour&3" around 30 bits (cracked in a day). ("ILoveTacoAndBurgersWhatever1984", suggested below, 53 bits). > Yes. Knowing the password rules limits the space that'd need to be bruteforced. Yes, but not that much, really: 1. Giving away the length of your password doesn't help the attacker much. For realistic scenarios, testing all passwords with length < N takes less than 2% of the time of testing all passwords with length N. (The proportion of passwords with length < N to passwords with length N is approximately 1/M, where M is the number of distinct symbols (here about 60). Exactly it's (q-q^N)/(1-q), I think, where q=1/M.) So, even if you use only numbers, telling the attacker the length of the password gives them only a 10% edge. 2. Knowing that a 10 letter password contains at least one number excludes about 1/6 of passwords ((50/60)^10). So, that's less than one bit. Similarly with special characters etc. TL;DR: Telling an adversary the length of your password doesn't really help them. Telling them password rules (contains a number, etc.) helps them more, but adding just one more character to your password increases the difficulty more than knowing the password rules decreases it. [1] https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-password-strength-estimation/ https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-pass... https://www.bennish.net/password-strength-checker/ https://www.bennish.net/password-strength-checker/
  - lucb1e 9y ago
    > the best simple password strength estimator What one is really trying to estimate with a "strength estimator" is how much entropy needs to be used to crack it when the generation method is known (Kerckhoff's principle, sort of). So what one really needs to look at is the generation method, not the resulting password.
- yosito 9y ago
  > Assuming a vocabulary of 16K words I would assume that including words not likely to be in any dictionary is a good way to increase the difficulty of guessing a password; made up words, slang in non-english languages, rare names, etc.
  - rbanffy 9y ago
    Yes, but you need to keep it random. If rare names occur more in passwords than a random choice would create, you are reducing the search space.
yeukhon 9y ago
Limiting character is wrong because the space is totally limited. Plenty of "important" websites do that and I go sigh. I use different password for different types of services for that reason. If we don't limit number of characters (but seriously I'd say on average password lengh would be 8-10; I go a lot beyond that). In practice forcing to have combinations of various character sets increase search space, but in practice I bet most users are likely to use @ for a, l for 1, or captialize either first initial, or first initial of every word. Or worse, just append, preappend, or modify one or two characters because some other websites decided to have a more unique password policy, and users hate to reinvent a whole new password. Then imagine one website got hacked, the next is easy.. So essentially if we can gather sufficent data about a target, then the brute force search space is now hammered and reduced. In any case, I am a big believer of no restriction, because of what I said above. The behavior of choosing password is not too random so we can predict and infer from whatever we know. Password and passphrase are the same shit because "ILoveTacoAndBurgersWhatever1984" is a legitmate password. Good luck guessing that because I am not a huge fan of Taco, and I bet you no machine brute force this in any reasonable time. The whole password vs passphrase is a campaign to get rid of the sophicated password policy, so people came up with a new name. In the end, I believe having a 2-auth and allowing users to freely choose whatever passwors they want is better than forcing them to choose whatever we think is best. Education is the key, both on social engineering and on choosing passwords. We as software technologists have the responsibility to make dangerous / "i am not sure if that's a good thing to do" warning more obvious. Of course I am aware there are other alternative proposals to replace pwd but for now password is not going anywhere soon.
- IncRnd 9y ago
  Limiting the character length of a password is an indication that the password is getting stored.
  - yeukhon 9y ago
    I am referring to limiting password to a small number. Of course no one should take in a password > 32 characters. bcrypt has limitation itself. A reasonable and practical limit is 32, so we can prevent DoS attack because encrypt/decrypt takes up a chunk of CPU resource. I'd be surprise anyone go beyond that (for a "passphrase").
teolandon 9y ago
The xkcd comic doesn't claim that "correct horse battery staple" is a completely secure password, it just shows that it's so much better than weird passwords that people tend to generate by themselves, like "k@tApU1t2143", and also how much easier it is to remember. So the suggestion is, if you're gonna use a password that you're going to remember, it's better to use a long one than a "complex" one. But yes, if the attacker knows that you're using English words for your passwords, the English language has about 170.000 words according to Oxford English Dict, and if you consider 1/10 of them to be known enough to be used in a password by you, if you use 4 words you have about 80.000.000.000.000.000 combinations, or about a day of brute-forcing with JTR. (Someone correct me if I'm wrong). Five words makes it a lot more secure, or using more obscure words. Coming up with a "random" method of choosing some 5-6 words out of a dictionary, using dice or coin flips, can go a long way to make your "phrase" password more secure against these kinds of attacks. Of course, the best approach is to use such a password, and use a password manager. As for your second question, I believe it doesn't reduce the time it takes to guess some user's password. The restriction to include capital letters or special characters forces users to introduce more entropy in their password, and thus prevents a lot of common password usage. An attacker knowing that the site's password must be at least 8 characters long is not that helpful. Checking all the 1-7 character long passwords is trivial compared to checking all the 8-10 character long passwords. So it is helpful, since it prevents a lot of users from using simple, guessable passwords. In short, the restrictions introduce more complexity than they subtract for most users. Edit: Having read the other replies, yes, it does technically reduce the search space, and it might be a bad thing (due to users adding simple common symbols, which are again easily guessed). So it probably isn't good practice.
- rrobukef 9y ago
  4 words take 835 x 10^18. You're low by x10000. The biggest number of the JTR benchmark page [1] is 80981K for single core (Microsoft LanMan) or 6200 kc/s for 1 CPU (DES). All combinations take 1x10^9 cpu-days or 14 x 10^9 cpu-days. Amazon pricing ranges from a lot to a whole lot more (at least 39 million $). [1] http://openwall.info/wiki/john/benchmarks http://openwall.info/wiki/john/benchmarks
sytelus 9y ago
I'm not an expert in this area but my general perception is that all those restrictions make system overall much less secure. This is simply because average users can't remember lengthy passwords and so they tend to use same password on many website or write it down somewhere insecurely. A much better approach may be just to have user use two or three words as password.
JohnStrange 9y ago
First question: If the size of the (known) dictionary is n words and the number of words in your passphrase is k, and if the choice of each word is made by a random number generator, then the entropy of the passphrase is k x log2(n). So for example a passphrase with 8 words from a dictionary containing 200,000 words has entropy 8 x log2(200000)=140.9 bits, which is very secure. If you don't choose the words randomly, the security may decrease drastically, but I doubt it will be less for a passphrase of 8 words than a non-randomly chosen short 'password'. Generally, XKCD's advice is sound, as long as people are aware that dedicated attackers can and probably will guess common phrases and book codes (passages from a book). Second question: Yes, any restrictions on password length or allowed characters drastically reduces password security. For example, 8 characters of random Latin1 is too short, it only has an entropy of 56.87 bit. Things get way worse once passords are not randomly generated. A user-chosen password limited to 8 characters of Latin1 is ridiculous and anyone can crack it. Generally speaking, humanly generated passphrases are no longer secure.
deleted 9y ago
[deleted]
zokier 9y ago
Its bit annoying how much misinformation there is on the web about diceware-style passwords (that correct horse batter staple is an example of). There are so many people (luckily not in this thread!) saying that because it is using dictionary words it is vulnerable to dictionary attacks. That is utterly false. The numbers simply do not lie: Set Number of symbols Bits per symbol 80 bit string length 20k word dict 20000 14.29 6 Printable ASCII 95 6.57 13 [A-Za-z0-9] 62 5.95 14 [a-zA-Z] 52 5.70 15 [a-z0-9] 36 5.17 16 [a-z] 26 4.70 18 [0-9] 10 3.32 25 ???? n log2(n) ceil(80/log2(n)) Bigger question is what is reasonable security level for common use. 80 bit security (like in that table) is probably good enough for most people, 40ish bits like in the XKCD is on the low side. Of course those bits should be always be generated in a secure manner, e.g. CSPRNG, no matter how they are then transformed into a password/phrse/whatever. edit: did some further quick math: From random internet source I got that single Nvidia 1080 GPU can do about 25 GH/s for MD5 (and much less for something sane). With that 80 bit password takes about 60000 GPU years to crack, 64 bits 1 GPU year, 40 bits less than a single GPU minute.
- triangleman 9y ago
  So in your example here, we are talking about a password composed of 6 random English words, compared to, for instance, a 13-character password composed of random upper/lowercase letters and numbers?
  - zokier 9y ago
    Yes, 6 randomly picked words from 20k word dictionary.
- Cacti 9y ago
  Even 60,000 GPU years sounds well within the capabilities of a large nation-state. Expensive, probably not worth it, probably better ways, maybe not practical, but certainly possible.

by Kequc 9y ago

rbanffy 9y ago

> correct horse battery staple Assuming a vocabulary of 16K words, it's 15 bits per word for a total of 60 bits for the four word password. Letters plus punctuation will give you about 60 symbols or 6 bits per position. At 60 bits, the four word password is as good as the 10 characters you generated by smashing your elbows on the keyboard and, hopefully, easier to remember. > Also reduces the time it takes to crack because the algorithm can simply dump a huge amount of possible answers? Yes. Knowing the password rules limits the space that'd need to be bruteforced.

deleted 9y ago
[deleted]
thesz 9y ago
Typical ASR vocabulary size for English is about 64K words. If you are unsatisfied with these, use Finnish or Turkish. The vocabulary there is unlimited, for all practical purposes. Even English can do better than 64K words - use suffixes, as Turkish people do. "Correctless horse batteryness staplenesslessness". Now you are in the 80 bits for 4 words territory.
- zokier 9y ago
  > The vocabulary there is unlimited, for all practical purposes Don't know about Turkish, but for practical purposes Finnish dictionary is very much limited. Source: I'm a native (bilingual) Finnish speaker.
  - thesz 9y ago
    I am working with language modeling lately. For practical purposes (computing perplexity, etc, which is close to of password guessing), Finnish vocabulary is pretty much unlimited.
FabHK 9y ago
zxcvbn [1], the best simple password strength estimator I'm aware of, gives "correct horse battery staple" around 62 bits, and "Tr0ub4dour&3" around 30 bits (cracked in a day). ("ILoveTacoAndBurgersWhatever1984", suggested below, 53 bits). > Yes. Knowing the password rules limits the space that'd need to be bruteforced. Yes, but not that much, really: 1. Giving away the length of your password doesn't help the attacker much. For realistic scenarios, testing all passwords with length < N takes less than 2% of the time of testing all passwords with length N. (The proportion of passwords with length < N to passwords with length N is approximately 1/M, where M is the number of distinct symbols (here about 60). Exactly it's (q-q^N)/(1-q), I think, where q=1/M.) So, even if you use only numbers, telling the attacker the length of the password gives them only a 10% edge. 2. Knowing that a 10 letter password contains at least one number excludes about 1/6 of passwords ((50/60)^10). So, that's less than one bit. Similarly with special characters etc. TL;DR: Telling an adversary the length of your password doesn't really help them. Telling them password rules (contains a number, etc.) helps them more, but adding just one more character to your password increases the difficulty more than knowing the password rules decreases it. [1] https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-password-strength-estimation/ https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-pass... https://www.bennish.net/password-strength-checker/ https://www.bennish.net/password-strength-checker/
- lucb1e 9y ago
  > the best simple password strength estimator What one is really trying to estimate with a "strength estimator" is how much entropy needs to be used to crack it when the generation method is known (Kerckhoff's principle, sort of). So what one really needs to look at is the generation method, not the resulting password.
yosito 9y ago
> Assuming a vocabulary of 16K words I would assume that including words not likely to be in any dictionary is a good way to increase the difficulty of guessing a password; made up words, slang in non-english languages, rare names, etc.
- rbanffy 9y ago
  Yes, but you need to keep it random. If rare names occur more in passwords than a random choice would create, you are reducing the search space.

yeukhon 9y ago

Limiting character is wrong because the space is totally limited. Plenty of "important" websites do that and I go sigh. I use different password for different types of services for that reason. If we don't limit number of characters (but seriously I'd say on average password lengh would be 8-10; I go a lot beyond that). In practice forcing to have combinations of various character sets increase search space, but in practice I bet most users are likely to use @ for a, l for 1, or captialize either first initial, or first initial of every word. Or worse, just append, preappend, or modify one or two characters because some other websites decided to have a more unique password policy, and users hate to reinvent a whole new password. Then imagine one website got hacked, the next is easy.. So essentially if we can gather sufficent data about a target, then the brute force search space is now hammered and reduced. In any case, I am a big believer of no restriction, because of what I said above. The behavior of choosing password is not too random so we can predict and infer from whatever we know. Password and passphrase are the same shit because "ILoveTacoAndBurgersWhatever1984" is a legitmate password. Good luck guessing that because I am not a huge fan of Taco, and I bet you no machine brute force this in any reasonable time. The whole password vs passphrase is a campaign to get rid of the sophicated password policy, so people came up with a new name. In the end, I believe having a 2-auth and allowing users to freely choose whatever passwors they want is better than forcing them to choose whatever we think is best. Education is the key, both on social engineering and on choosing passwords. We as software technologists have the responsibility to make dangerous / "i am not sure if that's a good thing to do" warning more obvious. Of course I am aware there are other alternative proposals to replace pwd but for now password is not going anywhere soon.

IncRnd 9y ago
Limiting the character length of a password is an indication that the password is getting stored.
- yeukhon 9y ago
  I am referring to limiting password to a small number. Of course no one should take in a password > 32 characters. bcrypt has limitation itself. A reasonable and practical limit is 32, so we can prevent DoS attack because encrypt/decrypt takes up a chunk of CPU resource. I'd be surprise anyone go beyond that (for a "passphrase").

teolandon 9y ago

The xkcd comic doesn't claim that "correct horse battery staple" is a completely secure password, it just shows that it's so much better than weird passwords that people tend to generate by themselves, like "k@tApU1t2143", and also how much easier it is to remember. So the suggestion is, if you're gonna use a password that you're going to remember, it's better to use a long one than a "complex" one. But yes, if the attacker knows that you're using English words for your passwords, the English language has about 170.000 words according to Oxford English Dict, and if you consider 1/10 of them to be known enough to be used in a password by you, if you use 4 words you have about 80.000.000.000.000.000 combinations, or about a day of brute-forcing with JTR. (Someone correct me if I'm wrong). Five words makes it a lot more secure, or using more obscure words. Coming up with a "random" method of choosing some 5-6 words out of a dictionary, using dice or coin flips, can go a long way to make your "phrase" password more secure against these kinds of attacks. Of course, the best approach is to use such a password, and use a password manager. As for your second question, I believe it doesn't reduce the time it takes to guess some user's password. The restriction to include capital letters or special characters forces users to introduce more entropy in their password, and thus prevents a lot of common password usage. An attacker knowing that the site's password must be at least 8 characters long is not that helpful. Checking all the 1-7 character long passwords is trivial compared to checking all the 8-10 character long passwords. So it is helpful, since it prevents a lot of users from using simple, guessable passwords. In short, the restrictions introduce more complexity than they subtract for most users. Edit: Having read the other replies, yes, it does technically reduce the search space, and it might be a bad thing (due to users adding simple common symbols, which are again easily guessed). So it probably isn't good practice.

rrobukef 9y ago
4 words take 835 x 10^18. You're low by x10000. The biggest number of the JTR benchmark page [1] is 80981K for single core (Microsoft LanMan) or 6200 kc/s for 1 CPU (DES). All combinations take 1x10^9 cpu-days or 14 x 10^9 cpu-days. Amazon pricing ranges from a lot to a whole lot more (at least 39 million $). [1] http://openwall.info/wiki/john/benchmarks http://openwall.info/wiki/john/benchmarks

sytelus 9y ago

I'm not an expert in this area but my general perception is that all those restrictions make system overall much less secure. This is simply because average users can't remember lengthy passwords and so they tend to use same password on many website or write it down somewhere insecurely. A much better approach may be just to have user use two or three words as password.

JohnStrange 9y ago

First question: If the size of the (known) dictionary is n words and the number of words in your passphrase is k, and if the choice of each word is made by a random number generator, then the entropy of the passphrase is k x log2(n). So for example a passphrase with 8 words from a dictionary containing 200,000 words has entropy 8 x log2(200000)=140.9 bits, which is very secure. If you don't choose the words randomly, the security may decrease drastically, but I doubt it will be less for a passphrase of 8 words than a non-randomly chosen short 'password'. Generally, XKCD's advice is sound, as long as people are aware that dedicated attackers can and probably will guess common phrases and book codes (passages from a book). Second question: Yes, any restrictions on password length or allowed characters drastically reduces password security. For example, 8 characters of random Latin1 is too short, it only has an entropy of 56.87 bit. Things get way worse once passords are not randomly generated. A user-chosen password limited to 8 characters of Latin1 is ridiculous and anyone can crack it. Generally speaking, humanly generated passphrases are no longer secure.

deleted 9y ago

[deleted]

zokier 9y ago

Its bit annoying how much misinformation there is on the web about diceware-style passwords (that correct horse batter staple is an example of). There are so many people (luckily not in this thread!) saying that because it is using dictionary words it is vulnerable to dictionary attacks. That is utterly false. The numbers simply do not lie: Set Number of symbols Bits per symbol 80 bit string length 20k word dict 20000 14.29 6 Printable ASCII 95 6.57 13 [A-Za-z0-9] 62 5.95 14 [a-zA-Z] 52 5.70 15 [a-z0-9] 36 5.17 16 [a-z] 26 4.70 18 [0-9] 10 3.32 25 ???? n log2(n) ceil(80/log2(n)) Bigger question is what is reasonable security level for common use. 80 bit security (like in that table) is probably good enough for most people, 40ish bits like in the XKCD is on the low side. Of course those bits should be always be generated in a secure manner, e.g. CSPRNG, no matter how they are then transformed into a password/phrse/whatever. edit: did some further quick math: From random internet source I got that single Nvidia 1080 GPU can do about 25 GH/s for MD5 (and much less for something sane). With that 80 bit password takes about 60000 GPU years to crack, 64 bits 1 GPU year, 40 bits less than a single GPU minute.

triangleman 9y ago
So in your example here, we are talking about a password composed of 6 random English words, compared to, for instance, a 13-character password composed of random upper/lowercase letters and numbers?
- zokier 9y ago
  Yes, 6 randomly picked words from 20k word dictionary.
Cacti 9y ago
Even 60,000 GPU years sounds well within the capabilities of a large nation-state. Expensive, probably not worth it, probably better ways, maybe not practical, but certainly possible.