5 ms·

What does NIST have to say about passwords like CorrectHorseBatteryStaple [0] that can be easily cracked by brute-forcing concatenations of dictionary words? [

by ddxxdd 7y ago

What does NIST have to say about passwords like CorrectHorseBatteryStaple [0] that can be easily cracked by brute-forcing concatenations of dictionary words? [0] https://xkcd.com/936/ https://xkcd.com/936/

cardine 7y ago
Even if you knew the pattern, four random lowercase dictionary words (assuming a dictionary size of 50,000 words) would take longer to crack than a randomly generated 10 digit password with letters, numbers, and special characters. 50,000^4 > (26+26+10+10)^10
- jupp0r 7y ago
  This is really dependent on the size of the dictionary.
  - bhelkey 7y ago
    > assuming a dictionary size of 50,000 words
  - cardine 7y ago
    If your dictionary is smaller than 50,000 words, all you would have to do is add another word. 10,000^5 > 50,000^4
- montecarl 7y ago
  Its not quite fair to assume that people are choosing randomly from 50k words. Here is what those passwords look like. I excluded proper nouns and possessives. If you want to try, this command works on Ubuntu: echo $(cat /usr/share/dict/american-english | grep -v \' | egrep -v '[A-Z].*' | shuf -n 4 | tr '\n' ' ') trawled scratch protract sagings perpetuates barium entreated credits integrals virago chronicled weathercocks foremasts milkmaid bashful maddened disposes shrunk propose stanchion midwived romantics gallbladders spotlighted
  - deleted 7y ago
    [deleted]
  - j88439h84 7y ago
    What is the size of that dictionary?
    - montecarl 7y ago
      About 60k words.
  - codetrotter 7y ago
    Good point. The EFF has made and published three lists of words to use that are easy to spell and generally easy to remember. I wrote a command-line tool in Rust for generating passphrase using these wordlists. I use it myself any time I need a password. My tool is fast, free of charge, open source and it can also tell you the entropy that will result for any given choice of number of words. For example let’s say I want it to give me four words from the long wordlist, and I want to know how many bits of entropy this corresponds to. pgen -l -n 4 -e Current settings will create passphrases with 51.70 bits of entropy. 51.70 bits of entropy. What does that mean, you might ask. The Wikipedia article on password strength (https://en.wikipedia.org/wiki/Password_strength https://en.wikipedia.org/wiki/Password_strength) explains it well: > A password with an entropy of 42 bits calculated in this way would be as strong as a string of 42 bits chosen randomly, for example by a fair coin toss. Put another way, a password with an entropy of 42 bits would require 2^42 (4,398,046,511,104) attempts to exhaust all possibilities during a brute force search. Thus, by increasing the entropy of the password by one bit the number of guesses required doubles, making an attacker's task twice as difficult. On average, an attacker will have to try half the possible number of passwords before finding the correct one. Ok, so how good is 51.70 bits of entropy, you ask? Wikipedia, same article again: > The minimum number of bits of entropy needed for a password depends on the threat model for the given application. [...] RFC 4086, "Randomness Requirements for Security", presents some example threat models and how to calculate the entropy desired for each one. Their answers vary between 29 bits of entropy needed if only online attacks are expected, and up to 96 bits of entropy needed for important cryptographic keys used in applications like encryption where the password or key needs to be secure for a long period of time and stretching isn't applicable. So let's say that you are satisfied with 51.70 bits of entropy in this case. What does a password like that look like? Let's generate one. pgen -l -n 4 plastic case refocus demise Pretty memorable if you ask me :) Oh yeah, and about the claim that it's fast. Just how fast is it? Have a look. time pgen -l -n 4 browbeat hummus sandbox unfixable real 0m0.005s user 0m0.001s sys 0m0.006s That's 5 milliseconds. But hey, let's say we wanted to generate a bunch of passphrases at once. How much time does it take to generate 10.000 passphrases and dump them into a text file? time pgen -l -n 4 -k 10000 > 10k.txt real 0m0.132s user 0m0.073s sys 0m0.058s About zero point one seconds. Not that generating 10.000 passphrases is something that you are likely to do, but it just speaks to how fast this tool is ^^ Source and instructions on how to install it are on GitHub. https://github.com/ctsrc/Pgen https://github.com/ctsrc/Pgen
- txcwpalpha 7y ago
  It would be very interesting to see the results of a study asking people to come up with a list of random words. I really doubt that the actual dictionary size would be anywhere near 50k, and probably would have a high frequency of common words like 'apple', 'house', 'food' etc, making them easier to crack, and almost no frequency of less common words.
  - deleted 7y ago
    [deleted]
  - dyu 7y ago
    the assumption is you do not come up with your own words, and pick words at random from the whole dictionary.
    - txcwpalpha 7y ago
      I'm not sure I agree with that assumption, as the entire purpose of a passphrase of words rather than a password of random characters is that the passphrase should be easier to remember. If you're randomly picking words like 'gargarize-youster-noctivagant-axilla', it's not exactly accomplishing that purpose very well. It's also a huge PITA to type in, which based on my experience in the IAM space, is an immediate dealbreaker.
      - lstamour 7y ago
        I’d rather pick from obscure words I know than at random. In my case the words might lean tech/business/news/sports, but I’m sure I could come up with a good list. It might be interesting to try and generate passwords from a corpus of email and/or browsing history... assuming you blacklist sensitive subjects.
        bigiain 7y ago
        I let my password manager pick words for me, and I keep hitting refresh until I get one that I think I'm likely to get the spelling correct when needed. 1Password just gave me this: land convolve witchery bequest Having said that, since I use 1Password, these are rare and almost exclusively used for things where I need very-short-term memorable passphrases for things that won't let me copy/paste from 1Password (like my Apple ID or the passwords my bank ask me for over the phone...) Everything else just gets 25 random chars (or the maximum number of chars the input will allow).
- danielbarla 7y ago
  What I find interesting about the XKCD is that the entropy analysis is basically spot-on, even very generous towards the opposition. It shows that a) the typical "strong password" that people pick is not truly random (i.e. not 26+26+10+10, but worse), and b) that under these conditions even a 4-length pass phrase picked from a measly dictionary of 2048 words is better. (This is probably an even more interesting / compelling argument.) Yet somehow, each time the XKCD is posted, someone will "point out" that pass phrases can be dictionary attacked, which is kind of like me saying "I know which letters are on your keyboard, and can therefore brute force your password!", but not having done the math beyond that.
jupp0r 7y ago
Quoting: When processing requests to establish and change memorized secrets, verifiers SHALL compare the prospective secrets against a list that contains values known to be commonly-used, expected, or compromised. For example, the list MAY include, but is not limited to: - Passwords obtained from previous breach corpuses. - Dictionary words. - Repetitive or sequential characters (e.g. ‘aaaaaa’, ‘1234abcd’). - Context-specific words, such as the name of the service, the username, and derivatives thereof. [1] https://pages.nist.gov/800-63-3/sp800-63b.html https://pages.nist.gov/800-63-3/sp800-63b.html
- dllthomas 7y ago
  If I read that correctly, it's about comparing the entire password, not portions thereof, so it's not really about "multiple English word" passwords (except that I assume "passwords obtained from previous breach corpuses" is likely to contain some specific examples of the breed, almost certainly including "correct horse battery staple").
wiml 7y ago
They can't be, unless you generate them badly. A diceware passphrase has 6^6 possibilities ≈ 15 bits of entropy per word, so an unremarkable 5-word password has 77 bits of entropy — generally good enough — and if you have a high value target that might be susceptible to offline attacks, 90-100 bit passwords are still pretty easy to remember. I wish people wouldn't use XKCD as the go-to reference for "collection of randomly selected words"-style passwords; it always seems to leave people confused about why the technique works.
dllthomas 7y ago
> easily cracked by brute-forcing concatenations of dictionary words This is probably misleading (and possibly confused). Diceware style passphrases are easily brute forced relative to a random passphrase of the same length but that doesn't mean they're "easily brute forced". Assume your attacker knows how you're constructing your password, estimate the amount of entropy, and be sure it's enough. 44 bits is low for offline attacks, but (as the comic points out) still better than a lot of passwords people use even when they're trying to make a good password and following NIST guidelines. If you use 5 words and draw from a longer list, it's easy to be solidly out of the range that's crackable on modern hardware.

by ddxxdd 7y ago

cardine 7y ago

Even if you knew the pattern, four random lowercase dictionary words (assuming a dictionary size of 50,000 words) would take longer to crack than a randomly generated 10 digit password with letters, numbers, and special characters. 50,000^4 > (26+26+10+10)^10

jupp0r 7y ago
This is really dependent on the size of the dictionary.
- bhelkey 7y ago
  > assuming a dictionary size of 50,000 words
- cardine 7y ago
  If your dictionary is smaller than 50,000 words, all you would have to do is add another word. 10,000^5 > 50,000^4
montecarl 7y ago
Its not quite fair to assume that people are choosing randomly from 50k words. Here is what those passwords look like. I excluded proper nouns and possessives. If you want to try, this command works on Ubuntu: echo $(cat /usr/share/dict/american-english | grep -v \' | egrep -v '[A-Z].*' | shuf -n 4 | tr '\n' ' ') trawled scratch protract sagings perpetuates barium entreated credits integrals virago chronicled weathercocks foremasts milkmaid bashful maddened disposes shrunk propose stanchion midwived romantics gallbladders spotlighted
- deleted 7y ago
  [deleted]
- j88439h84 7y ago
  What is the size of that dictionary?
  - montecarl 7y ago
    About 60k words.
- codetrotter 7y ago
  Good point. The EFF has made and published three lists of words to use that are easy to spell and generally easy to remember. I wrote a command-line tool in Rust for generating passphrase using these wordlists. I use it myself any time I need a password. My tool is fast, free of charge, open source and it can also tell you the entropy that will result for any given choice of number of words. For example let’s say I want it to give me four words from the long wordlist, and I want to know how many bits of entropy this corresponds to. pgen -l -n 4 -e Current settings will create passphrases with 51.70 bits of entropy. 51.70 bits of entropy. What does that mean, you might ask. The Wikipedia article on password strength (https://en.wikipedia.org/wiki/Password_strength https://en.wikipedia.org/wiki/Password_strength) explains it well: > A password with an entropy of 42 bits calculated in this way would be as strong as a string of 42 bits chosen randomly, for example by a fair coin toss. Put another way, a password with an entropy of 42 bits would require 2^42 (4,398,046,511,104) attempts to exhaust all possibilities during a brute force search. Thus, by increasing the entropy of the password by one bit the number of guesses required doubles, making an attacker's task twice as difficult. On average, an attacker will have to try half the possible number of passwords before finding the correct one. Ok, so how good is 51.70 bits of entropy, you ask? Wikipedia, same article again: > The minimum number of bits of entropy needed for a password depends on the threat model for the given application. [...] RFC 4086, "Randomness Requirements for Security", presents some example threat models and how to calculate the entropy desired for each one. Their answers vary between 29 bits of entropy needed if only online attacks are expected, and up to 96 bits of entropy needed for important cryptographic keys used in applications like encryption where the password or key needs to be secure for a long period of time and stretching isn't applicable. So let's say that you are satisfied with 51.70 bits of entropy in this case. What does a password like that look like? Let's generate one. pgen -l -n 4 plastic case refocus demise Pretty memorable if you ask me :) Oh yeah, and about the claim that it's fast. Just how fast is it? Have a look. time pgen -l -n 4 browbeat hummus sandbox unfixable real 0m0.005s user 0m0.001s sys 0m0.006s That's 5 milliseconds. But hey, let's say we wanted to generate a bunch of passphrases at once. How much time does it take to generate 10.000 passphrases and dump them into a text file? time pgen -l -n 4 -k 10000 > 10k.txt real 0m0.132s user 0m0.073s sys 0m0.058s About zero point one seconds. Not that generating 10.000 passphrases is something that you are likely to do, but it just speaks to how fast this tool is ^^ Source and instructions on how to install it are on GitHub. https://github.com/ctsrc/Pgen https://github.com/ctsrc/Pgen
txcwpalpha 7y ago
It would be very interesting to see the results of a study asking people to come up with a list of random words. I really doubt that the actual dictionary size would be anywhere near 50k, and probably would have a high frequency of common words like 'apple', 'house', 'food' etc, making them easier to crack, and almost no frequency of less common words.
- deleted 7y ago
  [deleted]
- dyu 7y ago
  the assumption is you do not come up with your own words, and pick words at random from the whole dictionary.
  - txcwpalpha 7y ago
    I'm not sure I agree with that assumption, as the entire purpose of a passphrase of words rather than a password of random characters is that the passphrase should be easier to remember. If you're randomly picking words like 'gargarize-youster-noctivagant-axilla', it's not exactly accomplishing that purpose very well. It's also a huge PITA to type in, which based on my experience in the IAM space, is an immediate dealbreaker.
    - lstamour 7y ago
      I’d rather pick from obscure words I know than at random. In my case the words might lean tech/business/news/sports, but I’m sure I could come up with a good list. It might be interesting to try and generate passwords from a corpus of email and/or browsing history... assuming you blacklist sensitive subjects.
      - bigiain 7y ago
        I let my password manager pick words for me, and I keep hitting refresh until I get one that I think I'm likely to get the spelling correct when needed. 1Password just gave me this: land convolve witchery bequest Having said that, since I use 1Password, these are rare and almost exclusively used for things where I need very-short-term memorable passphrases for things that won't let me copy/paste from 1Password (like my Apple ID or the passwords my bank ask me for over the phone...) Everything else just gets 25 random chars (or the maximum number of chars the input will allow).
danielbarla 7y ago
What I find interesting about the XKCD is that the entropy analysis is basically spot-on, even very generous towards the opposition. It shows that a) the typical "strong password" that people pick is not truly random (i.e. not 26+26+10+10, but worse), and b) that under these conditions even a 4-length pass phrase picked from a measly dictionary of 2048 words is better. (This is probably an even more interesting / compelling argument.) Yet somehow, each time the XKCD is posted, someone will "point out" that pass phrases can be dictionary attacked, which is kind of like me saying "I know which letters are on your keyboard, and can therefore brute force your password!", but not having done the math beyond that.

jupp0r 7y ago

Quoting: When processing requests to establish and change memorized secrets, verifiers SHALL compare the prospective secrets against a list that contains values known to be commonly-used, expected, or compromised. For example, the list MAY include, but is not limited to: - Passwords obtained from previous breach corpuses. - Dictionary words. - Repetitive or sequential characters (e.g. ‘aaaaaa’, ‘1234abcd’). - Context-specific words, such as the name of the service, the username, and derivatives thereof. [1] https://pages.nist.gov/800-63-3/sp800-63b.html https://pages.nist.gov/800-63-3/sp800-63b.html

dllthomas 7y ago
If I read that correctly, it's about comparing the entire password, not portions thereof, so it's not really about "multiple English word" passwords (except that I assume "passwords obtained from previous breach corpuses" is likely to contain some specific examples of the breed, almost certainly including "correct horse battery staple").

wiml 7y ago

They can't be, unless you generate them badly. A diceware passphrase has 6^6 possibilities ≈ 15 bits of entropy per word, so an unremarkable 5-word password has 77 bits of entropy — generally good enough — and if you have a high value target that might be susceptible to offline attacks, 90-100 bit passwords are still pretty easy to remember. I wish people wouldn't use XKCD as the go-to reference for "collection of randomly selected words"-style passwords; it always seems to leave people confused about why the technique works.

dllthomas 7y ago

> easily cracked by brute-forcing concatenations of dictionary words This is probably misleading (and possibly confused). Diceware style passphrases are easily brute forced relative to a random passphrase of the same length but that doesn't mean they're "easily brute forced". Assume your attacker knows how you're constructing your password, estimate the amount of entropy, and be sure it's enough. 44 bits is low for offline attacks, but (as the comic points out) still better than a lot of passwords people use even when they're trying to make a good password and following NIST guidelines. If you use 5 words and draw from a longer list, it's easy to be solidly out of the range that's crackable on modern hardware.