[ale] OT - making really strong pass phrases - was New encryption technology using a piece of paper

Michael H. Warfield mhw at WittsEnd.com
Tue Sep 6 17:17:09 EDT 2011


On Tue, 2011-09-06 at 16:44 -0400, Ron Frazier wrote: 
> Hi Michael W.,

> Thanks for the info.  OK, now I have to go find my scientific 
> calculator.  OK, I see what you're saying.  Each word has 2048 (at 
> least) permutations depending on the lexicon, so 11 bits of entropy per 
> word.  All I was saying was this.  If each word has 4 characters, all 
> lower case, and you have 6 words, then you have 24 total characters.  
> Your total number of permutations with words is 2048 ^ 6, which should 
> work out to the same number you quoted.  My calculator shows 7.379 x 
> 10^19.  2^66 comes out to the same thing.  However, if each group of 4 
> characters didn't have to be a word, but could be gibberish, and they're 
> still lower case, then the number of permutations for each group of 4 
> characters becomes 26^4 = 456,976 rather than 2048.  In the case of 
> gibberish characters in every character slot, still lower case, the 
> number of permutations for 24 characters becomes 26^24 = 9.107 x 10^33.  
> So, what I was getting at was that if you have 24 characters of random 
> gibberish, the attacker will have to try up to approximately 1 x 10^14 
> times more random permutations (the difference between 10^19 and 10^33) 
> to hit on your password.

> Now, I'm not saying pass phrases are not effective.  They obviously can 
> be if they're long enough.  Every thing you do to increase the alphabet 
> you're using, the more difficult the password is to crack by brute 
> force.  I know you already are familiar with all this.  I'm just 
> bringing it up for discussion for those people who haven't investigated 
> it as much.

> So, here are some various options to use for a 24 character password, 
> assuming the attacker knows your "word" strategy, if you're using one.

> 1) your original example, 6 words of 4 characters separated by spaces 
> from a 2048 word lexicon, disregarding spaces since attacker knows 
> they're there
>     2048^6 permutations = 2^66 permutations = 7.379x10^19 permutations
>     Time to crack offline at 100 billion guesses / second (single 
> powerful machine): 737.87 million seconds = 204.96 thousand hours = 8.54 
> thousand days = 23.4 years.
>        That ain't bad, for my Amazon login, assuming they'll let me put 
> all that in there.
>     Note that, if you aim a 1000 PC botnet (100 trillion guesses / 
> second) at the problem, this drops to 8.5 days, still a long time, but 
> doable for high value data.

> 2) 6 words, 4 characters each, upper and lower case characters used.  
> So, in the simplest case, each word could have the first letter lower 
> case or capitalized.  This doubles the number of permutations per word.
>     4096^6 permutations = 2^72 permutations = 4.722 x 10^21 permutations
>     Time to crack @ 100 billion guesses / second: 4.722 x 10^10 seconds 
> = 13.12 million hours = 546 thousand days = 1.5 thousand years
>        Now we're talking!
>     Time to crack @ 100 trillion guesses / second: 1.5 years

Ok...  First off.  Get off the hang up over 4 character words.  That's
not an essential element.  That's merely a characteristic of the OPIE
lexicon.  Actually, though, no it's not.  The OPIE lexicon is 1-4
characters.  "A" and "I" are in in the lexicon.  A lexicon can be all 4
character words, if you wish.  Or they can be longer.  The only matter
is that it's 2048 words in the lexicon.  You really probably would be
better off coming up with a different lexicon of phonetically unique
words that would make support even better.  You can even expand that to
4096 words for 12 bits per word it you like.  OPIE is just an example
that happens to be codified and standardized and happens to correspond
to the math the xkcd folks were using.

> Now, we've got upper and lower case in the picture.  Let's bring in 
> digits and symbols.  Lets assume we separate the words by a digit or a 
> symbol.  I'm assuming a total alphabet of 26 lower case, 26 upper case, 
> 10 digits, and 33 symbols for a total of 95 available characters.  That 
> means digits and symbols are 43 possible characters.  Assuming the 
> attacker still knows our word strategy, but not necessarily our 
> capitalization nor symbol strategy (except that trying simpler things 
> didn't work), we have the following:

> Permutations for words: 4096^6 = 2^72 = 4.722 x 10^21
>     Permutations for 5 digits / symbols between words: 43^5 = 147.008 x 10^6

Ah...  That's the whole point.  Yes you can go down this road and add
complexity (and misery) to the process but you can accomplish the same
task by adding words that are easy to read and process and much easier
to support.

Do the math again for 8 words.  88 bits of entropy.

At one time, 64 bit encryption was considered industrial strength.  DES
was 56 bits.  66 bits of entropy is 2^10 times stronger than single DES.
Do we consider it to be cryptographically secure?  Hell no...

You want AES strength, you need 12 words.  132 bits of entropy.

You can always add numbers and symbols and upper and lower case as you
feel.  The questions are...  "What does it buy you?"  "What does it cost
you?"  "Is it necessary?"  "Is it sufficient?"

> Now, the permutations for these two sets of things together will 
> multiply together, thus:
> 
>     Permutations for the whole shabang: (4.722 x 10^21) x (147.008 x 
> 10^6) = 694.174 x 10^27
>     Time to crack @ 100 billion guesses / second = 6.942 x 10^18 seconds 
> = 1.928 x 10^15 hours = 80.344 x 10^12 days = 220.121 x 10^9 years
>     Time to crack @ 100 trillion guesses / second = 220.121 million years
> 
> Now, my point is not that you need to protect your Amazon login for 220 
> million years from a botnet array.  What I am getting at is that, just 
> by adding capitalization and digits and symbols to the same pass phrase, 
> your protection from the botnet array attack goes from 8.5 days to 220 
> million years with very little change in the difficulty or memorability 
> of the pass phrase.  People with experience in cryptography may see this 
> as old hat.  However, people not as familiar with the math may be very 
> surprised how much of an insane increase in security just making these 
> little changes makes.  This is particularly relevant in the case of a 
> website that won't allow you to put a very long pass phrase in.  Say you 
> had a one or two or three word pass phrase.  No matter what you do to 
> it, it won't be incredibly secure.  However, if that's all you can put 
> in, adding upper / lower case, digits, and symbols, if you have a 
> choice, dramatically increases the level of security.  Also, using a 
> lexicon with more than 2048 words will dramatically increase security.
> 
> Sincerely,
> 
> Ron
> 
> On 9/6/2011 11:05 AM, Michael H. Warfield wrote:
> > On Tue, 2011-09-06 at 09:53 -0400, Ron Frazier wrote:
> >    
> snip
> >> many sites, good entropy if they're long, if attacker knows you're using
> >> words separated by spaces, his search for your pass phrase becomes much
> >> easier
> >>      
> > No it doesn't.  If he knows that you are using 6 words all in lower case
> > separated by a single space coming from 2048 words (assuming he even
> > knows your entire lexicon - change it how you want), the chances of him
> > guessing your password are one chance in 73786976294838206464 (2^66) per
> > guess.  That might just give him reason to shake his head an walk off.
> >
> > The xkcd example of 4 words from a similar lexicon gives you one chance
> > in 17592186044416 (2^44) per guess.  He's still not going to brute force
> > that.
> >
> >    
> 
> -- 
> 
> (PS - If you email me and don't get a quick response, you might want to
> call on the phone.  I get about 300 emails per day from alternate energy
> mailing lists and such.  I don't always see new messages very quickly.)
> 
> Ron Frazier
> 
> 770-205-9422 (O)   Leave a message.
> linuxdude AT c3energy.com
> 
> 

-- 
Michael H. Warfield (AI4NB) | (770) 985-6132 |  mhw at WittsEnd.com
   /\/\|=mhw=|\/\/          | (678) 463-0932 |  http://www.wittsend.com/mhw/
   NIC whois: MHW9          | An optimist believes we live in the best of all
 PGP Key: 0x674627FF        | possible worlds.  A pessimist is sure of it!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 482 bytes
Desc: This is a digitally signed message part
Url : http://mail.ale.org/pipermail/ale/attachments/20110906/ed8fed93/attachment.bin 


More information about the Ale mailing list