4
$\begingroup$

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).

$\endgroup$
6
  • 5
    $\begingroup$ Assuming that Alice and Bob are not real friends of yours, this smells like homework in Introduction to Cryptography course or something similar. Given that this is indeed homework, what have you tried? $\endgroup$
    – barak manos
    Jan 15, 2016 at 14:03
  • $\begingroup$ It depends on the alphabet and on the average length of the passwords. For example, in an alphabet with only two characters $a,b$, the password of Alice must have the form $b\dots b$, so it is easy to guess. $\endgroup$
    – Crostul
    Jan 15, 2016 at 14:06
  • $\begingroup$ Given a password of length $n$, which may contain any one of $m$ unique symbols any number of times: The probability of guessing Bob's password is $1-\left(\frac{m-1}{m}\right)^n$. The probability of guessing Alices's password is $\left(\frac{m-1}{m}\right)^n$. So this answer basically depends on the values of $m$ and $n$. $\endgroup$
    – barak manos
    Jan 15, 2016 at 14:09
  • $\begingroup$ @barakmanos: it sure sounds like homework, but amazingly isnt' This happened a few hours ago at a meeting. But Bob and Alice are an homage to homework, yes. $\endgroup$
    – joao
    Jan 15, 2016 at 14:18
  • $\begingroup$ Jus a quick note, I don't believe you can assume a "maximum password length of infinity", because a "maximum" is something obtained, and if something is unbounded, then the maximum just does not exist. I think you want to say the password has unbounded length. $\endgroup$
    – Sean English
    Jan 16, 2016 at 14:52

2 Answers 2

Reset to default
3
$\begingroup$

Let's assume both have a password length of $N$, and an alphabet size of $s$.

Then the first has a possible $s^N - (s-1)^N$ many passwords: all passwords except those that are all from the alphabet without an a.

The other has $(s-1)^N$ many passwords.

Now compare...

$\endgroup$
6
  • $\begingroup$ I didn't make that assumption in my question. Can you try again without it? $\endgroup$
    – joao
    Jan 15, 2016 at 14:19
  • 2
    $\begingroup$ It will always depend on the alphabet size and length. Make realistic assumptions (like $N=8$ and $s=62$) and compare the numbers. It will be pretty clear I think. $\endgroup$
    – Henno Brandsma
    Jan 15, 2016 at 14:21
  • $\begingroup$ are you saying that without those "realistic assumptions" there are no statement that can be made regarding, for example, the change in the mean time to brute-forcing each of those passwords before and after the information was provided inadvertently by Alice and Bob? I disagree. $\endgroup$
    – joao
    Jan 16, 2016 at 14:49
  • $\begingroup$ Incidently, the only truly "realistic assumption" is that you don't know the length of anyone's password, any more than you know the passphrase. You just know it is finite. $\endgroup$
    – joao
    Jan 16, 2016 at 15:00
  • $\begingroup$ Intuitively, this will mean that if the passwords are long enough that they "ought to have an $a$" (more characters than there are in the alphabet), Alice has removed more possibilities. If they are shorter than the number of characters in the alphabet, Bob has removed more possibilities, because the password "should not have an $a$". $\endgroup$
    – Ross Millikan
    Jan 16, 2016 at 15:04
1
$\begingroup$

Well it depend on two things:

  1. First the length of the password
  2. The size of the alphabet used for the password

Assume that the passwords have length 1 Bob did give away his password but Alice didn't.

However if you have only 2 possible letters (say a and b) then it is Alice that gave away her password (a sequence of b's).

$\endgroup$
1
  • $\begingroup$ except for the length of the password ;) $\endgroup$
    – Pieter21
    Jan 15, 2016 at 14:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .