I've started using song lyrics when given the option of an extra-long password. I can get a very long string with little effort, and it's trivial to remember.

The best part is that any automated attack would have to deal with ringtone popups.

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 entropy than you'd think. A smaller number of independent random words is likely to be a better tradeoff.

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 "dictionary attack"?

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

If these types of passwords become popular, brute force crackers will build dictionaries of well known phrases.

That may be true, but we still end up better off. The compute time for the password cracker has gone up quite a bit, making it a more expensive endeavor (they've got to build dictionaries for both WKP's and passwords with fuzzing). It doesn't solve the problem, but it's a start in the right direction (away from fuzzing of dictionary words, which is clearly bad for human memory, and good for password crackers efficiency).

However, when using randomly chosen dictionary words to build phrases (not well known), the entropy shoots well above the level of being reasonable to crack in a lifetime.

Given that the knowledge about correct parts of a password based on known sources (pi, peace and war, song lyrics etc) drastically reduces the amount of possible solutions. But how would an attacker figure out the first part of such a password? What comes to mind are timing attacks http://en.wikipedia.org/wiki/Timing_attack What other possibilities did I miss?

EDIT: I get that having a long streak of my pass in a dictionary would reduce overall security but it's still unclear how a partial match in the dictionary would be detected.

But there's a long tail of song lyrics. If you pick something obscure, the odds of the attacker even having heard of it become very small (particularly if the attacker is from a different culture than your own). Pick something arty and incomprehensible, and the odds against someone else accidentally stringing those words together in some other context become astronomical.

For instance, I'd wager no cracker has ever heard the song containing the line "We barter images on the matrix". And that's one of the more intelligible lines from the song in question (from a 1978 album by the little-known prog-rock group Happy The Man). Pull it up on Google and you'll see what I mean.

If you don't know the song, of course, lines from it will be about as hard to remember as randomly chosen words. But if you do know it, you have a good mnemonic.

This gets into the whole "security through obscurity" thing. Ideally, you should use a password-generation system such that if the attacker knows your pasword-generation system (e.g. lines from songs) it would still be infeasible to guess your actual password.

Thats why the 4-random-words technique is good. According to XKCD, the 4-random-words technique generates about 17 trillion passwords---all equally likely.

But even with a long tail, song-lyric passwords relies on obscurity. I imagine there are much fewer than 17 trillion songs to choose from. And if the attacker knew some information about you (say from looking at your Facebook profile or your search history) I'm sure it could drastically weed out the search space.

The answer is obviously to write your own song or poem and not tell anyone about it. A passpoem, perhaps in the style of Lewis Carrol.

there might not be 17 trillion songs, but you aren't limited to the first 4 words of the song. there might be 100-300 words per song and you can pick your starting word anywhere you like.

But it falls into the same boat as any dictionary attack. Most people with a passphrase are probably going to use one from a song. 90% of them are going to use one of the top 1,000 songs, 90% of them are going to start at the beginning of a line. If we say there are ~20 unique lines in the average song, and most people won't use more than ten successive words even if it bridges a line, that's 1000 * 20 * 10 = a keyspace of 200,000. Trivial.

What this means is even if you decide you're going to be really secure and pick, say, the 30,000th most popular song, assume all songs have 200 unique lines (to account for sensical starting points in the middle of lines), and use 20 words from it, you're in a keyspace of only 120 million, which even if it takes 1ms to hash will be cracked in a day.

By contrast, four random english words chosen from the 2,048 most common has a keyspace of ~1.75e13, or 17,500,000,000,000.

Choosing a clever, unusual line from the middle of a very uncommon song is the passphrase land version of choosing a rare English dictionary word and replacing the vowels with numbers. If your hash gets compromised, it might as well be "password".

There's an easy way to defeat this:

   smellz like T33N SPIRIT!

Trivial to memorize. Unlikely to brute force.

I use phrases like that for the few locations where password managers don't reach (i.e. the password manager master password).

>.<

How is this an improvement? I now have to remember a song lyric, and some set of random manipulations of that song lyric. I've used that trick for passwords before, and it was a hassle. But that doesn't even matter— unless you're choosing the manipulations randomly (which is a contradiction in terms) you're falling right back into the exact damn trap the comic was about!

You've added ! at the end, replaced s with z, capitalized some words, and replaced vowels with numbers. These are already standard manipulations in a dictionary attack. And it's causing you to ignore the fact that you've chosen what is probably among the top 10 song lyrics used. "p4ssw0rd!" is "password" as far as a dictionary attacker is concerned. Calling this trivial to brute force is demeaning to the word "trivial". Your attacker wouldn't even laugh at you, because there'd be dozens of other hashes in the file just like yours.

It's been said over and over in these comments: the appearance of randomness is not randomness. Humans are horrible at making things random, as you've just demonstrated. Stop trying to make it look weird, and actually do the math.

It's fairly easy for me to remember those manipulations. But you're right insofar that this would probably be both safer and easier to remember:

   Smells like teen spirit, and I like that plenty mucho!

I'm too lazy to do the math on it, perhaps you can help out?

Edit: It's a little annoying to collect these downvotes from people who either haven't done the math themselves or are too lazy to explain their advanced attack methods.

In my naive opinion my string above is at least equivalent to a 12 character password from a set of "Mixed upper and lower case alphabet plus numbers and common symbols.".

I count each word (10) and both symbols (,!) as a character here.

According to [1] an 8 char password of that type would take 83½ Days to crack in a Class-F attack ("supercomputer"). I'm purely guessing that those additional 4 "chars" should put it well into the multi-year range, under the premise my other assumptions are not too far off and that the number of english words is quite a bit larger than the number of ascii characters/symbols.

Any of the downvoters care to debunk that with real math?

I'd be honestly curious about a worst-case analysis that assumes the fragment "Smells like teen spirit" does appear in the attackers dictionary.

[1] http://www.lockdown.co.uk/?pg=combi

Yeah, that's what I was getting at. Something like that is pretty much immune to naive brute force, even if we count "Smells like teen spirit" as a word. My guess would be that if it does get cracked, it would be by searching [lyric]+", and"+[some kind of Markov attack], but I honestly have no idea how one would work out the entropy in that model. It depends a lot on how the search is carried out, I think.

I guess we'll find out when passphrases become common :)

What happens when your obscure song makes the soundtrack for a hit movie next summer?

given how prone people are to mis-hearing song lyrics, the corpus isn't the full text of all published song lyrics as you suggest.

I make less typing mistakes with shorter, complicated passwords.

Long passwords are typing-error prone. With mobile devices, it gets worse, as typing is really painful.

I've had the opposite experience, where I'm more likely to mistype passwords with mixed case letters and symbols holding the shift key down too long. With mobile devices, it gets worse, as common words are easy to type, but symbols and mixed case are a pain.

It is a good point, though, that for frequently typed passwords on a good keyboard, you can engage your muscle memory. That allows you to type short passwords very quickly, and even remember passwords with your fingers that you've lost from your conscious memory!

Thats how I can remember 25 character passwords with symbols and mixed case. I am not thinking "43#gj(eO3%". I'm thinking "4-4-shift3-g-j-shift9-e-shifto-3-shift5". So basically you have about 47 keys with nice characters and they each have two of them.

Just use a random password generator with those 47 characters and type it 25 times into a notepad to pound it into your muscle memory. (and if you're paranoid, clean up your memory and swap file)

For the ones you don't use every few weeks, keep them in a password database like KeePass with 2 factor authentication and keep the key file on a thumb drive on your keychain.

mmm You got me thinking. You're right, both look error prone. Typing errors increase as it gets longer or more complicated.

I don't think entropy is the whole story. I would argue that although security-through-obscurity is a terrible, awful practice for systems, it's not that bad for personal password schemes. Using a nonce "system" for passwords, even if it's mathematically low-entropy, is still secure, at least enough for personal use.

For example, if I use single dictionary words fed through a trivial ceasar cipher, then that is mathematically very low entropy. Realistically speaking, however, it's relatively safe if the cracker doesn't know that's what I'm doing, because it's impractical for crackers to compute all possible low entropy "alternative dictionaries."

You'd be surprised. JTR does l33tspeak substitutions, one-row-up substitutions, keyboard walks, pretty much all of the common things everyone does because "no hacker would ever think of that."

I'll grant you that it's more important to have a password be difficult to guess, but that doesn't obviate the importance of it also being easy to remember. Even better, let's look for password schemes that are harder to guess and easier to remember at the same time.

It's easy to compare the entropy of two schemes as you're doing in your comment, but it's more difficult to objectively claim which is easier to remember. You argue that a random sequence of 12 characters is easier to remember than 4 words. If so, then I'd agree it would be a better scheme. However, I don't think that's the case. To really settle the argument, we should do some experiments - maybe someone already has?

Here's some examples I used a generator to create:

gangster insert madden quartic

overlong cage figurine hardship

trimmer wholly movie nadir

Bt].iu@0Soc*

Vf+pIW;C>\vp

'.}]Ba,g%@vI

Which do you think are easier to remember?

Are you serious? You think it's easier to remember 12 random characters than to remember four English words?

g6M;`Zt3^,d" vs selected aardvark badminton winnings

The way the human brain works, it would be at least as easy to remember 12 random words as 12 random characters.

The trouble is that by human intuitions, you think there's a strong inverse correlation between being hard to guess and easy to remember; but that's not always the case.

It's hard for humans to remember meaningless conjunctions of symbols, so we think they are hard to guess; so we err on the side of making them too short. Contrariwise, we think a sequence of just four words couldn't possibly be hard to guess because it's so easy to remember, but it's only easy to remember because we can use the meanings of the words to form an idea or image, something our brains are built for (unlike strings of meaningless characters).

This is why the word technique is better: it corresponds better with how we remember, while reducing two other risks: the risk of losing your password - non-trivial - and choosing too short a password.

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 already using special characters for our passwords.

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

First, that's still beside the point. You shouldn't evaluate a password scheme solely by entropy if it is a password you intend to memorize. XKCD argues that it's easier to remember 4 random words than 8 random characters.

Second, your example isn't very good because it assumes that every 8 byte character (save one) is acceptable, which is rarely the case, especially if you are trying to memorize them.

Finally, as another commenter pointed out, you've got your math wrong, and even your example has more entropy for the words than the characters.

Incorrect: It's 171k^4 and 255^8.

(which works out to 8.55E20 and 1.78E19)

Yep, and that's assuming 8 random bytes from extended ASCII. The other point of the article was that nobody actually makes a password from random characters because words are easier to remember. And I think it's disingenuous to suppose people will enter alt-codes and that nonprintable characters would be allowed, so assuming MENSA-quality users with internal random number generators, we get 95^8 ~= 6.6E15, a clear loss of entropy.

Actually, since you normally can't use anything but characters in the 0x20-0x7E range, the 8 char password has much less entropy: 95^8 ~= 6.63E15.

I love the backtick in my passwords. If a website accepts it and doesn't give me any issues, it's a decent indicator of basic security.

>the 8 char password has much less entropy: 95^8 ~= 6.63E15 //

Most of the word usage is going to be limited though too. testyourvocab.com put the average at 27k I think. We're looking for words one can remember easily so the word pool is going to be a lot lower - 15000^4 ~= 5E16 FWIW.

Right- I was just correcting the dude's math :-)

hey it was an honest typo

yeah thats correct

No, the single word password is based on a dictionary word with some chars replaced by other visually similar chars. That's much less than 8^255.

real complex passwords are more like '"^vmds!w*é$sé550µW"'-à the point of the post was to show the maximum theorical possibilities for both. As many pointed out not all 255 are usually printable and not all 171K words are used then that's for english only and not counting old english and not taking care of possible punctuation

It's actually closer to 92^8 (printable ASCII) or even 62^8 (if they only allow letters and numbers).