  Choosing a hard-to-guess secret is a prerequisite in many security
applications. Whether it is a password for user authentication or a secret key
for a cryptographic primitive, picking it requires the user to trade-off
usability costs with resistance against an adversary: a simple password is
easier to remember but is also easier to guess; likewise, a shorter
cryptographic key may require fewer computational and storage resources but it
is also easier to attack. A fundamental question is how one can optimally
resolve this trade-off. A big challenge is the fact that an adversary can also
utilize the knowledge of such usability vs. security trade-offs to strengthen
its attack. In this paper, we propose a game-theoretic framework for analyzing
the optimal trade-offs in the face of strategic adversaries. We consider two
types of adversaries: those limited in their number of tries, and those that
are ruled by the cost of making individual guesses. For each type, we derive
the mutually-optimal decisions as Nash Equilibria, the strategically
pessimistic decisions as maximin, and optimal commitments as Strong Stackelberg
Equilibria of the game. We establish that when the adversaries are faced with a
capped number of guesses, the user's optimal trade-off is a uniform
randomization over a subset of the secret domain. On the other hand, when the
attacker strategy is ruled by the cost of making individual guesses, Nash
Equilibria may completely fail to provide the user with any level of security,
signifying the crucial role of credible commitment for such cases. We
illustrate our results using numerical examples based on real-world samples and
discuss some policy implications of our work.
