Picking vs Guessing Secrets: A Game-Theoretic Analysis

Arman Khouzani

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 costs for resistance against an adversary. More challenging is the fact that an adversary can also utilise the knowledge of such usability vs security trade-offs to strengthen its attack. A game-theoretic framework can provide optimal trade-offs in the face of a strategic reaction of adversaries, where optimality can be defined with respect to the capabilities of the adversary and different strategic measures. Namely, 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 randomizations to commit to as Stackelberg Equilibria of the game.

When the adversaries are faced with a capped number of guesses, we establish that the optimal trade-off policy of a user is in general still a uniform randomization, but over a subset of the secret domain. On the other hand, when the attacker strategy is ruled by the cost of making individual guesses, we show how Nash Equilibria may completely fail to provide the user with any level of security, signifying the vital role of credible commitment for such cases.