Bounding security of password authentication given entropy An adversary Craig tries to log-in as Alice on a system that will only accept the right password, leaks (only) if an attempt succeeds, and allows many attempts.

Alice's password choice is modeled as a random pick in a finite set of $m$ possible passwords $P_i$ each with probability $p_i$, with $0\le i&lt;j&lt;m\implies p_i\ge p_j&gt;0$ , and $1=\displaystyle\sum_{0\le i&lt;k}p_i$ .

Assume Craig has a perfect model of Alice's password choice and tries up to $n$ passwords $P_i$ by increasing $i$ (with $0\le n\le m$), stopping if he logs-in. That success for Craig has probability $q_n=\displaystyle\sum_{0\le i&lt;n}p_i$ .

We know $n$, $m$, and the password distribution's Shannon entropy $H=\displaystyle-\sum_{0\le i&lt;m}p_i\cdot\log_2(p_i)$ . For a uniform distribution of the $p_i$, we'd have $q_n=n/m=n/2^H$ . But we do not know said distribution.

How can we rigorously, and tightly, bound Craig's success probability $q_n$ ?
Clarification: it is asked upper and lower bounds of $q_n$ as a function of $(n,m,H)$.

What if we additionally have the min entropy $H_\text{min}=-\log_2(p_0)$ or some other interesting metric of the probability distribution?



Now there are $u$ users Alice, Bob.. that (we assume) have chosen their password independently of each others, but per the same distribution. Craig knows user logins, and tries $P_i$ for each user before moving to $P_{i+1}$. He stops when he logs into the account of any user, or has made $n$ tries, with $0\le n\le (m-1)\cdot u+1$ .

What does the bounds become?



Suggested numerical illustration: for $n=1000$ out of $m=2^{48}$, $H=20$-bit entropy, what bound can we get for $q_n$? If we additionally assume $H_\text{min}=12$? Or with $u=2^{10}$?



Does some property that actual distributions of password choice tend to have let us tighten the bounds?
Optimizing attacker's success probability constrained by $H$ and number of passwords

Let's tweak the notation a little bit to make it less cumbersome: the passwords the adversary tries have probability $p_i$ for $0 \leq i &lt; n$, and the passwords the adversary doesn't try have probability $q_j$ for $0 \leq j &lt; m$.  The adversary succeeds with probability $\sum_i p_i$.

We seek an extreme point of $f = \sum_i p_i$ among the zeros of $g$ and $h$ where
\begin{align*}
  g &amp;= H + \sum_i p_i \log p_i + \sum_j q_j \log q_j,
    &amp;&amp;\text{entropy constraint;} \\
  h &amp;= 1 - \sum_i p_i - \sum_j q_j,
    &amp;&amp;\text{total probability constraint.}
\end{align*}
These extreme points are zeros of $$d(f - \lambda g - \mu h) = df - g\,d\lambda - \lambda\,dg - h\,d\mu - \mu\,dh$$ for Lagrange multipliers $\lambda$ and $\mu$.  Since $$d(x\log x) = \log x\,dx + x\cdot(1/x)\,dx = (1 + \log x)\,dx,$$ we have
\begin{align*}
  df &amp;= \sum_i dp_i, \\
  \lambda\,dg &amp;= \lambda\,dH + \sum_i \lambda (1 + \log p_i)\,dp_i + \sum_j \lambda (1 + \log q_j)\,dq_j, \\
  \mu\,dh &amp;= -\sum_i \mu\,dp_i - \sum_j \mu\,dq_j.
\end{align*}
Thus if $dH = 0$ while $dp_i$ and $dq_j$ are nonzero (we hold $H$ fixed but allow the probabilities to vary), we obtain from $0 = d(f - \lambda g - \mu h)$ the system of equations
\begin{align*}
  0 &amp;= 1 - \lambda (1 + \log p_i) + \mu, \\
  0 &amp;= -\lambda (1 + \log q_j) + \mu,
\end{align*}
and from $g\,d\lambda = 0$ and $h\,d\mu = 0$ we get the entropy and total probability constraints as before.  Since $\log$ is injective, this system implies that the $p_i$ are all equal, and the $q_j$ are all equal; call the common values $p/n$ and $q/m$, respectively.  From the total probability constraint, we have $p = 1 - q$.  The entropy constraint reduces to $$H = -p \log (p/n) - (1 - p) \log [(1 - p)/m].$$  The adversary's success probability $p$ must be optimized by minimum/maximum uniform probability mass distributed to the first $n$ passwords consistent with this entropy constraint.  There are two solutions, because $H$ is increasing for $p &lt; n/(n + m)$ and decreasing for $p &gt; n/(n + m)$, corresponding to the attacker's minimum and maximum success probability.

Inverting $H$ is tricky, but we can approximate it in this case without too much trouble.  Let $n = 1000$ and $m = 2^{48} - 1000$ as in the question.  For the minimum value of $p &lt; n/(n + m) = 1000/2^{48}$, we might use the approximation that $\log (1 - p) \approx 0$, so that
\begin{align*}
  H &amp;= -p \log (p/n) - (1 - p) \log [(1 - p)/m] \\
    &amp;\approx -p \log (p/n) + (1 - p) \log m \\
    &amp;= \log m - p \log (p/n) - p \log m \\
    &amp;= \log m - p \log (p m/n).
\end{align*}
To solve this, let $W(x e^x) = x$ be Lambert's W function.  Suppose $y = x \log (a x)$; then $e^y = e^{x \log (a x)} = a x e^x$, so that $e^y/a = x e^x$, from which $x = W(x e^x) = W(e^y/a)$.  Thus, since $\log m - H \approx p \log (p m/n)$, we can recover $p \approx W(e^{\log m - H}/(m/n)) = W(e^{-H} n)$.  For $H = 20 \log 2$ so that $e^{-H} = 2^{-20}$, we get $$p \approx W(2^{-20} \cdot 1000) \approx 0.000952766 &gt; 2^{-11}.$$  For the maximum value of $p &gt; n/(n + m)$, we can use bisection on the decreasing function $H$ (on a range much more amenable to naive numerical computation) to find $$p \approx 0.757204 &lt; 4/5.$$  Thus, $$2^{-11} &lt; p &lt; 4/5.$$

Multi-user setting

Suppose Alice, Bob, etc., all use the same distribution on passwords.  If there are $u$ users, the adversary's probability of success at breaking at least one of the $u$ users with the $i^{\mathit{th}}$ password is given by $\hat p_i = 1 - (1 - p_i)^u$.  This is the complement of the probability that every user picked a password other than $P_i$.  The adversary's probability of success after trying the first $n$ passwords is $\hat p = 1 - (1 - \sum_i p_i)^u$.  To optimize this, we simply replace the objective $f$ in the above procedure by $f' = 1 - (1 - \sum_i p_i)^u$.  We obtain the modified system of equations
\begin{align*}
  0 &amp;= u \bigl(1 - \sum\nolimits_\iota p_\iota\bigr)^{u-1} - \lambda (1 + \log p_i) + \mu, \\
  0 &amp;= -\lambda (1 + \log q_j) + \mu,
\end{align*}
which as far as I can tell doesn't change the extreme points, only the value of the adversary's success probability at those points.  Suppose $u = 2^{10}$; then since $2^{-11} &lt; p &lt; 4/5$,
\begin{gather*}
  1 - (1 - 1/2^{11})^{2^{11}} \approx 1 - e^{-1} \approx 0.63212 \\
  1 - (1 - 4/5)^u = 1 - (1/5)^{2^{10}} \approx 1,
\end{gather*}
so we have $$1/2 &lt; \hat p &lt; 1.$$
That is, the adversary's probability of success in a multi-target attack guessing a thousand passwords out of $2^{48}$ possibilities with 20 bits of entropy for any of a thousand users is guaranteed to be better than a fair coin toss coming up heads, and may be essentially 1.  Note that this multi-target attack still costs $n\cdot u$ queries, just like the single-target attack costs $n$ queries (unless the password database is amazingly badly designed).  In this case, it costs $2^{20} \approx 10^6$ queries.

Addendum: If number of passwords is unbounded then entropy is unbounded for any success probability no matter how close to 1

Fix $0 &lt; \varepsilon &lt; 1$.  Let $p_0 = 1 - \varepsilon$ and $p_i = \varepsilon/m$ for $i = 1, 2, \ldots, m$.  The Shannon entropy of this distribution is
\begin{align*}
  H &amp;= -(1 - \varepsilon)\log(1 - \varepsilon) - \sum_{i=1}^m (\varepsilon/m) \log(\varepsilon/m) \\
    &amp;= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log (\varepsilon/m) \\
    &amp;= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log \varepsilon + \varepsilon \log m.
\end{align*}
If $\log m$ is unbounded above, so is $H$.

The adversary's chance of success at a single guess, trying the first password with probability $p_0$, is $1 - \varepsilon$, which can be made arbitrarily close to 1, while the Shannon entropy of the whole distribution is made arbitrarily high, by adding more equiprobable passwords other than the first one.

What this counterexample demonstrates is that for any Shannon entropy, the probability of success after the first trial can be made arbitrarily close to 1.  On the other hand, the min-entropy of this distribution is $-\log (1 - \varepsilon)$, no matter how many other choices there are.

In general, if the min-entropy of the distribution on passwords is $H_\infty$, then the best chance of success at a single guess is $e^{-H_\infty}$.  If the min-entropy of the distribution on passwords given that it is not the first one is $H'_\infty$, the best chance of success at a single guess after the first one is $e^{-H'_\infty}$, so the best probability of success after two trials is $$\Pr[T_0] + \Pr[T_1 \mathrel| \neg T_0] \Pr[\neg T_0] = e^{-H_\infty} + e^{-H'_\infty} (1 - e^{H_\infty})$$ and so on, where $T_0$ means success after the first trial, $T_1$ means success after the second, etc.  In the uniform case, this reduces to a hypergeometric distribution as one might expect.