How to prove a password guessing theory from Matt Bishop's book “Introduction to Computer Security”

Question

First, this is not a homework problem. This is a problem from Matt Bishop's book "Introduction to Computer Security" which was used as one of the textbooks for a Computer Security class I took last year. This question never came up during the course. In hindsight I should have asked the course's professor to explain the proof, but again this textbook wasn't the main text for the course.

The theorem states:

Let the expected time required to guess a password be T. Then T is a maximum when the selection of any of a set of passwords is equiprobable.

The question is how do you prove this theorem?

I understand that if there are n possible passwords, that on average you can guess the password in n/2 attempts using brute force. Also, if each password is equiprobable then the probability of each password is 1/n.

Here's where I get stuck, if the probability of each password is not equal then obviously there is a smaller set of passwords to check and therefore a shorter amount of time required to perform a brute force attack.

However, if I don't know what the probability of each password is then I need to perform a brute force attack on all possible passwords and we're back at n/2 attempts.

Or is that the proof. If the probability of each password is not equal and you test the passwords with the higher probabilities, you are dealing with a smaller subset and therefore a shorter period of time than testing all of the possible passwords.

Is there a more formal way to state this?

Also, what happens if the password is a part of the subset of passwords with lower probabilities, by searching only the higher probability passwords you will fail to find the desired password. Or take longer than if you just tried all.

Thank you for your consideration to this question.

Answer 1

With mathematics:

Suppose there are n possible passwords. Password number i has probability p_i of being selected. It is assumed that the attacker knows the exact values of the p_i and tries them in due order. Without loss of generality, I assume that p₁ is the most probable password, and so on (i.e. p_i >= p_j whenever i < j).

Let q_j the sum of all p_i for i ranging from 1 to j. q_j is the probability that the password is part of the j most probable passwords (necessarily, q_n = 1: the password is part of the space of possible passwords). The following holds true:

For all j, q_j >= j/n

Because if q_j < j/n (for some value j), then there must be one value i lower than j such that p_i < 1/n. The condition on the p_i (non-increasing values) then implies that all p_k for k > i are lower than 1/n, and this implies that q_n < 1, which is not possible.

q_j is the probability that the attacker succeeds by doing at most j guesses. Higher values imply faster success, i.e. if there are two distribution probabilities P and P' such that q'_j >= q_j for all j, then the attack for P' succeeds at least as fast as the attack for P. Note that two given distribution probabilities cannot necessarily be compared like this (there could be some, but not all values j such that q'_j >= q_j), but, if they can be compared, then the conclusion follows.

The uniform distribution (p_i = 1/n for all i) implies q_j = j/n for all j, which, as explained above, compares favourably (for the defender) to all other distributions. Therefore, this is the distribution which makes the attack slowest.

---

With physics:

Attack success speed is higher when password entropy is lower. Uniform distribution maximizes entropy.

Answer 2

Let's make some definitions:

1. Equiprobable means that for a set of passwords W, every element in W has an equal probability of occurance, i.e. P(W_a) = P(W_b) for any a and b.
2. There is an assumption that the set W does indeed contain the password we're searching for. As such, we can assume that Σ P(W_n) = 1.
3. The probability that an n-length subset of W contains the password we're looking for is n*P(W_x) for any x, or essentially n divided by the number of passwords in W.
4. If all passwords are not equiprobable, but definition #2 still holds, our best estimate (without knowing the probabilities of specific subsets) is that a random selection of W will still adhere to definition #3.

Expected time is defined as the amount of work necessary to find the target password with a probability of 50%. As such, naively cracking a password against set W will always result in an expected time of n/2, where n is the number of entries in W.

However, if you know the probability of each password, you can arrange them into equiprobable buckets. As such, all passwords in W are split into n subsets W⁰, W¹, W², ... Wⁿ, each of which contains a number of equiprobable passwords. The caveat of this is that the password is no longer guaranteed to be in any single subset - we just have a probabilitiy that the password is in a particular subset. However, definition #2 still holds when you consider all subsets as a whole, i.e. Σ P(Wⁿ) = 1.

Let's assume we have five subsets:

Subset | Prob. (Password) | Count | Prob. (Subset)
-------+------------------+-------+---------------
W0     | 0.005            | 20    | 0.1
W1     | 0.002            | 60    | 0.12
W2     | 0.0004           | 540   | 0.216
W3     | 0.00007          | 6000  | 0.42
W4     | ~0.0000426       | 3380  | 0.144

In this case we need to compute the number of passwords we check before the total probability of hitting the password reaches 0.5. So, for the first subset (W⁰) we reach 0.1, for the second (W¹) we reach 0.22, for the third (W²) we reach 0.436. When we look at the fourth bucket (W³) we notice that we're exceeding 0.5. So, we compute the number of passwords in bucket W³ that will take us from a probability of 0.436 to 0.5. This is simple: subtract, then divide: 0.5 - 0.436 = 0.064, 0.064 / 0.00007 = 914. So, our expected work is 20 + 60 + 540 + 914 = 1534 hashes.