Picking vs. Guessing Secrets: A Game-Theoretic Analysis (Technical Report)
This work addresses the fundamental trade-off between usability and security in secret selection, which is critical for applications like authentication and cryptography, though it is incremental in applying game theory to this domain.
The paper tackles the problem of optimally choosing secrets (e.g., passwords or cryptographic keys) by balancing usability and security against strategic adversaries, using a game-theoretic framework. It finds that optimal strategies depend on adversary types: for capped-guess adversaries, uniform randomization over a subset is optimal, while for cost-based adversaries, Nash Equilibria may fail, highlighting the need for credible commitments.
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.