Probability of finding the right password in a set of passwords. This might seem like a homework question because it is. But I and my friend have been trying to solve it for the past three days. S1 is the set of 4 digit numeric passwords, so it contains 10000 passwords.
For the first question, 20 passwords are common and there's a 26.83% chance that the correct password is among them.
Assume an attacker is using a dictionary attack against the pin codes (scheme S1), starting with the top 20 passwords from that post(The top 20 have a solving probability of 26.83%). Assume that they can try 1 password / second. Given the % of users who would choose one of those as their 4 digit pin, what is the % chance that a password will be cracked within 1 minute? 1 hour? 1 day? Assume that there is a uniform distribution of frequencies for passwords between the 21st and the 9,979th.
For the first question, we proposed the answer should be
$$
\begin{align}
\operatorname{Pr}(\text{solved}) &= \operatorname{Pr}(\text{password is weak}) \cdot \operatorname{Pr}(\text{solving a weak password})\\ &+ \operatorname{Pr}(\text{password is strong}) \cdot \operatorname{Pr}(\text{solving a strong password}) \\
&= \frac{20}{n} \cdot 0.2683 + \frac{n - 20}{n} \cdot \frac{\operatorname{speed} \cdot \left(\operatorname{time} - 20\right)}{n - 20} \\
&= \frac{20 \cdot 0.2683}{n} + \frac{\operatorname{time}- 20}{n} \\
&= \frac{\operatorname{time} - 14.634}{n}
\end{align}
$$
Where n is the number of passwords in S1. We assume the hacker inputs the 20 passwords with the higher chances of being the correct password first and spends the first 20 seconds on those since the speed is 1 password per second.
 A: First of all, you didn't apply conditional probability properly.
Let $time = t$. And let $S_t = $solved in $t$ seconds. Let $X$ indicate the strength of the password and $X=C$ means common password and $X = U$ mean uncommon password.
$P(S_t) = P(S_t|C) P(C) + P(S_t|U)P(U)$.
$P(C) = 0.2683$. If $t \geq 20$, $P(S_t|C) = 1$. If $t<20$ we would have to do some finer analysis but for now let's just assume otherwise (and as you will see, we will do some very similar fine analysis for $P(S_t|U)$ so you should be able to figure it out yourself.
$P(U) = 1-P(C)$ of course.
Now the only real issue is what is $P(S_t|U)$?
Let us order the uncommon passwords, dictionary wise as $\{p_{21}, p_{22}, ..., p_{10000}\}$. Given that the password is not common, it is equally likely, i.e uniformly distributed, amongst these $9980$ passwords.
Let $p$ be our password. Then $p= p_n$ is $1/9980$ for every $n \geq21$ (given that it is uncommon already)
Now it should be easy to see once again that $P(S_t|p =p_n) = 1$ if $t \geq n$  and $0$ otherwise.
So for instance, if $ t= 22$, then the password will only be solved if $p = p_{21}$ or $p_{22}$. This happens with probability $2 \times 1/9980$.
Similarly for a general $t$, within time $t$, the first $t-20$ passwords in $\{p_{21}, p_{22}, \cdots, p_{10000}\}$ will be guessed- $\{p_{21}, ..., p_{t}\}$. The probability that $p$ will lie in this is $\frac{t-20}{9980}$.
Putting it altogether, we get that:
$P(S_t) = P(S_t|C)P(C)  + P(S_t|U)P(U) = 0.2683 + (1-0.2683)\times \frac{t-20}{9980}$
(Sanity check: if $t = 10000$ then $P(S_t) = 1$ which makes sense since in $10000$ seconds we would end up checking every single password and thus eventually hit the right one. If $t = 20$ then $P(S_t) = P(C)$ which makes sense since we can only check the common passwords in the first $20$ seconds and thus we will have only solved it if the password is common).
Again this is assuming that $t \geq 0 20$ for simplicity. If $t<20$ then the right summand should automatically go to $0$ (put an indicator function there if you want), and then you would need to incorporate information about the distribution of passwords in the first $20$ passwords; if these first $20$ passwords are uniformly distributed (which isn't given to us to be clear) then it would follow a very similar analysis to $P(S_t|U)$.
