Today, Bob, a colleague of mine, accidentally revealed that his password contains a
. Alice laughed, but then also inadvertently said her password does not contain any a
.
Who has given away more about his/her password? In other words, whose password is now easier to guess?
EDIT: I have purposedly not provided information about the length of any password, or even maximum length. One can assume the maximum length to be unbounded. I.e. let the variable m
representing the maximum password length in any formulae, tend towards infiny.
EDIT2: I picked "Alice" and "Bob" as a homage/reference to the homework problems in my undergraduate course's books. But this really happened. A colleague of mine has a defective a
in his keyboard.
EDIT3: Here's my stab at the question that I arrived at with my colleagues over lunch yesterday:
Let's write the formulae for the number of possible passwords given an alphabet of integer size $\alpha$ and a maximum password length of $m$
$\sum_{n=1}^m \alpha^n$
This I arrived at by summing "$\alpha$ passwords of length 1" + "$\alpha^2$ passwords of length 2" + ... + "$\alpha^m$ passwords of length $m$".
Now, Alice has revealed she doesn't have an a
anywhere in her password. She has reduced the alphabet size to the attacker by 1. So the total number of passwords for her is:
$N_{Alice}=\sum_{n=1}^m (\alpha-1)^n$
Bob's total number of possible passwords has also decreased:
$N_{Bob}=\sum_{n=1}^m \alpha^n -\sum_{n=1}^m (\alpha-1)^n$
In other words, $N_B$ has decreased exactly the same amount as the number of possible passwords for Alice, which have the letter a
.
Now, if $m$ is [the totally unrealistic value of] 1, Alice has clearly given away her password completely, while Bob still has $\alpha - 1$ total passwords.
But, as an intuition as $m$ increases towards infinity, I think $N_{Alice} << N_{Bob}$, so I think it is Alice who is now more likely to have his password brute forced!!
My calculus is a bit shaky :-) so I do not know yet if it is true that $N_{Alice} << N_{Bob}$ as $m$ tends towards infinity. If this question is reopened, perhaps someone can help me.
EDIT4: Trial-and-error in a simple program seems to confirm my intuition. For an alphabet size of 26, if the maximum password length is 17, Bob has given away more. If it is 18, he wins (Alice has given away more).