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.