Live data from Hacker News

Xkcd Password Generator

preshing.com

251–260 of 299 posts

Re: Xkcd Password Generator

#251
post #154

Earlier quoted context omitted.

Be aware that adding to the length simply by taking more of the lyrics adds very little entropy. If you're trying "Oh say can you see" then it doesn't take a lot of extra bits also to try "Oh say can you see by the dawn's early light what so proudly we hailed at the twilight's last gleaming". Similarly, extended passages of text -- even if they don't come from a restricted corpus like that of song lyrics -- have less…

I can see your point in that the kolmogorov complexity of two lines in a song isn't much larger than one line. Similarly, 30 digits of pi and 300 digits of pi have very little difference in kolmogorov complexity. What I don't know is if state-of-the-art password guessers are great at recognizing larger patterns in the entire canon of human knowledge. I.e. is there a "common phrases" attack that's analogous to a "dict…

Google released the world's largest corpus and did us a favor by analyzing it for n-grams. For example, they found that the phrase "serve as the initial" was over a 100 times more common than the phrase "serve as the insurance". [1] For $150 you can buy the 24GB data set yourself, so it's a fair assumption that makers of password crackers could reliably guess common phrases first. [2]

[1] http://googleresearch.blogspot.com/2006/08/all-our-n-gram-ar... [2] http://www.ldc.upenn.edu/Catalog/CatalogEntry.jsp?catalogId=...

Re: Xkcd Password Generator

#252
post #96

Earlier quoted context omitted.

Don't forget spaces. And Poland. Another point is that letter placement within words is significantly non-random. By intelligently choosing which letters to try in each position, the hacker could at the very least minimize the number of tries by an order of magnitude for the first word.

I probably shouldn't announce, in a forum, that using Don't Forget About Poland! as a passphrase seems like an awfully tempting for someone like me :) (American by birth, Polish by heritage) Speaking of the example I just presented, how much more effective would it be to include special characters within these long passphrases? Obviously the goal is to be able to remember them, but surely most if not all of us, are a…

When counting the entropy you would probably count each word as a single entry, and each special character as an entry (and disregard spaces).

* By capitalizing the words you've doubled the search space for words (assuming that the search space starts with all words lowercased)

* You could increase the search space for each word by 200% (from the space of all lowercase words) by including the possibility of words in all caps (it's unlikely for people to start using alternating case in the middle of words).

* The ' in "Don't" doesn't increase the search space that much because there are a small number of (common) contractions like that, and each of them would only break down into 3 permutations:

  don't
  dont
  don t
(though the last one is highly unlikely). So you're adding maybe 30 more words to a search space much large than that.

* As far as the special character is concerned, it probably doesn't add too much to the search space. You can break down your phase like so:

  Don't Forget About Poland!
              ||
              \/
  {item} {item} {item} {item}{item}
              ||
              ||  Disregard whitespace (acquire entropy!)
              \/
  {item}{item}{item}{item}{item}
So now you've got 5 items. Each item could be either a word or punctuation. The search space for words is huge. The search space for punctuation is small. Your algorithm just has to realize that if it chooses punctuation for one of the items, then it doesn't bother to use whitespace to separate it from the preceding word ("word," vs "word ,").

* You can also further reduce the effects of punctuation on the search space by realizing that punctuation will almost always follow a word, and not other punctuation. This also discounts punctuation as the first item in the passphrase too.

Edit:

Upon further though, if the attacker uses a simplified algorithm to account to upper-/lowercase, then it may not have that much of an effect on the search of each individual item (i.e. n!4 instead of (n+4)!). An attacker could break the common instances of case down into:

  * All words lowercased  "don't forget about poland!"
  * All words uppercased  "DON'T FORGET ABOUT POLAND!"
  * All words titlecased  "Don't Forget About Poland!"
  * First word titlecased "Don't forget about poland!"
This discounts the possibility of people alternating titlecase across words, because that's probably as likely to happen as people alternating case within words (e.g. WoRdS lIkE ThIs). Granted, this also discounts proper nouns in the middle of the passphrase (things that don't require extra effort for people to remember to capitalize).

Re: Xkcd Password Generator

#253

I find the idea incredibly stupid. If I know someone who used that precise generator to produce his password. Then I know that the generator has less than 2000 words in the dictionnary. It then takes me only a few minutes to guess his password, rather than 550 years. Conclusion: Don't ever use this password generator, write you own, and tell no-one about it.

  4b02d9f6353a8f36fbb092f040d5a31cdf6841f2

You up for a challenge? I just generated a pass phrase with this generator, and hashed it with SHA-1 (echo -n ... | sha1sum), no salting or anything else special. Feel free to brute force it.

Re: Xkcd Password Generator

#254
post #18

I would actually advise going against this advice. While it isn't a best practice, password sharing can and does happen, as does shoulder-surfing. It would take a LOT of effort to memorise my password, but a simple four word password will probably be remembered by accident. In a year's time if I piss a friend off, I don't want my Facebook password to be readily accessible in their memory. I think more people need to…

>I think more people need to learn to remember arbitrary strings. The entire point is that humans aren't very good at doing this. >(Note: This doesn't really apply to me or most of us here in most cases, but for example my WiFi password is of the form "Mycatsname9" and yet my neighbour still has to ask me for it whenever her phone forgets it) This is actually exactly the kind of scenario where using pass phrases make…

> The entire point is that humans aren't very good at doing this.

How true is this? Because everyone that tells me "I have a bad memory" doesn't even know the most basic tricks.

> This is actually exactly the kind of scenario where using pass phrases makes the most sense

I agree, actually - I don't mind if my neighbour does remember it, I was just trying to illustrate that things that are easy to remember are remembered by accident, and things like that are easily forgotten without effort.

Re: Xkcd Password Generator

#255
post #164
post #18

I would actually advise going against this advice. While it isn't a best practice, password sharing can and does happen, as does shoulder-surfing. It would take a LOT of effort to memorise my password, but a simple four word password will probably be remembered by accident. In a year's time if I piss a friend off, I don't want my Facebook password to be readily accessible in their memory. I think more people need to…

So you're advising against what appears to be a more practical and secure methodology on the basis that it's worse when you share your password? If you share your password, your exact problem is that you're sharing your password -- it's not how easy or hard the password is to remember. In fact, why does this even have any significance when the person you're sharing it with can just write it down? Oh and if within a y…

> So you're advising against what appears to be a more practical and secure methodology on the basis that it's worse when you share your password?

Iff you share your password then yes, you should use a scheme more suitable for that. And yes we shouldn't be sharing passwords, and if we do we should be changing them, but in the real world where most people don't do that I don't think we should encourage passwords which their friends will remember easily - because that is a very common attack vector.

Re: Xkcd Password Generator

#256
I tried to generate all possible permutations of 4 of the 2000 most popular words in the English language.

My computer failed miserable after about 2000000 permutations and considering there is 10^13, i wont be making a rainbow table for this new type of password.

Re: Xkcd Password Generator

#257
post #73

Note that 44 bits of entropy is still nothing if you want protection from off-line attacks on password hashes. A couple of GPUs together can calculate a billion hashes per second, which eats through 2^44 possible passwords in only a few hours. This was recently demonstrated when the mtgox password database was compromised. edit : but this shouldn't be a problem if the password is properly hashed with bcrypt or some o…

But this approach scales at a much faster rate. Simply adding a fifth word throws even a billion-per-second attack out into hundreds-of-years territory.

Re: Xkcd Password Generator

#258

Earlier quoted context omitted.

Don't forget sites that require: "your password MUST contain at least one number, one uppercase letter, and one of the following characters: !, @, #, or $, but not %, ^, &, or *". I slap my forehead at how counterproductive these requirements are.

I have a couple of domains registered with 123-reg. To prevent unauthorised access to your account your password must contain 8 characters. Wait, what? They're right, too. You can't have 7 characters and you can't have 9.

Hi

I work on behalf of 123-reg.

We are working on changing this in future control panel updates.

Regards,

Ricky

Re: Xkcd Password Generator

#259
post #11

Assuming that this method for generating passwords gets popular enough, brute force tools will begin to create an optimized attack for these passwords. As there are so little words available, if I were to write a brute-forcing tool, I would try combinations of four words in my wordlist once I failed with my one-word-dictionary attack before I start trying out all characters. But all is not lost: Either use more words…

But the combinatorial explosion starts putting that out of reach fairly quickly.

Let's say you're restricting yourself to a dictionary of only 2000 common words.

A single word, up against a 1000-tries-per-second attack, would therefore fall within 2 seconds. Clearly bad. Adding a second word gives 2000^2 combinations to test against, which would require about an hour. Still not good. A third word, pushing that up to 2000^3, takes us to about three months, which is probably acceptable in many cases. The fourth word, at 2000^4 combinations, gets us to 500 years, which is well beyond what most people are ever going to need for a web-based password.

Now, if you want to bring this into the realm of passwords in other contexts, which can perhaps be brute-forced with several-billion-tries-per-second attacks, this approach still works: you just need to add an extra word or two. At 2,000,000,000 per second the four word combination might only take a couple of hours, but a fifth word takes that up to half a year, and a sixth out to the thousand years mark, whilst still falling easily within the standard 7±1 memory limit and being much much much easier to remember than m(yV7&NlxAIZNx3>&@p&8/kX.

Re: Xkcd Password Generator

#260
post #78

If you look at the source, their word list contains around 1600 words. That is just no where near enough. Using this would give you a very easy to crack password. You need to make up your own passwords with words you come up with.

On what basis is that "very easy"? Four words from 1600 is 1600^4 permutations, which would take over 200 years to test at a 1000/second attack.

Sure, if we're talking about a different type of password, and 2-billion-tries-per-second attacks, it'll fall in about an hour, but simply pushing that out to six words from that dictionary will still stymie that level of attack for a couple of hundred years. The size of the dictionary is much less important than the length of phrase you generate from it.

Post reply on HN