Bounding security of password authentication given entropy

Question

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<j<m\implies p_i\ge p_j>0$ , and $1=\displaystyle\sum_{0\le i<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<n}p_i$ .

We know $n$, $m$, and the password distribution's Shannon entropy $H=\displaystyle-\sum_{0\le i<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?

Answer 1

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 < n$, and the passwords the adversary doesn't try have probability $q_j$ for $0 \leq j < 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 &= H + \sum_i p_i \log p_i + \sum_j q_j \log q_j, &&\text{entropy constraint;} \\ h &= 1 - \sum_i p_i - \sum_j q_j, &&\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 &= \sum_i dp_i, \\ \lambda\,dg &= \lambda\,dH + \sum_i \lambda (1 + \log p_i)\,dp_i + \sum_j \lambda (1 + \log q_j)\,dq_j, \\ \mu\,dh &= -\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 &= 1 - \lambda (1 + \log p_i) + \mu, \\ 0 &= -\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 < n/(n + m)$ and decreasing for $p > 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 < n/(n + m) = 1000/2^{48}$, we might use the approximation that $\log (1 - p) \approx 0$, so that \begin{align*} H &= -p \log (p/n) - (1 - p) \log [(1 - p)/m] \\ &\approx -p \log (p/n) + (1 - p) \log m \\ &= \log m - p \log (p/n) - p \log m \\ &= \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 > 2^{-11}.$$ For the maximum value of $p > 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 < 4/5.$$ Thus, $$2^{-11} < p < 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 &= u \bigl(1 - \sum\nolimits_\iota p_\iota\bigr)^{u-1} - \lambda (1 + \log p_i) + \mu, \\ 0 &= -\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} < p < 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 < \hat p < 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 < \varepsilon < 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 &= -(1 - \varepsilon)\log(1 - \varepsilon) - \sum_{i=1}^m (\varepsilon/m) \log(\varepsilon/m) \\ &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log (\varepsilon/m) \\ &= -(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.

Answer 2

The Shannon entropy is not a good measure for this problem. In fact, the relationship between difficulty of guessing/predicting an unknown random variable $X$ and entropy (or entropies) is quite a delicate one, and depends on the assumptions about the attack scenario.

It was shown by John Pliam (see preprint) that if $X$ is a discrete random variable with $M$ points in its support $H(X)$ can be close to its maximum value $\log M$ while the probability of an optimal guessor discovering the actual value of $X$ in $k$ sequential questions is much less than $2^{H(X)}=M.$

For more details, see the Appendix below. Another rule of thumb is that since we assume a known monotone decreasing distribution, the median of the distribution is below its' mean, so things are worse than they look. In fact Pliam derived distributions where Shannon entropy is large but the secret is very unsafe against guessing.

One disclaimer, if the distribution is very close to uniform, all these don't matter, the min-entropy, as well as the Renyi entropies are then very close to the Shannon entropy. But, it is weak distributions that we are usually concerned about.

Specific Case of Multiple Targets

The above question asked for the case of multiple targets having the same distribution. If one wants a practical attack, for realistic keyspace sizes, then the assumption of an attacker keeping track of their past guesses is not realistic, unless they have immense amounts of memory.

The question is, should the attacker be guessing according to the password distribution. The somewhat surprising answer is, No.

Let's consider a single attacker who is memory constrained and won't keep track of past guesses, but knows the distribution $\mathbb{P}$ which the opponent uses to draw a single value $x$ from $\cal X$ according to $\mathbb{P}(x).$

The guessor generates i.i.d. $X_1,X_2,\ldots,$ from $\cal X$ according to a distribution $\mathbb{Q}(x)$ again with the goal of minimizing $\mathbb{E}[G],$ the expected number of guesses. Define $G=\min\{k:X_k=X\}$ as a random variable which denotes the number of guesses before she is successful in exposing $X.$ Note that $G=k$ with probability $\sum_{x=1}^N \mathbb{P}(x)(1-\mathbb{Q}(x))^{k-1} \mathbb{Q}(x)$, where $k \geq 1,$ by a success-fail argument. This is because \begin{eqnarray*} \mathbb{P}(G= k) & = & \sum_{x \in {\cal X}} \mathbb{P}(X=x) \, \mathbb{P}(G=k\mathrel|X=x)\\ & = & \sum_{x \in {\cal X}} \mathbb{P}(x) \Pr\left(\bigcap_{m=1}^{k-1} \{X_m \neq x\}~and~ X_{k}=x \right)\\ & = & \sum_{x \in {\cal X}} \mathbb{P}(x) (1-\mathbb{Q}(x))^{k-1} \mathbb{Q}(x). \end{eqnarray*} Since the guessing scheme is randomized, it is possible to have an unbounded number of guesses, hence \begin{eqnarray*} \mathbb{E}[G] & = & \sum_{k=1}^{\infty} k \sum_{x \in {\cal X}} \mathbb{P}(x) (1-\mathbb{Q}(x))^{k-1} \mathbb{Q}(x) \\ & = & \sum_{x \in {\cal X}} \mathbb{P}(x) \mathbb{Q}(x) \sum_{k=1}^{\infty} k (1-\mathbb{Q}(x))^{k-1} \\ & = & \sum_{x \in {\cal X}} \frac{\mathbb{P}(x) \mathbb{Q}(x)}{\mathbb{Q}(x)^2} = \sum_{x \in {\cal X}} \frac{\mathbb{P}(x)}{\mathbb{Q}(x)} \end{eqnarray*} where we used the generating function identity \begin{equation*} \sum_{k=0}^{\infty} k u^{k-1} = \sum_{k=1}^{\infty} k u^{k-1} = \frac{1}{(1-u)^2}. \label{genfun} \end{equation*} If we apply Lagrange multipliers with the Lagrangian $$ J=\mathbb{E}[G]+\lambda\left(\sum_{x \in {\cal X}}\mathbb{Q}(x) - 1\right)=\sum_{x \in {\cal X}} \frac{\mathbb{P}(x)}{\mathbb{Q}(x)}+\lambda\left(\sum_{x \in {\cal X} }\mathbb{Q}(x) - 1\right), $$ we can actually show that $\mathbb{E}[G]$ is minimized when we choose $\mathbb{Q}(x) \propto \sqrt{\mathbb{P}(x)}$, quite an interesting result. Thus $\mathbb{Q}$ is given by $$ \mathbb{Q}(x)=\frac{\sqrt{\mathbb{P}(x)}}{\sum_{z\in {\cal X}} \sqrt{\mathbb{P}(z)} } $$

Appendix to single user problem:

Moreover, not only the expected number of guesses, but arbitary moments of the number of guesses can be related to Renyi entropies of various order. Renyi entropies are a family of entropies $H_{\alpha}(X)$ with parameter $\alpha \in [0,1)\cup(1,\infty)$ which satisfy $$\lim_{\alpha \rightarrow 1}H_{\alpha}(X)=H(X),$$where $H(X)$ is the Shannon entropy of $X.$

One result on the expectation is that the expected number of guesses to determine a random variable $X$ (for the optimal guessing sequence) is upperbounded by

$$2^{H_{1/2}(X)-1}$$

where $H_{1/2}(X)$ denotes the Renyi entropy of order $\alpha=1/2$ and is also called guessing entropy. Moreover, it is lowerbounded by (for all guessing sequences)

$$\frac{2^{H_{1/2}(X)}}{1 + \log M } \approx 2^{H_{1/2}(X)} / H_{max}(X)$$

where $H_{max}(X)$ is the maximum entropy $\log M$ in either the Renyi or the Shannon case. Papers by J L Massey, Arikan, Boztas and others have followed this train of thought.

Answer 3

This is tentative, and so far only finds bounds for $q_n$ in the basic case of given $(n,m,H)$.

We have $q_0=0$ and $q_m=1$. From now on, assume $0<n<m$, with thus $n/m\le q_n<1$.

---

The distribution of $p_i$ that maximizes $q_n$ for given $(n,m,H)$ will (I argue without proof) be the same as one obtained by fixing $q_n$ to the maximum attained and maximizing $H$. For $(n,m,q_n)$ fixed, we can optimize the distribution of $p_i$ separately on both sides of $n$ in the question's expression of $H$. Both are maximized for flat distribution, thus with $$p_i=\begin{cases} q_n/n&\text{ if }0\le i<n\\ (1-q_n)/(m-n)&\text{ if }n\le i<m \end{cases}$$ thus $$H=q_n\,\log_2\left(\frac n{q_n}\right)+(1-q_n)\,\log_2\left(\frac{m-n}{1-q_n}\right)$$

That equation allows to numerically find $q_n$ from $(n,m,H)$ in a distribution maximizing $q_n$. We restrict to $n/m\le q_n<1$ and use successive approximation.

---

The constraint $p_{n-1}\ge p_n$ complicates exhibiting a distribution minimizing $H$ for given $(n,m,q_n)$.

For notational simplicity, define the extra $p_m=0$, and allow $p_i\ge0$ for $n<i<m$ when the original statement has $p_i>0$ (removing terms with $p_i=0$ from the sum defining $H$). A minor consequence is that perhaps a bound we'll get for $q_n$ will be reached for some distribution, when it could only be asymptotically reached in the original statement.

For $q_n$ and $p_n$ fixed, the contribution to $H$ of the $p_i$ with $0\le i<n$ is minimized when $1\le i<n\implies q_i=q_n$; and the contribution of the other $p_i$ is minimized when for some $m'$ with $n\le m'\le m$, it holds that $n\le i<m'\implies p_i=p_n$ and $m'<i<m\implies p_i=0$.

Things gets conjectural from there on. For $q_n$ and $m'$ fixed, and for any distribution of $p_i$ as in the above paragraph which further has a $p_n$ minimizing $H$, it seems plausible that $p_{m'}=0$ or $p_{m'}=p_n$; and then we can restrict to the former by otherwise incrementing $m'$. Thus for given $(n,m,q_n)$, any distribution minimizing $H$ would be for some $m'$ with $n<m'\le m$ and $$p_i=\begin{cases} 1-(m'-1)(1-q_n)/(m'-n)&\text{ if }i=0\\ (1-q_n)/(m'-n)&\text{ if }1\le i<m'\\ 0&\text{ if }m'\le i<m \end{cases}$$ with $p_0\ge p_1$ restricting $m'$ to $n/q_n\le m'\le m$. We get $$\begin{align} H&=-\left(1-(m'-1)\,\frac{1-q_n}{m'-n}\right)\,\log_2\left(1-(m'-1)\,\frac{1-q_n}{m'-n}\right)\\ &\quad-(m'-1)\,\frac{1-q_n}{m'-n}\,\log_2\left(\frac{1-q_n}{m'-n}\right) \end{align}$$ That tentative equation would allow to numerically find $q_n$ from $(n,m,H)$ in a distribution minimizing $q_n$. We restrict to $n/q_n\le m'\le m$ and use successive approximation to find $q_n$ and $m'$ minimizing it.

When $n$ is much smaller than $2^H$, the right $m'$ will often be $\lceil 2^H\rceil$ and the minimum $q_n$ is about $n\;2^{-H}$ (exactly when $m'=2^H$).

---

For $n=1000$ out of $m=2^{48}$ with $H=20$-bit entropy, I get $0.000953<q_n<0.7573$ (confirmation, fix, improvements welcome).

The upper bound illustrates that approximating $q_n$ when $n\ll2^H$ per the intuitively plausible $n/2^H$ (for lack of knowledge of $H_\text{min}$) can be dramatically underestimating the probability of unauthorized log-in for an adversary assumed perfect at trying passwords by decreasing probability. I have seen and made that mistake!