5 ms·

A line from a song is far weaker entropy-wise due to grammar. I wonder by how much. Common songs/writings would be vulnerable to a dictionary type attack. As f

A line from a song is far weaker entropy-wise due to grammar. I wonder by how much. Common songs/writings would be vulnerable to a dictionary type attack. As for the hundreds of passwords in your list, I'm convinced a password manager with a master password/3rd party auth/dongle is the way to go. Otherwise it's impossible to have unique passwords for all sites, rotate them, and remember them. Of course the risk is of losing the dongle.

bradleyjg 12y ago
> A line from a song is far weaker entropy-wise due to grammar. Interesting observation, the usual objection is due to the reduced Kolmogorov complexity which is difficult to quantify. Let's look at a modified diceware scheme of the form: Article adjective noun adverb verb adjective noun A (non-random) example might be: The young boy really likes video games. I'm not going to go through the diceware word list and classify each word, but assuming it is (or could be made) 50% nouns, 25% adjectives, 14% verbs, 11% adverbs and four articles you'd get roughly: 2 bits + 11 bits + 12 bits + 10 bits + 10 bits + 11 bits + 12 bits = 68 bits, which is the equivalent to a 5.2 word normal diceware password. Most of that reduction comes from the article. Here's a random example made with a diceware generator: an straw scrim ne adorn drab sybil I'm not sure that's any easier to memorize.
- abandonliberty 12y ago
  Interesting, I really like your approach to this. If we go back to the original 'song verse' idea, the space of all valid/written phrases is much smaller than the space of all possible word combinations. It's vulnerable to dictionary attacks based on commonly chosen phrases and frequency of phrase use in language/culture. Wikipedia only has 2.4 billion words, out of an estimated billion English words [1]. Perhaps we could add project Gutenberg with it's 50,000 works, and all the song lyrics we could find on the internet. We may hit 5 billion words. Let's estimate we also get 5 billion 6-word phrases out of that set. We've lost a ton of entropy. Ultimately, we suck at passwords. Machine capability will exceed what we can reliably, efficiently memorize. [1] http://www.languagemonitor.com/number-of-words/number-of-words-in-the-english-language-1008879/ http://www.languagemonitor.com/number-of-words/number-of-wor...
  - bradleyjg 12y ago
    This is the more usual objection that I was referring to with Kolmogorov complexity. Forty random digits has very decent entropy, 40 digits of PI, though they look very random, has much less. From that you can see how it's really hard to quantify exactly how much entropy there is an song verse that exists somewhere on the internet. If you wanted an absolute ranking of password strength, you'd first want to construct a universal brute force dictionary of passwords. Clearly the password 'password' is going to be near the beginning of the list and a password consisting of 48 randomly picked characters from [a-zA-Z0-9!@#$%^&*()] is likely to be somewhere out beyond the number of particles in the universe. But where exactly is "When you ain't got nothing, you got nothing to lose" going to appear? The first 10 million? billion? 10 billion? trillion? I really have no idea.
    - abandonliberty 12y ago
      We should be able to at least estimate an upper bound. If wikipedia has 2.5B words, let's generously assume 10B words. Let's allow phrase lengths of 1-10 words and arrive at 100B combinations. Optimistically we're at 37 bits, not even a 7 character [a-zA-Z0-9!@#$%^&()]. And unlike the [a-zA-Z0-9!@#$%^&*()], we could madly cut that down based on frequency and popularity. Therefore existing phrase passwords are security through minority. If they are adopted, they provide at best an order of magnitude or two over simple dictionary words. But we're kidding ourselves, most people still use 'password'.
- geoelectric 12y ago
  I wonder how many nouns, verbs, and adjectives we can dig up? Can we dig up 7776 each? While I think the set of adverbs would be much smaller (and obviously the set of articles will be very small) you could easily approach the same entropy as the Diceware method with a longer phrase. So long as there are 7 words in the phrase with 7776 possibilities each, you're equivalent. The rest is mnemonic glue. Since I think nouns are going to be the easiest set, shooting for something even more noun heavy could help. Edit: though since you're now syntactically more likely to be used in the wild, you'd probably want to search to make sure the phrase wasn't used in some other source. Problem there is the search leaks your password...

bradleyjg 12y ago

> A line from a song is far weaker entropy-wise due to grammar. Interesting observation, the usual objection is due to the reduced Kolmogorov complexity which is difficult to quantify. Let's look at a modified diceware scheme of the form: Article adjective noun adverb verb adjective noun A (non-random) example might be: The young boy really likes video games. I'm not going to go through the diceware word list and classify each word, but assuming it is (or could be made) 50% nouns, 25% adjectives, 14% verbs, 11% adverbs and four articles you'd get roughly: 2 bits + 11 bits + 12 bits + 10 bits + 10 bits + 11 bits + 12 bits = 68 bits, which is the equivalent to a 5.2 word normal diceware password. Most of that reduction comes from the article. Here's a random example made with a diceware generator: an straw scrim ne adorn drab sybil I'm not sure that's any easier to memorize.

abandonliberty 12y ago
Interesting, I really like your approach to this. If we go back to the original 'song verse' idea, the space of all valid/written phrases is much smaller than the space of all possible word combinations. It's vulnerable to dictionary attacks based on commonly chosen phrases and frequency of phrase use in language/culture. Wikipedia only has 2.4 billion words, out of an estimated billion English words [1]. Perhaps we could add project Gutenberg with it's 50,000 works, and all the song lyrics we could find on the internet. We may hit 5 billion words. Let's estimate we also get 5 billion 6-word phrases out of that set. We've lost a ton of entropy. Ultimately, we suck at passwords. Machine capability will exceed what we can reliably, efficiently memorize. [1] http://www.languagemonitor.com/number-of-words/number-of-words-in-the-english-language-1008879/ http://www.languagemonitor.com/number-of-words/number-of-wor...
- bradleyjg 12y ago
  This is the more usual objection that I was referring to with Kolmogorov complexity. Forty random digits has very decent entropy, 40 digits of PI, though they look very random, has much less. From that you can see how it's really hard to quantify exactly how much entropy there is an song verse that exists somewhere on the internet. If you wanted an absolute ranking of password strength, you'd first want to construct a universal brute force dictionary of passwords. Clearly the password 'password' is going to be near the beginning of the list and a password consisting of 48 randomly picked characters from [a-zA-Z0-9!@#$%^&*()] is likely to be somewhere out beyond the number of particles in the universe. But where exactly is "When you ain't got nothing, you got nothing to lose" going to appear? The first 10 million? billion? 10 billion? trillion? I really have no idea.
  - abandonliberty 12y ago
    We should be able to at least estimate an upper bound. If wikipedia has 2.5B words, let's generously assume 10B words. Let's allow phrase lengths of 1-10 words and arrive at 100B combinations. Optimistically we're at 37 bits, not even a 7 character [a-zA-Z0-9!@#$%^&()]. And unlike the [a-zA-Z0-9!@#$%^&*()], we could madly cut that down based on frequency and popularity. Therefore existing phrase passwords are security through minority. If they are adopted, they provide at best an order of magnitude or two over simple dictionary words. But we're kidding ourselves, most people still use 'password'.
geoelectric 12y ago
I wonder how many nouns, verbs, and adjectives we can dig up? Can we dig up 7776 each? While I think the set of adverbs would be much smaller (and obviously the set of articles will be very small) you could easily approach the same entropy as the Diceware method with a longer phrase. So long as there are 7 words in the phrase with 7776 possibilities each, you're equivalent. The rest is mnemonic glue. Since I think nouns are going to be the easiest set, shooting for something even more noun heavy could help. Edit: though since you're now syntactically more likely to be used in the wild, you'd probably want to search to make sure the phrase wasn't used in some other source. Problem there is the search leaks your password...