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.
Similar content being viewed by others
References
Hackers crack cash machine PIN codes to steal millions. The Times online. http://www.timesonline.co.uk/tol/money/consumer_affairs/article4259009.ece
Mastermind. http://commons.wikimedia.org/wiki/File:Mastermind.jpg
PIN Crackers Nab Holy Grail of Bank Card Security. Wired magazine blog ’Threat Level’. http://blog.wired.com/27bstroke6/2009/04/pins.html
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)
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
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)
Bond, M., Clulow, J.: Extending security protocol analysis: new challenges. Electron. Notes Theor. Comput. Sci. 125, 13–24 (2005)
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
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)
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)
Chvatal, V.: Mastermind. Combinatorica 3, 325–329 (1983)
Clulow, J.: The design and analysis of cryptographic APIs for security devices. Master’s thesis, University of Natal, Durban, 2003
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)
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)
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
Goddard, W.: Mastermind revisited. J. Comb. Math. Comb. Comput. 51, 215–220 (2004)
Jäger, G., Pezarski, M.: The number of pessimistic guesses in generalized mastermind. Inf. Process. Lett. 109, 635–641 (2009)
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)
Knuth, D.: The computer as a master mind. J. Recreat. Math. 9, 1–6 (1976)
Koyama, M., Lai, T.: An optimal mastermind strategy. J. Recreat. Math. 25, 251–256 (1993)
Steel, G.: Formal analysis of PIN block attacks. Theor. Comput. Sci. 367(1–2), 257–270 (2006)
Stuckman, J., Zhang, G.: Mastermind is NP-complete. INFOCOMP J. Comput. Sci. 5, 25–28 (2006)
Author information
Authors and Affiliations
Corresponding author
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
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
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-011-9340-9