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

[Ron Frazier]

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

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

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