4 ms·

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

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'.

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'.