Live data from Hacker News

Xkcd Password Generator

preshing.com

291–299 of 299 posts

Re: Xkcd Password Generator

#291
post #238
post #236

Earlier quoted context omitted.

I wouldn't use a JS program served from somebody else's website to generate my password anyway. How do I know it's not sending them a copy of the passwords it generates?

Well, I watched network connections and saw none. Do that + use Incognito mode = you're probably good.

He recently changed it to use a random seed sent from the server instead of the client-side RNG. Over, I believe, unencrypted HTTP. Your suggested countermeasure would not have detected that attack; indeed, perhaps it was already in place before you reported no evidence of attacks.

It would, however, have made it harder for him (or your ISP) to tell whose password they'd stolen.

Re: Xkcd Password Generator

#292

Earlier quoted context omitted.

1) the predictability of the distribution of characters in the English language has nothing to do with this type of password - the symbols aren't characters, but words. 2) that figure of entropy per character of 1.3 bits per character only applies to English text , and the figure is low because there are a bunch of small words, like "and" and "the" that are regularly repeated. The entropy per character for words cont…

I am merely suggesting that the entropy can be less than what is estimated by looking only at the dictionary. Re 1: words still consist of characters Re 2: Certainly correct, but to ignore the possibility of English words having less entropy than it appears at first is odd given the patterns English words often follow. I'm interested in reading more about those entropy estimations, can you recall where you read about…

The mistake you are making is that you keep on wanting to treat a passphrase made up of words as being a 'text' in the sense that Shannon was using, but it is not a text in the Shannon sense of the word.

Shannon was analysing real world messages to arrive at that figure, not a string of random words. Here's a way of thinking it through that should help you see the problem clearly.

Let's imagine that Alice has just used a dictionary to generate a passphrase. Furthermore, let's imagine that the dictionary in question is a collection of 6 character or longer words pulled from "Pride and Prejudice". I'm pretty sure Jane Austen tops the 5000 words needed for such a dictionary.

Now, in the simple example, let's imagine that the passphrase is one word long. Bob is an attacker that knows the dictionary, He will guess the word in a maximum of 5000 tries. After 2500 he will have a 50% chance of having found the word.

Charlie, a second attacker, isn't going to use words as symbols, he's going to try and brute-force the word just by throwing random characters at the problem. He doesn't know the length of the word, so he's going to have to try all lengths of the word starting from one letter and working up. I trust that you can see that Charlie is going to need a lot more than 5000 guesses to find the passphrase.

David is a bit smarter than Charlie. He decides to use a Markov Chain of 3 character length to generate his guesses, so that the generated passphrases start resembling English words. The Markov chain was trained on text from the Sydney Morning Herald. David is going to do a lot better than Charlie, but that Markov Chain has to be capable of generating all of the words in my original dictionary, plus a bunch of other words, plus a bunch of gibberish non-words. He's clearly going to take more attempts than 5000 to find Alice's passphrase.

Evan is smarter still. He trains his Markov Chain using only words that are 6 characters or longer, and furthermore, he increases the chain length to 6 characters. He also teaches his Markov Chain that word seperators exist, and the Markov Chain generator is reset when a new word is started. Now we're talking - Evan's system will produce very few strings that are not actual words, but it will generate a bunch of words that were in the SMH, but not in "Pride And Prejudice", so he's going to still need more than 5000 guesses to be sure that he's found Alice's passphrase, so he still hasn't done better than treating the words as symbols.

There is one Markov Chain attack that gets nearly equal performance. Take Alice's dictionary, use it to train a Markhov Chain generator that knows about word separators, and that knows that the words don't have any probability links between them. But now your Markov Chain generator has just become a fancy way of picking words out of the dictionary. In other words, it has degenerated to a dictionary attack, not a brute force attack, and a dictionary attack is just another way of saying "treat the words as symbols" which means we're back to my original entropy calculations as being the optimal way of determining the entropy of the passphrase.

As I said at the start, your error is that you're trying to use randomly picked dictionary words as an English text in the Shannon sense of the word. Hopefully the example scenario that I just ran through will help you see why the distinction is important.

Re: Xkcd Password Generator

#293

Earlier quoted context omitted.

I am merely suggesting that the entropy can be less than what is estimated by looking only at the dictionary. Re 1: words still consist of characters Re 2: Certainly correct, but to ignore the possibility of English words having less entropy than it appears at first is odd given the patterns English words often follow. I'm interested in reading more about those entropy estimations, can you recall where you read about…

The mistake you are making is that you keep on wanting to treat a passphrase made up of words as being a 'text' in the sense that Shannon was using, but it is not a text in the Shannon sense of the word. Shannon was analysing real world messages to arrive at that figure, not a string of random words. Here's a way of thinking it through that should help you see the problem clearly. Let's imagine that Alice has just us…

I understand randomly selected words are not the same as the English text Shannon is talking about. However my point is that entropy may be lower than what it appears to be. I'm not saying it is 0.6 bits per character (or any other number). I'm saying that unless you words are long enough it is very likely that the entropy is lower than simply taking log(dictionary_size^word_per_passphrase)/log(2) The references to Shannon and Applied Cryptography were only made as supporting evidence that entropy of English text is lower than what it appears. I'm not claiming their exact numbers apply in this situation.

If we can't agree on that, the we must simply agree to disagree.

Re: Xkcd Password Generator

#294

Earlier quoted context omitted.

The mistake you are making is that you keep on wanting to treat a passphrase made up of words as being a 'text' in the sense that Shannon was using, but it is not a text in the Shannon sense of the word. Shannon was analysing real world messages to arrive at that figure, not a string of random words. Here's a way of thinking it through that should help you see the problem clearly. Let's imagine that Alice has just us…

I understand randomly selected words are not the same as the English text Shannon is talking about. However my point is that entropy may be lower than what it appears to be. I'm not saying it is 0.6 bits per character (or any other number). I'm saying that unless you words are long enough it is very likely that the entropy is lower than simply taking log(dictionary_size^word_per_passphrase)/log(2) The references to S…

* I'm not claiming their exact numbers apply in this situation.*

You see, the thing is, you kind of are making that claim. If entropy goes out to 3 bits per character, the one feeble point that you did have gets blown out of the water. The fact that you don't seem to understand that indicates that you really need to go back and reread a few books on Information Theory.

Look, for your own edification, try and come up with a scheme that will reliably beat a dictionary attack in terms of the number of attempts needed before finding a password taken from the dictionary. You could even write a simple program to test the idea. Take a dictionary of 5000 words with a length of 6 characters or longer (much shorter words than what your theory suggests should be secure). Select 100 words from the dictionary at random, and then run any attack of your devising against those words. If you can reliably get a better average number of attempts than 2500, I'll concede the point.

Until then, I'm here to tell you that you don't understand information theory as well as you seem to think you do.

Re: Xkcd Password Generator

#295
post #16

I prefer using a program like Password Safe ( http://passwordsafe.sourceforge.net/ ), and use a safe password that's a long sentence (with punctuation). Then I can use arbitrarily long and complex passwords for all my accounts, and not have to worry about memorizing them individually. The password safe can even be synced across computers using Dropbox.

GPG-encrypted free-form file (though it's fairly structured), edited via vim and a well-known "auto-encrypt/decrypt GPG files" configuration: http://vim.wikia.com/wiki/Encryption

(Actually, from that page, vim now has built-in blowfish encryption, which I'll have to look at -- yet another argument in favor of sharing tips on the 'TarTubes: you may learn something even when you're sharing your own knowledge).

Re: Xkcd Password Generator

#296
post #16

I prefer using a program like Password Safe ( http://passwordsafe.sourceforge.net/ ), and use a safe password that's a long sentence (with punctuation). Then I can use arbitrarily long and complex passwords for all my accounts, and not have to worry about memorizing them individually. The password safe can even be synced across computers using Dropbox.

GPG-encrypted free-form file (though it's fairly structured), edited via vim and a well-known "auto-encrypt/decrypt GPG files" configuration: http://vim.wikia.com/wiki/Encryption (Actually, from that page, vim now has built-in blowfish encryption, which I'll have to look at -- yet another argument in favor of sharing tips on the 'TarTubes: you may learn something even when you're sharing your own knowledge).

Erm: the blowfish encryption was in reference to the old '-x' vi encryption option (using a now pretty insecure Unix 'crypt' function).

A better "configure GPG edit mode" .vimrc is here: http://vim.wikia.com/wiki/Edit_gpg_encrypted_files

I believe that's based on the one first posted by Wouter Hanegraaff .

Re: Xkcd Password Generator

#297
post #232

Earlier quoted context omitted.

This is not entirely correct, we include non alphanumeric characters (punctuation) in our passwords occasionally because it increases the solution space for a brute force attack. While this doesn't really improve any individual password the fact that we occasionally include non alphanumeric charecters increases the possible password set from 62 possible charecters ^ password length to a something more like 90^passwor…

You seem to believe that you are saying something different from the comment you are replying to, but actually you seem to simply not understand it.

are you kidding, i'm pointing out the historical reasons for why we add punctuation chars in our passwords, as it directly impacts the solution space a brute force attack needs to cover.

Re: Xkcd Password Generator

#298
post #232

Earlier quoted context omitted.

You seem to believe that you are saying something different from the comment you are replying to, but actually you seem to simply not understand it.

are you kidding, i'm pointing out the historical reasons for why we add punctuation chars in our passwords, as it directly impacts the solution space a brute force attack needs to cover.

No, I'm not kidding. And the comment you were replying to already explained that.

Re: Xkcd Password Generator

#299
post #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.

I wrote this piece of code: https://gist.github.com/1149417

It's currently running at 3200000 tries per second on my Xeon machine. I am probably going to get bored before I find the right combination because I calculated it could take up to 52 days. :)

But anyways, it is still a lot less time than trying to bruteforce something like Tr0ub4dor&3 in my opinion.

It seems you like challenges, if I gave you a SHA1 hash of something similar to "Tr0ub4dor&3", would you be able to crack it (without rainbow table) under 52 days ? I don't think so.

Post reply on HN