How to determine passphrase entropy?
in [Cryptography]
|
From: Mok-Kong Shen on 24 May 2010 09:45 Paul Rubin wrote: > ...... Each person picks a password from their > own distribution. [snip] For a private person under normal situations, I wonder whether employing 2 passwords (one important, the other don't care) couldn't be sufficient. The important one could be generated fairly well randomly, e.g. via casting die. Writing it down (if desired with some transformations/mnemonics) and hiding it well to take care of eventual memory troubles shouldn't be a big problem in practice in my humble view. M. K. Shen
From: Anonymous on 24 May 2010 12:37 > The maximum entropy as worst case for brute force search? Sure, you can > calculate that the obvious way, H=log2(k**n) where k is the size of the > alphabet. But that is pretty useless, especially since the searcher > won't normally know the length of the passphrase (it could be very long). Thanks...and n is the number of chars in the password, or bits * chars in the password? In the example I'm considering the password length is (stupidly) fixed at 10 chars. > The usual reason people want to estimate password entropy is for those > stupid password-strength checkers that prevent users from setting > passwords fewer than n characters, etc. In that situation, the max > entropy above is the best case, not the worst, and it is unrealistic > to hope for if the users get to pick the password themselves. Ok thanks.
From: Paul Rubin on 24 May 2010 16:45 Anonymous <cripto(a)ecn.org> writes: >> The maximum entropy as worst case for brute force search? Sure, you can >> calculate that the obvious way, H=log2(k**n) where k is the size of the >> alphabet. But that is pretty useless, especially since the searcher >> won't normally know the length of the passphrase (it could be very long). > > Thanks...and n is the number of chars in the password, or bits * chars in > the password? In the example I'm considering the password length is > (stupidly) fixed at 10 chars. n = number of chars. k = size of alphabet, e.g. for lower case letters, k=26. What are you trying to do exactly? 10 chars would normally not be considered a "passphrase" (which connotes being able to withstand offline brute force search). Normally 10 chars would be for an access password which can only be checked with an online query for each guess, making brute force search much harder.
From: Paul Rubin on 24 May 2010 17:19 Maaartin <grajcar1(a)seznam.cz> writes: > I wonder how closely is the expected time of brute force search > related to the entropy. Imagine me picking a 10 characters random > password consisting of letters only, where I'm biased 80:20 against > capitals. The entropy is only 54 bits instead of 57, does it mean the > search takes 8 times less? Usually you'd just use the min-entropy (log of probability of most likely password) as a conservative estimate. If you want to be more precise, look at the cumulative distribution function (cdf) of the probability of each password, where they passwords are ordered from most likely to least likely. In this example, let L be the number of lower-case letters in a given password. If I did this right, the likeliest passwords are all upper-case (L=0) and there are 26**10 of them; the next most likely have L=1 and there are 10*26**10 of them, and in general N(L) = C(10,L)*26**10. And from the 80:20 bias, Pr[L=0] = 10.7%, Pr[L=1]=26.8%, and Pr[L=2]=30.2%, so the cdf hits 50% about 60% of the way through the L=2 passwords. That means you expect to search 26**10 * (1 + 10 + 45*0.6) = 37.5*26**10 passwords, or 37.5/256 = 14.6% of the whole 52**10 password space. I'll leave recreating and checking this calculation as an exercise for you. ;-)
From: Paul Rubin on 24 May 2010 17:28
Paul Rubin <no.email(a)nospam.invalid> writes: > 37.5/256 = 14.6% of the whole 52**10 password space. Silly me, of course I meant 37.5/1024 = 3.66% of the whole password space. I must have been thinking in bogo-binary to get 2**10=256. That post may have other mistakes too. Exercise: find them. |