7 ms·

Relevant XKCD: http://xkcd.com/936/ http://xkcd.com/936/

laumars 14y ago
That's another common misconception as that advice is only true for brute force attacks, which are usually only the last resort for password crackers. Dictionary attacks are pretty sophisticated these days so I really wouldn't gamble on a short list of common words being secure these days.
- marcosdumay 14y ago
  If you think Randal calculated the entropy wrong, state so, and show the error. Your argument from incredulity won't add anything to the discussion.
  - laumars 14y ago
    I did state so. You're still thinking in terms of brute force attacks but actually dictionary attacks are more common as they rattle off the 'low hanging fruit' much quicker. The danger of using common words like Randall did is that they might be in the dictionary so get cracked even before the attacker attempts to brute force the remainder of the passwords from a stolen database. In fact around half of the passwords people pick are vulnerable to such attacks (i'm on my phone though so can't easily cite a reference (I'm out of town this weekend) but it averages at either 40% or 60% of passwords use "guessable" / common terms) If Randall has thrown in some punctuation and numbers then he's reducing the odds of that password being cracked. But as the example stood, it's advertising complacency against the most common method of modern password cracking.
    - dllthomas 14y ago
      Um, no. It is absolutely the case that dictionary attacks are better than per-character brute force against the passwords Randal suggests, but he's not calculating entropy based on per-character brute force. He's calculating entropy based on per word brute force, and if the words are in fact chosen randomly that's the best you can do. Any dictionary attack against XKCD-style passwords are a brute-force attack in word-space. "Throw[ing] in some punctuation" does comparatively little.
      - laumars 14y ago
        I never said Randall calculated the entropy per character (please don't create arguments I didn't raise) and the reason I said adding punctuation might help is because it reduces the odds of the word being in the dictionary (if you're using terms not in a dictionary, then that dictionary attack will fail. Period). However even with adding punctuation theres still a chance the term is common enough to be included in a dictionary, so completely random passwords, while harder to remember, will be more secure. I cited a link in another fork of this comment where a pen tester comments about the words included in modern dictionary attacks.
        dllthomas 14y ago
        > I never said Randall calculated the entropy per character[.] You said: > You're still thinking in terms of brute force attacks but actually dictionary attacks are more common as they rattle off the 'low hanging fruit' much quicker. But the entropy calculations assume the attacker has the word-list. There is no low-hanging fruit, here. Strings generated by the algorithm are lowest-hanging, but they're all at the same height, and that's the number of bits calculated. The only attack is a brute force attack against word sequences. It is obviously true that anything that's not going to be checked is going to be stronger than anything that is, but the correct assumption is that your key generation algorithm is public, and building something to attack Randall's algorithm plus punctuation is not significantly harder than building something to attack Randall's algorithm as specified (a few extra bits, to be sure, but adding another word or increasing the list you're drawing from will be more effective). Incidentally, producing a literal dictionary is likely to be way slower than drawing words from the dictionary directly, since 1000 words will fit in memory and maybe even cache, while a trillion phrases is going to barely fit on disk. > [C]ompletely random passwords, while harder to remember, will be more secure. This is certainly the case, for a given password length. But the important point the comic is making is that we shouldn't be worried about conserving password length but about conserving memorability (and perhaps ease of typing), and for a given memorability the phrase is likely to be more secure.
        laumars 14y ago
    - NitpickMore 14y ago
      All the words he is using are in your dictionary but you don't have all the combinations of all the words in your dictionary. If you have "Apple", "Baker", and "Charlie" in your dictionary, it doesn't help with "Apple Baker" or "Apple Charlie".
      - laumars 14y ago
        You don't need the word combinations. Dictionary attackswwill do that part for you (a bit like a brute force, but by cycling words instead of characters)
      - dllthomas 14y ago
        This misses the point. The comic assumes a dictionary attack - that is to say, not brute-forcing character-by-character but rather word-by-word, whether this is constructed in advance in a static dictionary (possible, for 4 words from 1000; less possible for larger) or generated in a stream (likely more efficient regardless). Cryptographically, it's a dictionary attack - you're confining your search space based on guesses (in this case, we're assuming entirely accurate guesses) about the shape of the password. The point is that in the face of this, it's still more secure than the "variations on a single word" type of password, and can be easily made sufficiently secure for high security tasks (8 words => ~80 bits, and longer lists make it easier still) while remaining comparably memorable.
        DanBC 14y ago
        A dictionary attack uses a pre-built dictionary of (words OR phrases). A brute force attack takes an input of (characters OR words) and creates a (word OR passphrase) to test. It doesn't help that you've made this mistake several times in this thread. Imagine a 4 word diceware phrase. One attacker has the diceware list of words. The attacker knows we have a 4 word phrase, and so starts kludging different 4 word combinations of the diceware phrase. This is a bruteforce attack. It is not a dictionary attack.
        dllthomas 14y ago
        It's a brute-force attack in word space; it's a dictionary attack in character space - you are picking guesses expected to be more likely.
    - KMag 14y ago
      > "The danger ... is that they might be in the dictionary" Randal's entropy calculation clearly assumes a dictionary of about 2048 words, where the attacker has perfect knowledge of the dictionary at her disposal. Randal's entropy calculation is correct, and the point of the cartoon is that 44 bits of entropy is much stronger than the passwords most people create using common password advice. Personally, I think 44 bits is way too little entropy for a password, but I would be happy if my grandmother started using 44-bit passwords.
      - laumars 14y ago
        I got the point of the cartoon and I never argued that Randalls figures were wrong. I just think it's bad advice to give none technical people to say common words are secure because there's a risk that they won't use a sufficiently long (read: number of words) password. At the end of the day, the whole password model is broken, and Randall summed that part up succinctly.
- bnegreve 14y ago
  I agree, if you only pick words from the top 1000 most common english words it only takes 1000^4 = 1 trillion tries to crack a four words sentence. This is still quite a lot but much more reasonable than cracking a 8 chars random password with brute force.
  - dllthomas 14y ago
    He didn't compare to an 8 char random password. However, an 8 char random password is much harder to remember, and itself only contains (assuming 100 possible characters) only 10 quadrillion (or 53 bits) which is still somewhat weak. Including less common words, and using 5 of them, makes things significantly better. > grep '^[a-z]\+$' /usr/share/dict/words | wc -l gives 62887 on my system, which is almost 16 bits per word, so 4 puts us at over 63 bits and 5 at over 79 bits, or roughly 15 quintillion and 1 septillion respectively. Assuming brute force over sequences of words from the same dictionary and of the correct length, at a billion tries each second, it'll take over 200 years to crack the former and over 31 million years to crack the latter.
    - laumars 14y ago
      Modern dictionary attacks use common terms that have been generated from analyzing the passwords that have been stolen from past attacks. So the dictionary isn't just a list of English words but in fact a catalog of terms that people do use for passwords in real life. This makes them much more effective than dictionary attacks off old.
      - dllthomas 14y ago
        Analyzing passwords that have been stolen helps you build a better dictionary. The math in the comic assumes an optimum dictionary has been constructed to attack this kind of password by inspecting the algorithm; no dictionary attack is going to do better than that without doing something like attacking the RNG used to generate the passwords (and if that's feasible you're just as vulnerable regardless of what approach you use).
- Samuel_Michon 14y ago
  So how about a combination of: * A relative’s name that isn’t particularly common * The (partial) title of your favorite foreign language film or song * A slang word from the area you grew up in * The (partial) company name of one of your parents’ (former) employers Those should be easy enough for you to remember, but will not show up in most dictionary lists. Alternative: you could use your pornstar name ;)
- ajross 14y ago
  You misunderstood the algorithm. Any single word is subject to a dictionary attack. But given a list of 4096 words (12 bits), choosing 4 of those randomly gives you a 48 bit password. There are no feasible dictionary attacks against a 48 bit space. Or think of it this way, this algorithm can create a secure password from just 48 words chosen from a dictionary with just two entries! (let's call them "1" and "0" just to be contrary).
  - laumars 14y ago
    Using your example, it's equally secure to an 8 character password using base64 characters. Recently a pen tester published[1] that he can crack a 9 char pass (w/o punctuation, so 62^9) password in 90 seconds by parallel processing across several top end graphics cards. So I really wouldn't argue that a 48bit password is secure any longer. [1]http://arstechnica.com/security/2012/08/passwords-under-assault/2/ http://arstechnica.com/security/2012/08/passwords-under-assa...
    - dllthomas 14y ago
      Right, the necessary strength of passwords increases. Thankfully, the comic gave us a good method of generating passwords to an arbitrary strength, by increasing either the size of our alphabet (dictionary from which words are drawn) or length of our string (number of words), and shows how to calculate the resulting entropy. As I've pointed out elsewhere, 5 words drawn from alphabetic entries in /usr/share/dict/words (over 62 thousand) is very nearly 80 bits strong, or stronger than a 13 character completely random base64 string (which is going to be quite substantially harder to remember). If 62^9 (54 bits) takes 90 seconds, 80 bits takes nearly two centuries, and computing the hashes for phrases is actually going to take longer for each try to boot.
      - laumars 14y ago
        You keep thinking of dictionary attacks as being based on a verbatim English dictionary and I keep telling you that they're not. It's a refined dictionary with common terms used in real life passwords. However I do completely agree with your point about adding a number of more words. Passphrases are definitely another option, proving the service in question doesn't impose a restrictive maximum character limit (it's idiotic practice, but some do)
redacted 14y ago
Shameless self-promotion https://github.com/redacted/XKCD-password-generator https://github.com/redacted/XKCD-password-generator

That's another common misconception as that advice is only true for brute force attacks, which are usually only the last resort for password crackers. Dictionary attacks are pretty sophisticated these days so I really wouldn't gamble on a short list of common words being secure these days.

marcosdumay 14y ago
If you think Randal calculated the entropy wrong, state so, and show the error. Your argument from incredulity won't add anything to the discussion.
- laumars 14y ago
  I did state so. You're still thinking in terms of brute force attacks but actually dictionary attacks are more common as they rattle off the 'low hanging fruit' much quicker. The danger of using common words like Randall did is that they might be in the dictionary so get cracked even before the attacker attempts to brute force the remainder of the passwords from a stolen database. In fact around half of the passwords people pick are vulnerable to such attacks (i'm on my phone though so can't easily cite a reference (I'm out of town this weekend) but it averages at either 40% or 60% of passwords use "guessable" / common terms) If Randall has thrown in some punctuation and numbers then he's reducing the odds of that password being cracked. But as the example stood, it's advertising complacency against the most common method of modern password cracking.
  - dllthomas 14y ago
    Um, no. It is absolutely the case that dictionary attacks are better than per-character brute force against the passwords Randal suggests, but he's not calculating entropy based on per-character brute force. He's calculating entropy based on per word brute force, and if the words are in fact chosen randomly that's the best you can do. Any dictionary attack against XKCD-style passwords are a brute-force attack in word-space. "Throw[ing] in some punctuation" does comparatively little.
    - laumars 14y ago
      I never said Randall calculated the entropy per character (please don't create arguments I didn't raise) and the reason I said adding punctuation might help is because it reduces the odds of the word being in the dictionary (if you're using terms not in a dictionary, then that dictionary attack will fail. Period). However even with adding punctuation theres still a chance the term is common enough to be included in a dictionary, so completely random passwords, while harder to remember, will be more secure. I cited a link in another fork of this comment where a pen tester comments about the words included in modern dictionary attacks.
      - dllthomas 14y ago
        > I never said Randall calculated the entropy per character[.] You said: > You're still thinking in terms of brute force attacks but actually dictionary attacks are more common as they rattle off the 'low hanging fruit' much quicker. But the entropy calculations assume the attacker has the word-list. There is no low-hanging fruit, here. Strings generated by the algorithm are lowest-hanging, but they're all at the same height, and that's the number of bits calculated. The only attack is a brute force attack against word sequences. It is obviously true that anything that's not going to be checked is going to be stronger than anything that is, but the correct assumption is that your key generation algorithm is public, and building something to attack Randall's algorithm plus punctuation is not significantly harder than building something to attack Randall's algorithm as specified (a few extra bits, to be sure, but adding another word or increasing the list you're drawing from will be more effective). Incidentally, producing a literal dictionary is likely to be way slower than drawing words from the dictionary directly, since 1000 words will fit in memory and maybe even cache, while a trillion phrases is going to barely fit on disk. > [C]ompletely random passwords, while harder to remember, will be more secure. This is certainly the case, for a given password length. But the important point the comic is making is that we shouldn't be worried about conserving password length but about conserving memorability (and perhaps ease of typing), and for a given memorability the phrase is likely to be more secure.
        laumars 14y ago
  - NitpickMore 14y ago
    All the words he is using are in your dictionary but you don't have all the combinations of all the words in your dictionary. If you have "Apple", "Baker", and "Charlie" in your dictionary, it doesn't help with "Apple Baker" or "Apple Charlie".
    - laumars 14y ago
      You don't need the word combinations. Dictionary attackswwill do that part for you (a bit like a brute force, but by cycling words instead of characters)
    - dllthomas 14y ago
      This misses the point. The comic assumes a dictionary attack - that is to say, not brute-forcing character-by-character but rather word-by-word, whether this is constructed in advance in a static dictionary (possible, for 4 words from 1000; less possible for larger) or generated in a stream (likely more efficient regardless). Cryptographically, it's a dictionary attack - you're confining your search space based on guesses (in this case, we're assuming entirely accurate guesses) about the shape of the password. The point is that in the face of this, it's still more secure than the "variations on a single word" type of password, and can be easily made sufficiently secure for high security tasks (8 words => ~80 bits, and longer lists make it easier still) while remaining comparably memorable.
      - DanBC 14y ago
        A dictionary attack uses a pre-built dictionary of (words OR phrases). A brute force attack takes an input of (characters OR words) and creates a (word OR passphrase) to test. It doesn't help that you've made this mistake several times in this thread. Imagine a 4 word diceware phrase. One attacker has the diceware list of words. The attacker knows we have a 4 word phrase, and so starts kludging different 4 word combinations of the diceware phrase. This is a bruteforce attack. It is not a dictionary attack.
        dllthomas 14y ago
        It's a brute-force attack in word space; it's a dictionary attack in character space - you are picking guesses expected to be more likely.
  - KMag 14y ago
    > "The danger ... is that they might be in the dictionary" Randal's entropy calculation clearly assumes a dictionary of about 2048 words, where the attacker has perfect knowledge of the dictionary at her disposal. Randal's entropy calculation is correct, and the point of the cartoon is that 44 bits of entropy is much stronger than the passwords most people create using common password advice. Personally, I think 44 bits is way too little entropy for a password, but I would be happy if my grandmother started using 44-bit passwords.
    - laumars 14y ago
      I got the point of the cartoon and I never argued that Randalls figures were wrong. I just think it's bad advice to give none technical people to say common words are secure because there's a risk that they won't use a sufficiently long (read: number of words) password. At the end of the day, the whole password model is broken, and Randall summed that part up succinctly.
bnegreve 14y ago
I agree, if you only pick words from the top 1000 most common english words it only takes 1000^4 = 1 trillion tries to crack a four words sentence. This is still quite a lot but much more reasonable than cracking a 8 chars random password with brute force.
- dllthomas 14y ago
  He didn't compare to an 8 char random password. However, an 8 char random password is much harder to remember, and itself only contains (assuming 100 possible characters) only 10 quadrillion (or 53 bits) which is still somewhat weak. Including less common words, and using 5 of them, makes things significantly better. > grep '^[a-z]\+$' /usr/share/dict/words | wc -l gives 62887 on my system, which is almost 16 bits per word, so 4 puts us at over 63 bits and 5 at over 79 bits, or roughly 15 quintillion and 1 septillion respectively. Assuming brute force over sequences of words from the same dictionary and of the correct length, at a billion tries each second, it'll take over 200 years to crack the former and over 31 million years to crack the latter.
  - laumars 14y ago
    Modern dictionary attacks use common terms that have been generated from analyzing the passwords that have been stolen from past attacks. So the dictionary isn't just a list of English words but in fact a catalog of terms that people do use for passwords in real life. This makes them much more effective than dictionary attacks off old.
    - dllthomas 14y ago
      Analyzing passwords that have been stolen helps you build a better dictionary. The math in the comic assumes an optimum dictionary has been constructed to attack this kind of password by inspecting the algorithm; no dictionary attack is going to do better than that without doing something like attacking the RNG used to generate the passwords (and if that's feasible you're just as vulnerable regardless of what approach you use).
Samuel_Michon 14y ago
So how about a combination of: * A relative’s name that isn’t particularly common * The (partial) title of your favorite foreign language film or song * A slang word from the area you grew up in * The (partial) company name of one of your parents’ (former) employers Those should be easy enough for you to remember, but will not show up in most dictionary lists. Alternative: you could use your pornstar name ;)
ajross 14y ago
You misunderstood the algorithm. Any single word is subject to a dictionary attack. But given a list of 4096 words (12 bits), choosing 4 of those randomly gives you a 48 bit password. There are no feasible dictionary attacks against a 48 bit space. Or think of it this way, this algorithm can create a secure password from just 48 words chosen from a dictionary with just two entries! (let's call them "1" and "0" just to be contrary).
- laumars 14y ago
  Using your example, it's equally secure to an 8 character password using base64 characters. Recently a pen tester published[1] that he can crack a 9 char pass (w/o punctuation, so 62^9) password in 90 seconds by parallel processing across several top end graphics cards. So I really wouldn't argue that a 48bit password is secure any longer. [1]http://arstechnica.com/security/2012/08/passwords-under-assault/2/ http://arstechnica.com/security/2012/08/passwords-under-assa...
  - dllthomas 14y ago
    Right, the necessary strength of passwords increases. Thankfully, the comic gave us a good method of generating passwords to an arbitrary strength, by increasing either the size of our alphabet (dictionary from which words are drawn) or length of our string (number of words), and shows how to calculate the resulting entropy. As I've pointed out elsewhere, 5 words drawn from alphabetic entries in /usr/share/dict/words (over 62 thousand) is very nearly 80 bits strong, or stronger than a 13 character completely random base64 string (which is going to be quite substantially harder to remember). If 62^9 (54 bits) takes 90 seconds, 80 bits takes nearly two centuries, and computing the hashes for phrases is actually going to take longer for each try to boot.
    - laumars 14y ago
      You keep thinking of dictionary attacks as being based on a verbatim English dictionary and I keep telling you that they're not. It's a refined dictionary with common terms used in real life passwords. However I do completely agree with your point about adding a number of more words. Passphrases are definitely another option, proving the service in question doesn't impose a restrictive maximum character limit (it's idiotic practice, but some do)

redacted 14y ago

Shameless self-promotion https://github.com/redacted/XKCD-password-generator https://github.com/redacted/XKCD-password-generator