How to determine passphrase entropy?
in [Cryptography]
|
From: unruh on 24 May 2010 20:00 On 2010-05-24, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > unruh wrote: > >> The question is not "what is the entropy of the passwords as an abstract >> exercise" buti" what is the password entropy given the attacker's paln of >> attack." Ie, it is more about the attaker. Thus if a user uses >> AvjU7^%hJrtM >> as their password, and the attacker has a strategy which chooses that as >> as the first password to try, it has extremely low entropy given the >> attacker's strategy. >> >> Or course it is pretty unlikely that the attacker's strategy will pick >> it as the first try. (unless the user for example published it on their >> web page.) >> The key is that there is not "entropy of a password". One can only make >> reasonable assumptions about the attacker's strategy and hope it is not >> too far out. Given those assumptions one can estimate the entropy. >>> Also, checking passwords against each other isn't so good since it means >>> you're storing them as unsalted hashes or even in the clear. > > If there is not "entropy of a password", could there be "entropy of a > message in general"? I am afraid that the existence non-existence > of both are somehow tightly related. It has been widely debated. There is a definition-- the log of the shortest program required to produce that sentence as output. Now that obviously depends on the compter and the language used. (for example your particualr sentence could be a single byte command in some language) but for a randomly chosen sentence ( which of course your password or your sentence is not, since it is the particular pharse chosen by you) the average entropy over all choices is essentially the same for all languages. Note that that "shortest" always exists-- Print "The particular sentence" is a program which will output that sentence, but finding the shortest program is a computationally hard problem ( it relates to the halting problem, since to test if a program does print out your sentence you have to know it has halted, and there is no algorithm which can determine whether any program will halt or not.) Thus, while the entropy defined in this way (Kolmogorov, Chaitin) is well defined it is not computable, and for any particular sentence is also undefined as you also have to define the language being used ( This is related to the difficulty I discussed of having to know the attacker's algorithm for going through all passwords). I supposed you could alter it to say that the entropy is the time ( not the length) of the shortest program, but then you would have to worry that perhaps there is a long program which could print out the sentence in a shorter time than Print <sentence> > > M. K. Shen > >
From: unruh on 24 May 2010 21:33 On 2010-05-24, Paul Rubin <no.email(a)nospam.invalid> wrote: > unruh <unruh(a)wormhole.physics.ubc.ca> writes: >> The key is that there is not "entropy of a password". One can only make >> reasonable assumptions about the attacker's strategy > > I see "entropy of a password" as shorthand for "entropy of the > distribution that the password is drawn from". The attacker's obvious > strategy is to model the distribution as closely as possible, then > search starting from the most probable passwords. Except of course that the attacker does not know what distribution the password was drawn from, nor does the person know what the attacker's search stragegy is. The user's best strategy is to choose the least likely password from the attacker's distribution, while the attacker;s to to choose the most likely from the user's distribution. But neither actually do that.
From: Mok-Kong Shen on 25 May 2010 01:58 unruh wrote: > Mok-Kong Shen wrote: >> unruh wrote: >> >>> The question is not "what is the entropy of the passwords as an abstract >>> exercise" buti" what is the password entropy given the attacker's paln of >>> attack." Ie, it is more about the attaker. Thus if a user uses >>> AvjU7^%hJrtM >>> as their password, and the attacker has a strategy which chooses that as >>> as the first password to try, it has extremely low entropy given the >>> attacker's strategy. >>> >>> Or course it is pretty unlikely that the attacker's strategy will pick >>> it as the first try. (unless the user for example published it on their >>> web page.) >>> The key is that there is not "entropy of a password". One can only make >>> reasonable assumptions about the attacker's strategy and hope it is not >>> too far out. Given those assumptions one can estimate the entropy. >>>> Also, checking passwords against each other isn't so good since it means >>>> you're storing them as unsalted hashes or even in the clear. >> >> If there is not "entropy of a password", could there be "entropy of a >> message in general"? I am afraid that the existence non-existence >> of both are somehow tightly related. > > It has been widely debated. There is a definition-- the log of the > shortest program required to produce that sentence as output. Now that > obviously depends on the compter and the language used. (for example > your particualr sentence could be a single byte command in some > language) but for a randomly chosen sentence ( which of course your > password or your sentence is not, since it is the particular pharse > chosen by you) the average entropy over all choices is essentially the > same for all languages. Note that that "shortest" always exists-- > Print "The particular sentence" > is a program which will output that sentence, but finding the shortest > program is a computationally hard problem ( it relates to the halting > problem, since to test if a program does print out your sentence you > have to know it has halted, and there is no algorithm which can > determine whether any program will halt or not.) > Thus, while the entropy defined in this way (Kolmogorov, Chaitin) is > well defined it is not computable, and for any particular sentence is > also undefined as you also have to define the language being used ( > This is related to the difficulty I discussed of having to know the > attacker's algorithm for going through all passwords). > I supposed you could alter it to say that the entropy is the time ( not > the length) of the shortest program, but then you would have to worry > that perhaps there is a long program which could print out the sentence > in a shorter time than Print<sentence> But I don't understand your sentence 'The key is that there is not "entorpy of a password"', which in my interpretation denies the existence of entropy of a password. If my interpretation is right, it would contradict what your wrote above, wouldn't it? BTW, I remember to have seen (maybe in another group) the claim that the measure of entropy only applies to a source of randomness and hence any bit sequence of finite length couldn't be ascribed a value of entropy. Is that o.k.? Any short argument to refute it? Thanks. M. K. Shen
From: Mok-Kong Shen on 25 May 2010 02:03 Mok-Kong Shen wrote: > unruh wrote: [snip] > But I don't understand your sentence 'The key is that there is not > "entorpy of a password"', which in my interpretation denies the > existence of entropy of a password. If my interpretation is right, > it would contradict what your wrote above, wouldn't it? > > BTW, I remember to have seen (maybe in another group) the claim that > the measure of entropy only applies to a source of randomness and > hence any bit sequence of finite length couldn't be ascribed a value > of entropy. Is that o.k.? Any short argument to refute it? The first question is answered in a follow-up of yours (which I read after posting). I would appreciate an answer to the 2nd question. M. K. Shen
From: starwars on 25 May 2010 08:24
I also realized most people are going to pick passwords that are very easily attacked with dictionary attacks etc. |