Game Design for Better Security of Combination Locks

Jean-Pierre Astudillo Guerra, Karim Ahmed, Ryan Maher, Eddie Ubri, Jeremy BlumAAAI 2022 · DOI

Abstract

Traditional letter-based combination locks prioritize usability, often at the expense of security. This paper applies game theory and genetic algorithms to optimize lock configurations, modeling a thief’s brute-force strategy as a Probabilistic Traveling Salesman Problem (PTSP). The resulting evolved designs are 77% harder to crack and support 56% more valid words than leading commercial alternatives.

Introduction: The Security-Usability Gap

Most "Wordlocks" or letter-based dial locks are engineered for marketing, ensuring users can easily spell common words like "BIKE" or "FAST." However, this focus on usability often creates a security vacuum. A thief does not merely try every possible combination; they prioritize every possible word.

The security of these locks depends on two factors: the total number of dictionary words the lock can form and the physical effort (the number of dial turns) required to transition between those words. This research treats the configuration of letters on the wheels as an optimization problem, aiming to maximize the "work" a thief must perform.

Methodology: A Three-Player Game

The authors frame the interaction as a three-player game involving:

  1. The Designer: Sets the letters and their order on each wheel to maximize security.
  2. The Owner: Picks a word at random from the available combinations.
  3. The Thief: Executes a brute-force search, moving through an a priori tour of all possible words.

To solve the designer's problem, a Genetic Algorithm (GA) was employed. Since calculating the exact optimal path for a thief is an NP-hard problem (the PTSP), the GA uses a lower bound fitness function. This function estimates the thief's effort by averaging the distances to the two nearest words for every possible word the lock can create.

The GA uses specialized operators such as initialization seeded by dictionary word frequency, modified ordered crossover (OX) to maintain unique letter sets, and targeted mutations to increase both word count and physical distance between words.

Datasets

The study utilized the Google Web Trillion Word Corpus, containing 333,333 common English strings. The researchers filtered this to 12,977 3-letter strings and 31,140 4-letter strings, including common "non-dictionary" strings like "yolo," reflecting realistic user choices.

Key Insights

  • Security is Geometric: Brute-force security is about the "distance" between valid points in the keyspace. Strategic letter placement forces a thief to rotate dials significantly more for every attempt.
  • The Vowel Paradox: While spreading vowels might seem intuitive to increase distance, clustering them actually increased the total word count so significantly that it outweighed the distance benefit, making the lock harder to crack.
  • Holistic Optimization: The selection and sequence of letters are deeply coupled. The GA’s ability to optimize both simultaneously allowed it to outperform heuristic-based commercial designs.

Results and Comparison

The GA-designed locks were compared against four popular commercial models from Master Lock and Wordlock.

Comparison of the number of words created by various locks.

As shown in the data, the GA-designed locks could form 56.7% more words than the best commercial competitor. Furthermore, the overall security—measured by the expected number of operations (dial turns plus open attempts) required to crack the lock—was significantly higher.

Comparison of the fitness (security level) of various locks.

The expected cracking cost for the GA lock was 77.4% higher than commercial alternatives. Additionally, the GA consistently converged to high-fitness solutions across 25 different runs, demonstrating the robustness of the approach.

Limitations and Future Work

The current model assumes a uniform probability that a lock owner will pick any possible word. Future work will incorporate word frequency into the thief’s strategy to account for human biases. Additionally, while this study focused on 4-wheel locks, scaling to 5-wheel versions presents a significantly larger search space requiring more efficient heuristics. Finally, the model currently only addresses brute-force dialing and does not account for physical bypass methods like shimming or picking.

Summary updated

BibTeX
@inproceedings{guerra2022game,
  author = {Jean-Pierre Astudillo Guerra and Karim Ahmed and Ryan Maher and Eddie Ubri and Jeremy Blum},
  title = {{Game Design for Better Security of Combination Locks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21547},
}
Figure