[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Guessing Bank PINs by Winning a Mastermind Game

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

In this paper we formally prove that the problem of cracking, i.e., correctly guessing, bank PINs used for accessing Automated Teller Machines and the problem of solving the Generalized Mastermind Game are strictly related. The Generalized Mastermind Game with N colors and k pegs is an extension of the well known Mastermind game, played with 6 colors and 4 pegs. The rules are the same, one player has to conceal a sequence of k colored pegs behind a screen and another player has to guess the exact position and colors of the pegs using the minimal number of moves. We first introduce a general game, called the Extended Mastermind Game (EMG), and we then formally prove it includes both the Generalized Mastermind Game and the PIN cracking Problem. We then present some experimental results that we have devised using a computer program that optimizes a well known technique presented by Knuth in 1976 for the standard Mastermind game. We finally show that the program improves the as state-of-the-art Mastermind solvers as it is able to compute strategies for cases which were not yet covered. More interestingly, the same solving strategy is adapted also for the solution of the PIN cracking problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Hackers crack cash machine PIN codes to steal millions. The Times online. http://www.timesonline.co.uk/tol/money/consumer_affairs/article4259009.ece

  2. Mastermind. http://commons.wikimedia.org/wiki/File:Mastermind.jpg

  3. PIN Crackers Nab Holy Grail of Bank Card Security. Wired magazine blog ’Threat Level’. http://blog.wired.com/27bstroke6/2009/04/pins.html

  4. Bento, L., Pereira, L., Rosa, A.: Mastermind by evolutionary algorithms. In: Proc. ACM Symp. Applied Computing, San Antonio, Texas, 28 February–2 March, pp. 307–311. ACM Press, New York (1999)

    Google Scholar 

  5. Berghman, L., Goossens, D., Leus, R.: Efficient solutions for Mastermind using genetic algorithms. Technical report KBI 0806, Katholieke Universiteit Leuven, Department of Decision Sciences and Information Management, 2006

  6. Berkman, O., Ostrovsky, O.M.: The unbearable lightness of PIN cracking. In: 11th International Conference, Financial Cryptography and Data Security (FC 2007), Scarborough, Trinidad and Tobago, February 12–16. Lecture Notes in Computer Science, vol. 48862, pp. 224–238. Springer, Berlin (2007)

    Chapter  Google Scholar 

  7. Bond, M., Clulow, J.: Extending security protocol analysis: new challenges. Electron. Notes Theor. Comput. Sci. 125, 13–24 (2005)

    Article  Google Scholar 

  8. Bond, M., Zielinski, P.: Decimalization table attacks for pin cracking. Technical report UCAM-CL-TR-560, University of Cambridge, Computer Laboratory, 2003. http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-560.pdf

  9. Centenaro, M., Focardi, R., Luccio, F., Steel, G.: Type-based analysis of PIN processing APIs. In: Proceedings of the 14th European Symposium on Research in Computer Security (ESORICS 09). Lecture Notes in Computer Science, vol. 5789, pp. 53–68. Springer, Berlin (2009)

    Google Scholar 

  10. Chen, Z., Cunha, C., Homer, S.: Finding a hidden code by asking questions. In: Computing and Combinatorics Second Annual International Conference (COCOON 96), Hong Kong, June 17–19. Lecture Notes in Computer Science, vol. 1090, pp. 50–55. Springer, Berlin (1996)

    Google Scholar 

  11. Chvatal, V.: Mastermind. Combinatorica 3, 325–329 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  12. Clulow, J.: The design and analysis of cryptographic APIs for security devices. Master’s thesis, University of Natal, Durban, 2003

  13. Focardi, R., Luccio, F., Steel, G.: Blunting differential attacks on PIN processing APIs. In: Proceedings of the 14th Nordic Conference on Secure IT Systems (NORDSEC 09), October. Lecture Notes in Computer Science, vol. 5838/2009, pp. 88–103. Springer, Berlin (2009)

    Google Scholar 

  14. Focardi, R., Luccio, F.L.: Cracking bank pins by playing mastermind. In: Proc. Fith International Conference Fun with algorithms (FUN 10), June 2–4. Lecture Notes in Computer Science, vol. 6099, pp. 202–213. Springer, Berlin (2010)

    Chapter  Google Scholar 

  15. Focardi, R., Luccio, F.L.: Cracking bank pins by playing mastermind. http://www.dsi.unive.it/~focardi/MM_PIN/FUN10corrected.pdf (2010). Corrected version of FUN10

  16. Goddard, W.: Mastermind revisited. J. Comb. Math. Comb. Comput. 51, 215–220 (2004)

    MathSciNet  MATH  Google Scholar 

  17. Jäger, G., Pezarski, M.: The number of pessimistic guesses in generalized mastermind. Inf. Process. Lett. 109, 635–641 (2009)

    Article  MATH  Google Scholar 

  18. Kalisker, T., Camens, D.: Solving mastermind using genetic algorithms. In: Proc. Genetic and Evolutionary Computation Conference (GECCO 03), July 12–16. Lecture Notes in Computer Science, vol. 2724, pp. 1590–1591. Springer, Berlin (2003)

    Google Scholar 

  19. Knuth, D.: The computer as a master mind. J. Recreat. Math. 9, 1–6 (1976)

    MathSciNet  Google Scholar 

  20. Koyama, M., Lai, T.: An optimal mastermind strategy. J. Recreat. Math. 25, 251–256 (1993)

    MATH  Google Scholar 

  21. Steel, G.: Formal analysis of PIN block attacks. Theor. Comput. Sci. 367(1–2), 257–270 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  22. Stuckman, J., Zhang, G.: Mastermind is NP-complete. INFOCOMP J. Comput. Sci. 5, 25–28 (2006)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. c/o Dipartimento di Scienze Ambientali, Informatica e Statistica (DAIS), Università Ca’ Foscari Venezia, via Torino 155, 30172, Venezia, Italy

    Riccardo Focardi & Flaminia L. Luccio

Authors
  1. Riccardo Focardi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Flaminia L. Luccio
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Flaminia L. Luccio.

Additional information

A preliminary version of this paper has been presented at the 5th International Conference on Fun with Algorithms (FUN’10) [14].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Focardi, R., Luccio, F.L. Guessing Bank PINs by Winning a Mastermind Game. Theory Comput Syst 50, 52–71 (2012). https://doi.org/10.1007/s00224-011-9340-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-011-9340-9

Keywords

Search

Navigation