Measure of randomness that maps well to “hard to guess”?

It was recently pointed out to me that entropy does not necessarily map well to "hard to guess".

E.g.: consider a distribution where there's a very high (say, 90%) chance you select a single, specific value, and otherwise you draw from some other high entropy distribution (say, generating 1024 bits uniformly randomly).

Such a distribution can have arbitrarily high entropy (in the case above, ~103 bits I believe) despite the odds of an attacker guessing in one try also being arbitrarily high (in the case above, 90%).

Is there some other measure of randomness to use that better captures this sense of "hard to guess"? Some things I thought of were:

• Maximum information content instead of expected value. But this feels like it would treat distributions as equal too aggressively.
• Median information content. But this also seems like it might be possible to "game".
• Directly measuring something closer to what I care about, like "average number of guesses an attacker would need to make". But this seems difficult to compute, and I was hoping for something simpler.
• Average numbers of guesses tend to be easy to compute! – whuber Feb 18 '19 at 20:33

Formulating the problem as password guessing

It's sounds like you have in mind a situation where you randomly choose a password from some probability distribution, then want to quantify how difficult it is for an attacker to guess that password. And, you assume a threat model where the attacker 1) has access to the password generating distribution, 2) has the ability to check whether every guessed password is correct, and 3) incurs equal cost for checking each password. The optimal strategy for the attacker in this scenario is to guess passwords in descending order of their probability. And, we can equate "hardness of guessing" with number of guesses.

Suppose we have possible passwords $$\{x_1, \dots, x_N\}$$ with corresponding probabilities $$\{p_1, \dots, p_N\}$$. Assume without loss of generality that the passwords have been sorted in descending order of their probabilities. So, the attacker will guess them in order. Let $$G$$ be a random variable representing the number of guesses needed for the attacker to find the password. Then, the probability that the attacker requires $$k$$ guesses is simply equal to the probability that the true password is $$x_k$$. That is:

$$\Pr(G=k) = p_k$$

Since we've equated hardness of guessing with number of guesses, this distribution contains everything there is to know. There are multiple ways to summarize this distribution with a single number, and each yields a different measure of "hardness". Here are two possibilities:

Expected number of guesses

The expected number of guesses is straightforward:

$$E[G] = \sum_{k=1}^N k p_k$$

Consider the example password distribution you described: we choose a particular (crappy) password with some high probability $$q$$, otherwise we select uniformly at random from $$n$$ other possibilities. In this case, the expected number of guesses works out to $$\frac{1}{2} (n + q - nq + 1)$$. For the specific numbers you gave ($$q=0.9, n=2^{1024}$$), this is approximately $$2^{1020}$$ guesses. That's far more guesses than would be required on average for a uniform password distribution with the equivalent amount of entropy (~103 bits). Yet, as you mentioned, the attacker can guess correctly on the first try with 90% probability. What's happening here is that you've constructed a distribution with an extremely long tail (i.e. there's a small probability that an enormous number of guesses will be needed).

Median number of guesses

You could also consider the median number of guesses. The cumulative distribution function of $$G$$ gives the probability that the attacker guesses correctly in $$k$$ guesses or fewer:

$$F_G(k) = \sum_{j=1}^k p_j$$

A median can be calculated as the number of guesses at which the cumulative probability meets or exceeds 0.5:

$$\text{median}(G) = \min \big\{ k \mid F_G(k) \ge 0.5 \big\}$$

In the example, the median is 1 guess (assuming the crappy password probability $$q \ge 0.5$$).