8 ms·

Sadly the "long passphrase" advice is also out of date. It relies on the naive idea that all password cracking is done brute-force, one character at a time. But

Sadly the "long passphrase" advice is also out of date. It relies on the naive idea that all password cracking is done brute-force, one character at a time. But all the huge leaks of password DBs over the past few years has given crackers a huge dataset to study and understand password generation behaviours, including how people come up with passphrases. Ars Technica did a long look at password cracking techniques[1] that covered stuff like this. The tl;dr is that any strategy short of full randomness is wrong. Either use a password manager, or use a set of dice, just make sure that your own human predictability cannot meaningfully affect the outcome. [1] https://arstechnica.com/information-technology/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ https://arstechnica.com/information-technology/2013/05/how-c...

GlitchMr 9y ago
The long passphrase idea as suggested by xkcd is fine, provided you pick random words. For instance, a database of 2048 words, and a 4 word passphrase has 44 entropy (2^44 possible passwords). >>> log2(2048 ** 4) 44.0 Even if somebody knows the pattern they have 17 592 186 044 416 passwords to try. You can further increase number of passwords to try by increasing number of words. Probably with advances of technology 4 words may be somewhat unsecure in the future, but 5 words is 2048 times harder to crack than 4 words password, so it should be still secure. The article in question shows three word passwords being cracked, but please note that three words is 2048 times easier to crack than 4 words, and probably very feasible to crack using graphics cards (provided poor choice of algorithms like MD5).
- davemp 9y ago
  Using non dictionary words should help greatly.
  - KekDemaga 9y ago
    There are probably less non dictionary words than dictionary words, perhaps better advice is to use words from a random language other than your own so the password cracker might make a wrong assumption and waste his time?
    - mcherm 9y ago
      > perhaps better advice is to use words from a random language other than your own I think you may have missed the point that the XKCD cartoon was making. The question here is NOT how to generate passwords that are hard for computers to guess. That's a solved problem: simply generate a 128-bit string with a secure random number generator, and that's your secure password that computers can't guess easily. The PROBLEM is to generate a password where the ratio of ease-for-humans-to-remember to ease-for-computers-to-guess is maximized. Using words from a language other than your own is NOT a good way to maximize this. Introducing just one more randomly-generated word from your own language will be far more effective by this criterion.
      - 5555624 9y ago
        You don't need to speak a language, much less be fluent in it, to use some words from it in a password. Although I am not fluent in any language other than English, I know words in Irish Gaelic, German, Japanese, Spanish, and some other languages. It's easy to use a word I know in one of those languages as part of a password. (I do have one password that does contain a word from a language I don't speak.)
        mannykannot 9y ago
        Up to a point, no doubt - but there is a good chance that the words you know from a language that you do not speak come from a small subset that is known by many non-speakers, so they may appear in cracking dictionaries, possibly gleaned from passwords that have been broken, or because they do sometimes appear in articles written predominantly in your language. Just for completeness, your strategy assumes the attackers are assuming a particular language - which I would guess is probably the right thing for them to do, if they are looking for low-hanging fruit.
      - chaoky 9y ago
        On the flip side, most of the world is multlingual or have at least been exposed to one other language. If you speak more than one language, mixing words from two or more basically renders dictionary attacks impossible, especially with number of languages and type unknown. I have words from non native languages in my passwords and they are just as easy or easier to remember.
- Taek 9y ago
  In practical terms, that's still not very many. GPUs can do 2 GH/s for a simple hashing function. Your 44 bit password can be cracked in 4 hours by a single GPU, or in minutes by a cluster. A large KDF helps, but damages user experience and again starts to become fragile if your threat model includes ASICs (a $3m expense or so for an attacker. That's a practical sum for many applications). To put things in perspective, a CPU can do about 2^20 hashes per second. A $3m ASIC cluster (made entirely from scratch) can do about 2^52 hashes per second. It's obscenely asymmetric. For high security accounts, you really want like 64 bits of entropy in your password plus a KDF, or you want 80 bits without a KDF. KDFs have another major problem. If you forget a word in your password, and you also have a KDF, you have to fight your own KDF to discover that last word. You don't want that barrier. edit: was off by a factor of 1000 in my ASIC math. $3m in ASICs can do about 2^52 hashes per second, not 2^42
  - yflu 9y ago
    Then I add another word or two and make that 44 bits 55 or 66 bits. The strategy itself still works, even if the particular details of implementation change.
  - Ajedi32 9y ago
    The XKCD comic includes this note: > 1000 Guesses/Sec (Plausible attack on a weak remote web service. Yes, cracking a stolen hash is faster, but it's not what the average user should worry about.)
    - tempay 9y ago
      Provided they don't use the same password for several services
      - Ajedi32 9y ago
        In which case, sooner or later they'll probably end up using the password on a site that stores passwords in plaintext, and after that no amount of entropy will help.
- JohnStrange 9y ago
  Maybe I'm paranoid, but I advice to my customers that any passphrase with an entropy below 80 bits is insecure, around 140 bit is fairly secure, and anything above 200 bit entropy is very secure.
  - Abekkus 9y ago
    Assuming that password complexity is the weak link in their practices.
    - JohnStrange 9y ago
      Uhm, no, independently of that...
  - contravariant 9y ago
    I can understand why you'd want to be more careful with generated passphrases, but 80 bits of entropy is like a 16 character long alphanumeric password. That seems fairly secure to me for most purposes. Unless the hash is 'broken' but then your options are fairly limited anyway.
    - JohnStrange 9y ago
      80 bits of entropy is between 12 and 13 visible ASCII characters and between 14-15 ASCII letters. Yes, if you go below that I'd say it's insecure. It's a conservative estimate, I admit. An entropy of 60 might be okay, too, but there is no harm in making passwords more secure.
      - Bromskloss 9y ago
        > but there is no harm in making passwords more secure. Well, it makes them harder to remember and slower to type (and increases the chance of making an error and having to type it again). I hesitate slightly to do things that require me to type my long password. :-)
- bitexploder 9y ago
  Going to just add some thoughts here: It isn't quite right to treat each word as a symbol either from the information theoretic standpoint. If an attacker /knows/ your password is xkcd style words there is still cracking cost to choosing to crack using only that strategy. To achieve similar entropy for a classic password you would need say, 8 characters A-Za-z (~7.71 characters required to achieve 44 bits of entropy) (https://en.wikipedia.org/wiki/Password_strength https://en.wikipedia.org/wiki/Password_strength) But now the cracker has to run two strategies (word based, and classic character based). Granted it is only "times two" and not an exponential increase you get by increasing your number of available symbols or better yet total number of symbols. In a "readable words dictionary" with say 75000 words you can achieve ~64 bits of entropy. This is also completely ignoring some facets of password storage and hashing. For example, ASICs are good, but not great against scrypt since it is memory hard. So storage format matters a lot. In an offline attack of the worst case known scenario (MD5) lets just call it 25,000-100,000 MH/s in your house without a crazy amount of expense. That works out to a (on the shortest end of things for 'desktop cracking') about 5 - 6 years. That password is safe for some time against password dumps and such. No one but a high resource attacker that wants your specific password is going to crack it in the near future if a password like that was leaked as an md5 hash. No cute articles about 90% success rates of cracking, etc. So, the security always comes down to the needed security. Right now 5 years is pretty good. You hopefully change your passwords every 5 years. Add in a 5th symbol in word based passwords and you hit 80 bits of entropy though. That takes the crack time up to about 383,000 years. It is such a vast difference it isn't even funny. So: 5 or 6 years vs 383,000 years. Basically, use a 5th word. This is all for a desktop cracker, but even someone with 10000 times the desktop crackers resources (e.g. ~50000 GPU, or at least several hundred ASICS) would still be working on a scale of decades.
- antisthenes 9y ago
  The actual XKCD password generator suggests using padding as well. Using non-alphabet padding symbols (even if they are all the same and as trivial as 111 or !!! at both ends) will improve entropy by a decent amount while being just as easy to remember. However the password itself is still only 1 aspect of security. There are many cases where there are far easier attack vectors that don't including cracking hashes.
mdemare 9y ago
The strategy is fine - the problem is that people don't use a random number generator. This is how you get a 3-word password with 54-bits of complexity (on a mac with a recent ruby): ruby -e 'puts File.read("/usr/share/dict/words").lines.sample(3).map(&:chomp).join(" ")' "applewife holographic intercommonage" Easier to remember than `rand(254)` => 16495714355860079
- binarytransform 9y ago
  Yeah super. Let me scale that for my bank, car loan, house loan, credit cards, FB, IG, Twitter, Email, HN, Coursera, EdX, Udacity, Udemy, Concur, forums, Netflix, LinkedIn, Paypal, Slac, Spotify, Hulu, AppleID, Reddit, Amazon, health insurance, college alumni page, Digital Ocean, WSJ, GoDaddy, hotel points, and airline miles sites.
  - balladeer 9y ago
    Except some you can outsource everything to a password manager. I think I remember just these passwords: my 2 banks (that keep my savings), stock broker, primary email a/c, AppleID, personal VPS. For these too I keep very personal hints (no one else can guess) in KeePass (just in case). Master passwords for LastPass and KeePass are quite difficult and I don't keep its hint or anything anywhere. It's a risk I decided to take. On the downside I have not changed these two passwords in a long time. Rest goes to LastPass (100s of them).
  - artmageddon 9y ago
    I finally started using KeePassX so I could keep track of the insanely long and randomized passwords it creates across the same plethora of sites you've listed. I love using it, but there's no way in hell I can quickly update so many different credentials conveniently(e.g. update your password every 6 months or so? Just kill me now)
    - distances 9y ago
      I've used password managers for about 15 years now. I just counted I have ~400 passwords saved, most of which I'm obviously not using and a large number for services that do not even exist any more. As I can't be bothered to even check which ones to delete, I will definitely not be updating any of those.
admiun 9y ago
The XKCD method of generating passwords [1] does not imply 'best case' entropy of crackers going after each individual character. Instead it clearly states 44 bits of entropy which is the 'worst case' entropy when the attacking knows your exact method and dictionary used when generating the password. I'd argue that when targeting the same number of bits of entropy the XKCD method is still easier to remember than a bunch of fully random characters. [1] https://xkcd.com/936/ https://xkcd.com/936/
Bromskloss 9y ago
> Sadly the "long passphrase" advice is also out of date. It relies on the naive idea that all password cracking is done brute-force, one character at a time. I thought the point was that a increasing the length typically does more for you in terms of entropy than increasing the size of the alphabet. > The tl;dr is that any strategy short of full randomness is wrong. I don't know. You might want to have a password with some regularity to make it easier to remember (at the expense of being longer for a given entropy).
- Gregaros 9y ago
  Adversaries will simply use common pass-phrase words as though they were part of a larger alphabet. Depending on the distribution/definition of "common", 2-4 word passphrases are then much worse than an 8 character password, for exactly the reason you state.
  - jeremy_wiebe 9y ago
    Asking because I really don't know: How do they know that a given hash is multi-word passphrase versus average joe's single "word" character jumble? If they flip to using words as part of their alphabet and I'm using 4 unique words, they still have a large search space because the English language has so many more words than the alphabet has letters. So do they just do both? Seems like a huge expansion in computational work.
    - Bromskloss 9y ago
      They might not know and might have to guess, or do both. This makes it harder for them, but it's hard to quantify how much harder, so it's reasonable to assume the worst case, i.e. that they do know the procedure with which you generated the password.
  - Bromskloss 9y ago
    I'm not sure what point this is meant to counter.

GlitchMr 9y ago

The long passphrase idea as suggested by xkcd is fine, provided you pick random words. For instance, a database of 2048 words, and a 4 word passphrase has 44 entropy (2^44 possible passwords). >>> log2(2048 ** 4) 44.0 Even if somebody knows the pattern they have 17 592 186 044 416 passwords to try. You can further increase number of passwords to try by increasing number of words. Probably with advances of technology 4 words may be somewhat unsecure in the future, but 5 words is 2048 times harder to crack than 4 words password, so it should be still secure. The article in question shows three word passwords being cracked, but please note that three words is 2048 times easier to crack than 4 words, and probably very feasible to crack using graphics cards (provided poor choice of algorithms like MD5).

davemp 9y ago
Using non dictionary words should help greatly.
- KekDemaga 9y ago
  There are probably less non dictionary words than dictionary words, perhaps better advice is to use words from a random language other than your own so the password cracker might make a wrong assumption and waste his time?
  - mcherm 9y ago
    > perhaps better advice is to use words from a random language other than your own I think you may have missed the point that the XKCD cartoon was making. The question here is NOT how to generate passwords that are hard for computers to guess. That's a solved problem: simply generate a 128-bit string with a secure random number generator, and that's your secure password that computers can't guess easily. The PROBLEM is to generate a password where the ratio of ease-for-humans-to-remember to ease-for-computers-to-guess is maximized. Using words from a language other than your own is NOT a good way to maximize this. Introducing just one more randomly-generated word from your own language will be far more effective by this criterion.
    - 5555624 9y ago
      You don't need to speak a language, much less be fluent in it, to use some words from it in a password. Although I am not fluent in any language other than English, I know words in Irish Gaelic, German, Japanese, Spanish, and some other languages. It's easy to use a word I know in one of those languages as part of a password. (I do have one password that does contain a word from a language I don't speak.)
      - mannykannot 9y ago
        Up to a point, no doubt - but there is a good chance that the words you know from a language that you do not speak come from a small subset that is known by many non-speakers, so they may appear in cracking dictionaries, possibly gleaned from passwords that have been broken, or because they do sometimes appear in articles written predominantly in your language. Just for completeness, your strategy assumes the attackers are assuming a particular language - which I would guess is probably the right thing for them to do, if they are looking for low-hanging fruit.
    - chaoky 9y ago
      On the flip side, most of the world is multlingual or have at least been exposed to one other language. If you speak more than one language, mixing words from two or more basically renders dictionary attacks impossible, especially with number of languages and type unknown. I have words from non native languages in my passwords and they are just as easy or easier to remember.
Taek 9y ago
In practical terms, that's still not very many. GPUs can do 2 GH/s for a simple hashing function. Your 44 bit password can be cracked in 4 hours by a single GPU, or in minutes by a cluster. A large KDF helps, but damages user experience and again starts to become fragile if your threat model includes ASICs (a $3m expense or so for an attacker. That's a practical sum for many applications). To put things in perspective, a CPU can do about 2^20 hashes per second. A $3m ASIC cluster (made entirely from scratch) can do about 2^52 hashes per second. It's obscenely asymmetric. For high security accounts, you really want like 64 bits of entropy in your password plus a KDF, or you want 80 bits without a KDF. KDFs have another major problem. If you forget a word in your password, and you also have a KDF, you have to fight your own KDF to discover that last word. You don't want that barrier. edit: was off by a factor of 1000 in my ASIC math. $3m in ASICs can do about 2^52 hashes per second, not 2^42
- yflu 9y ago
  Then I add another word or two and make that 44 bits 55 or 66 bits. The strategy itself still works, even if the particular details of implementation change.
- Ajedi32 9y ago
  The XKCD comic includes this note: > 1000 Guesses/Sec (Plausible attack on a weak remote web service. Yes, cracking a stolen hash is faster, but it's not what the average user should worry about.)
  - tempay 9y ago
    Provided they don't use the same password for several services
    - Ajedi32 9y ago
      In which case, sooner or later they'll probably end up using the password on a site that stores passwords in plaintext, and after that no amount of entropy will help.
JohnStrange 9y ago
Maybe I'm paranoid, but I advice to my customers that any passphrase with an entropy below 80 bits is insecure, around 140 bit is fairly secure, and anything above 200 bit entropy is very secure.
- Abekkus 9y ago
  Assuming that password complexity is the weak link in their practices.
  - JohnStrange 9y ago
    Uhm, no, independently of that...
- contravariant 9y ago
  I can understand why you'd want to be more careful with generated passphrases, but 80 bits of entropy is like a 16 character long alphanumeric password. That seems fairly secure to me for most purposes. Unless the hash is 'broken' but then your options are fairly limited anyway.
  - JohnStrange 9y ago
    80 bits of entropy is between 12 and 13 visible ASCII characters and between 14-15 ASCII letters. Yes, if you go below that I'd say it's insecure. It's a conservative estimate, I admit. An entropy of 60 might be okay, too, but there is no harm in making passwords more secure.
    - Bromskloss 9y ago
      > but there is no harm in making passwords more secure. Well, it makes them harder to remember and slower to type (and increases the chance of making an error and having to type it again). I hesitate slightly to do things that require me to type my long password. :-)
bitexploder 9y ago
Going to just add some thoughts here: It isn't quite right to treat each word as a symbol either from the information theoretic standpoint. If an attacker /knows/ your password is xkcd style words there is still cracking cost to choosing to crack using only that strategy. To achieve similar entropy for a classic password you would need say, 8 characters A-Za-z (~7.71 characters required to achieve 44 bits of entropy) (https://en.wikipedia.org/wiki/Password_strength https://en.wikipedia.org/wiki/Password_strength) But now the cracker has to run two strategies (word based, and classic character based). Granted it is only "times two" and not an exponential increase you get by increasing your number of available symbols or better yet total number of symbols. In a "readable words dictionary" with say 75000 words you can achieve ~64 bits of entropy. This is also completely ignoring some facets of password storage and hashing. For example, ASICs are good, but not great against scrypt since it is memory hard. So storage format matters a lot. In an offline attack of the worst case known scenario (MD5) lets just call it 25,000-100,000 MH/s in your house without a crazy amount of expense. That works out to a (on the shortest end of things for 'desktop cracking') about 5 - 6 years. That password is safe for some time against password dumps and such. No one but a high resource attacker that wants your specific password is going to crack it in the near future if a password like that was leaked as an md5 hash. No cute articles about 90% success rates of cracking, etc. So, the security always comes down to the needed security. Right now 5 years is pretty good. You hopefully change your passwords every 5 years. Add in a 5th symbol in word based passwords and you hit 80 bits of entropy though. That takes the crack time up to about 383,000 years. It is such a vast difference it isn't even funny. So: 5 or 6 years vs 383,000 years. Basically, use a 5th word. This is all for a desktop cracker, but even someone with 10000 times the desktop crackers resources (e.g. ~50000 GPU, or at least several hundred ASICS) would still be working on a scale of decades.
antisthenes 9y ago
The actual XKCD password generator suggests using padding as well. Using non-alphabet padding symbols (even if they are all the same and as trivial as 111 or !!! at both ends) will improve entropy by a decent amount while being just as easy to remember. However the password itself is still only 1 aspect of security. There are many cases where there are far easier attack vectors that don't including cracking hashes.

mdemare 9y ago

The strategy is fine - the problem is that people don't use a random number generator. This is how you get a 3-word password with 54-bits of complexity (on a mac with a recent ruby): ruby -e 'puts File.read("/usr/share/dict/words").lines.sample(3).map(&:chomp).join(" ")' "applewife holographic intercommonage" Easier to remember than `rand(254)` => 16495714355860079

binarytransform 9y ago
Yeah super. Let me scale that for my bank, car loan, house loan, credit cards, FB, IG, Twitter, Email, HN, Coursera, EdX, Udacity, Udemy, Concur, forums, Netflix, LinkedIn, Paypal, Slac, Spotify, Hulu, AppleID, Reddit, Amazon, health insurance, college alumni page, Digital Ocean, WSJ, GoDaddy, hotel points, and airline miles sites.
- balladeer 9y ago
  Except some you can outsource everything to a password manager. I think I remember just these passwords: my 2 banks (that keep my savings), stock broker, primary email a/c, AppleID, personal VPS. For these too I keep very personal hints (no one else can guess) in KeePass (just in case). Master passwords for LastPass and KeePass are quite difficult and I don't keep its hint or anything anywhere. It's a risk I decided to take. On the downside I have not changed these two passwords in a long time. Rest goes to LastPass (100s of them).
- artmageddon 9y ago
  I finally started using KeePassX so I could keep track of the insanely long and randomized passwords it creates across the same plethora of sites you've listed. I love using it, but there's no way in hell I can quickly update so many different credentials conveniently(e.g. update your password every 6 months or so? Just kill me now)
  - distances 9y ago
    I've used password managers for about 15 years now. I just counted I have ~400 passwords saved, most of which I'm obviously not using and a large number for services that do not even exist any more. As I can't be bothered to even check which ones to delete, I will definitely not be updating any of those.

admiun 9y ago

The XKCD method of generating passwords [1] does not imply 'best case' entropy of crackers going after each individual character. Instead it clearly states 44 bits of entropy which is the 'worst case' entropy when the attacking knows your exact method and dictionary used when generating the password. I'd argue that when targeting the same number of bits of entropy the XKCD method is still easier to remember than a bunch of fully random characters. [1] https://xkcd.com/936/ https://xkcd.com/936/

Bromskloss 9y ago

> Sadly the "long passphrase" advice is also out of date. It relies on the naive idea that all password cracking is done brute-force, one character at a time. I thought the point was that a increasing the length typically does more for you in terms of entropy than increasing the size of the alphabet. > The tl;dr is that any strategy short of full randomness is wrong. I don't know. You might want to have a password with some regularity to make it easier to remember (at the expense of being longer for a given entropy).

Gregaros 9y ago
Adversaries will simply use common pass-phrase words as though they were part of a larger alphabet. Depending on the distribution/definition of "common", 2-4 word passphrases are then much worse than an 8 character password, for exactly the reason you state.
- jeremy_wiebe 9y ago
  Asking because I really don't know: How do they know that a given hash is multi-word passphrase versus average joe's single "word" character jumble? If they flip to using words as part of their alphabet and I'm using 4 unique words, they still have a large search space because the English language has so many more words than the alphabet has letters. So do they just do both? Seems like a huge expansion in computational work.
  - Bromskloss 9y ago
    They might not know and might have to guess, or do both. This makes it harder for them, but it's hard to quantify how much harder, so it's reasonable to assume the worst case, i.e. that they do know the procedure with which you generated the password.
- Bromskloss 9y ago
  I'm not sure what point this is meant to counter.