How to determine passphrase entropy?
in [Cryptography]
|
From: jbriggs444 on 25 May 2010 08:57 On May 24, 9:33 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: > On 2010-05-24, Paul Rubin <no.em...(a)nospam.invalid> wrote: > > > unruh <un...(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. At the risk of stating the blatantly obvious... The user can put a bound on the effectiveness of the attacker's best strategy by arranging for the likelihood of his most likely password choice to be very small. Given a fixed finite limitation on password length, an optimum is achieved by using the maximum alphabet size and choosing at random so that all password choices are equally unlikely. This is "optimal" in the sense that it guarantees a particular level of effectiveness against the best possible counter-strategy. No other user strategy can provide a a guarantee of doing better. Given an unlimited password size, the user has no optimal strategy, but can make the attackers expected effort arbitrarily large.
From: Mok-Kong Shen on 25 May 2010 10:32 jbriggs444 wrote: > The user can put a bound on the effectiveness of the attacker's > best strategy by arranging for the likelihood of his most likely > password choice to be very small. Given a fixed finite limitation > on password length, an optimum is achieved by using the > maximum alphabet size and choosing at random so that all > password choices are equally unlikely. > > This is "optimal" in the sense that it guarantees a > particular level of effectiveness against the best possible > counter-strategy. No other user strategy can provide a > a guarantee of doing better. > > Given an unlimited password size, the user has no optimal > strategy, but can make the attackers expected effort arbitrarily > large. I have a layman's problem: Suppose that there is a mechanism that emits the characters of the alphabet perfectly randomly. Then by assumption it "could" happen that one obtains e.g. a result 'aaaaa.....'. But one "normally" wouldn't consider that to be a good password, would it? M. K. Shen
From: Maaartin on 25 May 2010 11:18 On May 25, 4:32 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I have a layman's problem: Suppose that there is a mechanism that > emits the characters of the alphabet perfectly randomly. Then > by assumption it "could" happen that one obtains e.g. a result > 'aaaaa.....'. But one "normally" wouldn't consider that to be > a good password, would it? It may happen, but normally it's quite improbable. The probability of a any given string (e.g., "aaaaaaaaaa") being taken from the uniform distribution (of 10 lower case letters) is exactly the same as the probability of the attacker using the same distribution succeeding with his first guess when guessing the password (e.g., "yugpsgxpzz"). When we don't care about the latter, we can ignore the former as well. Or can we?
From: jbriggs444 on 25 May 2010 12:25 On May 25, 11:18 am, Maaartin <grajc...(a)seznam.cz> wrote: > On May 25, 4:32 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > > > I have a layman's problem: Suppose that there is a mechanism that > > emits the characters of the alphabet perfectly randomly. Then > > by assumption it "could" happen that one obtains e.g. a result > > 'aaaaa.....'. But one "normally" wouldn't consider that to be > > a good password, would it? > > It may happen, but normally it's quite improbable. The probability of > a any given string (e.g., "aaaaaaaaaa") being taken from the uniform > distribution (of 10 lower case letters) is exactly the same as the > probability of the attacker using the same distribution succeeding > with his first guess when guessing the password (e.g., "yugpsgxpzz"). > When we don't care about the latter, we can ignore the former as well. > Or can we? Do you want to base your defense on Iocaine powder? Suppose your strategy is to filter out all 26 passwords where the same character is repeated 10 times. Suppose the password generator otherwise has a 26 character alphabet and is generating 10 character passwords. By filtering the password generator's output, you reduce its entropy [very slightly] and improve the odds that an attacker who understands your password generation algorithm will be able to mount a brute force attack. You ease this attacker's work factor by a factor from an average of (2^26+1)/2 down to an average of (2^26-25)/2 Against an attacker who is starting at aaaaaaaaaa and working up in alphabetic order, the filter achieves no net change in the attacker's work factor!!! [you eliminated "zzzzzzzzzz" from the end of the list at the same time you eliminated "aaaaaaaaaa" from the front -- average linear search time is unchanged]
From: Gordon Burditt on 25 May 2010 12:58
>I have a layman's problem: Suppose that there is a mechanism that >emits the characters of the alphabet perfectly randomly. Then Rolling dice is a pretty good approximation of this. Not perfect, but a reasonable approximation. You can buy a 30-sided die with the alphabet and 4 "wild" sides on it. Reroll if you get "wild" or use a symbol. You can also flip a coin to decide whether it will be upper or lower case. You could also roll 2 10-sided dice to get a 2-digit decimal number, and assign up to 100 characters to those numbers. Re-roll if you get an unassigned number. That should handle printable ASCII characters and a few control characters like newline and tab. >by assumption it "could" happen that one obtains e.g. a result >'aaaaa.....'. But one "normally" wouldn't consider that to be >a good password, would it? No. But the chances of that happening are very small, and eliminating all the passwords possibly considered "bad", such as all those with repeated letters, just makes the search space smaller. "goodness" of a password is more a function of how it was generated, or how it is guessed, rather than the actual password. |