I wrote my own program to produce XKCD-style passwords from a list of 2126 common words, and calculated some stats. I reproduced XKCD's calculation of 44 bits of entropy for 4 randomly-selected words. And I made a few mildly-interesting discoveries, and one more-interesting realization.
PASSWORD LENGTH: MORE = BETTER?
My average XKCD-style password length is 20.8 letters (over a large sample), which is a lot of typing. So I decided to limit word size. By filtering my list of 2129 words to nothing longer than 4 letters, I ended up with 709 words. That's not many, and 4 of them together only gives 37 bits of entropy. Not so hot. But if you string 5 of 709 words together, you get 47 bits of entropy, which is better than XKCD! And the average password drops to 18.3 characters.
I find that interesting: shorter passwords which produce more bits of entropy than longer passwords. Seems counter-intuitive, until you realize that opening it up to the full 2129 words increases average word length more than it increases entropy. (See below for the math.)
THE PASSWORDS
So, what do these passwords look like? Here's 10 of the XKCD-style: 4 words from the 2126 word set:
password: MostlyRelativeSpinAdvanced
length: 26
password: ForBasicallyThinkingExplain
length: 27
password: CookieArmyMysteryConference
length: 27
password: ExpectConvertQuarterbackPresentation
length: 36
password: EverybodyProductHotDemonstrate
length: 30
password: RockIndexWellFloat
length: 18
password: BehaviorNearlyPromotePercentage
length: 31
password: PocketSurviveFourLab
length: 20
password: MuchWeekWillAnd
length: 15
password: DivideMorePeakSeveral
length: 21
So, how easy are those to remember? Memorizing an XKCD-style password is about creating a mental picture or story around it. Use some imagination. It usually helps to make it amusing. How about the first one: "MostlyRelativeSpinAdvanced"? Well, I'm a bit of a science geek, so this one makes perfect sense. You have a particle stream, and most of the particles are moving at relativistic speeds. So measuring each particle's spin is a pretty advanced thing to do. Hmm ... what's the amusing part of that? Oh maybe that an actual physicist would roll his eyes at my explanation and say that I don't know the first thing about particle physics. But basically, I was able to imagine a mini-story or mental picture for each of those passwords, so while I might not be able to memorize all 10, I could easily memorize one of them.
What about the shorter passwords consisting of 5 words from the 709 words of 4 letters or less?
password: BuyWingSadRideSeed
length: 18
password: SeedPairTankJailDo
length: 18
password: PanBuryDenyDataOld
length: 18
password: GeneRiceTeaYetSin
length: 17
password: WallJailLabNextTent
length: 19
password: HallSnapCashRichRead
length: 20
password: WarmUsKeepRoseLess
length: 18
password: PortMarkSirYouLeaf
length: 18
password: HiAgoHipAnyBe
length: 13
password: EaseSkyRealTossFate
length: 19
Even though those are shorter (and more secure) passwords, I guess I find them more difficult to remember them. It's about creating a mental picture or story around those words. Since the words are random, they don't come out in any conceptually correlated way. So you stretch your imagination to encompass them. The more words in the password, the more you have to stretch.
Take the last password up there, "EaseSkyRealTossFate", and drop that last word to make it 4 words: "Ease sky real toss". My first thought is that "toss" is the children's game "ring toss". Sky and ease kind of fit since the game is usually pretty easy and you toss things towards the sky. The word "real" is kind of left out, but I imagine throwing something "real", like a laptop or a dinner plate, instead of a game piece. So I imagine the ease of tossing a real laptop into the sky. Yeah, that's stretching the imagination a bit, but maybe not too much. I could pretty easily remember EaseSkyRealToss.
But now throw "fate" in there and my whole mental picture falls apart. I guess I could say that when the laptop lands, its fate will be sealed, but ... not sure why ... but I would have much more trouble remembering it.
So I'll be sticking to 4 words and more typing.
THE MATH
Passwords are basically taking a set of N things, and taking L of them out with replacement. For example, a 4-digit PIN consists of a set of 10 digits (N=10), and you take 4 digits out (L=4) with replacement. The "with replacement" simply means that you might take the same digit out more than once (e.g. 2338). So the entropy of a 4-digit PIN is 10**4 *(10 to the power of 4), which is 10,000. To get that in terms of bits, take the log base 2 of it to get 13. So 13 bits of entropy.
Another example: 8 randomly-selected letters for a password. Let's assume lower-case only, and no digits or special characters. The set of N things is the letters of the alphabet, so N=26. By taking 8 characters, L=8. 26**8 = 208 billion. Log base 2 of that is 37 bits of entropy. Cool. Now let's do random upper/lower case. N=52, and 52**8 = 53 trillion, giving 45.6 bits of entropy. Add in 0-9: N=62, 62**8 = 218 trillion, giving 47.6 bits of entropy.
So, back to my XKCD-style passwords. My original set of 2126 words, taking 4 at a time, gives 2126**4 = 20 trillion, which is 44.2 bits. My reduced set of 709 short words, taking 5 at a time gives 709**5 = 179 trillion, which is 47.3 bits.
However, see my next blog post for an observation about random password generators and entropy.
MORE WORDS?
My list of 2126 words actually comes from a list of 3000 words from Education First. I filtered it to limit word length to 7 or fewer characters, resulting in my 2126 words. Note to the rigorous: you'll find that I'm 2 words short; it made my code easier to ignore the first and last words.
So how about if I remove that filter and pick 4 words from the entire set of 2998?
2998 ** 4 = 80 trillion, which is 46 bits. I.e. going from 2126 words to 2998 increases the entropy by 2 bits. My average password length jumps to 25.6, which is 5 more characters. I tried a few other word length limits and decided that 7 is best.
THE PROGRAM
See https://github.com/fordsfords/pgen Be sure to use "-r" if generating an actual password you want to use.
No comments:
Post a Comment