How to choose a password optimally

[kpreid]

1. Premise: Any attack on a password — whether online (login attempts) or offline (hash cracking) — will be designed so that the more likely a given password is, out of the space of all possible passwords, the less work is required to recover that password (unless a trivial amount of work is required to discover any possible password).

2. From (1), there exists a probability distribution of passwords.

3. Premise: There is a (practical) maximum length for passwords.

4. From (3), the set of possible passwords is finite.

5. From (2) and (4), there is a minimum probability in that distribution.

6. Use one of the passwords which has that minimum probability.

(There are at least two ways this doesn't work.)

Comments

[(Anonymous)]

Here's one reason why I think this won't work: (2) is flawed. The probability distribution depends on the chosen attack and differs for different attacks. We would need a probability distribution on the attacks to choose the "best" password.

[kpreid.livejournal.com]

Yep.

Here's a brute-force way to take that into account, assuming you have a finite list of attacks and all attacks are run simultaneously: Take each attack's list of passwords, each annotated with the effort required to reach it. For each password, take the minimum of the efforts. Choose the password with the greatest minimum effort.

(The 'list of passwords ranked by effort' representation is how I originally thought of the scheme in the post.)

I haven't thought of how to generalize that combination method to handle non-equiprobable attacks.

[(Anonymous)]

Does this relate to the unexpected hanging paradox?

[(Anonymous)]

Well, if you can calculate the minimum probability then so can an attacker.
So the ability to calculate a minimum makes that minimum unsuitable for use?

Seems to me we can use this heuristic:
1. Take all practical passwords.
2. Remove the X% most common passwords for some X.
3. Select a password from the remaining with uniform probability.

Removing the X% here should make you safer in the case of an undirected attack,
since any blind attacker will have to look at the most common passwords first. This
is because they don’t know how smart you are at selecting passwords.

In a directed attack, knowing that you have excluded the X% most common passwords
saves the the trouble of trying those, but the remaining passwords should be so many
as to make brute-forcing a futile endeavour.

I think this problem should be thought about in the context that an attacker knows our
method of choosing passwords and therefore can use it against us. And the above is the
best my limited intuition can tell me. How wrong am I?