Riccardo Focardi and Flaminia Luccio
Università Ca' Foscari di Venezia, Italy
focardi@dsi.unive.it, luccio@unive.it
We report on some experiments we performed using an extension on Knuth's technique for the Mastermind (see [1]) applied to both Mastermind and PIN cracking attacks.
Mastermind. The following table summarizes the worst cases of the strategies we have computed for the game with N colors and K pegs. Clicking on the number it is possible to download the file containing the whole strategy. (We have only made available a subset of the computed strategies.)
|
N\K |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
2 |
3 |
4 |
4 |
5 |
|||||
|
3 |
4 |
4 |
4 |
|
|
||||
|
4 |
4 |
4 |
4 |
|
|
|
|
||
|
5 |
5 |
5 |
5 |
|
|
|
|
|
|
|
6 |
5 |
5 |
|
|
|
|
|
|
|
|
7 |
6 |
6 |
|
|
|
|
|
|
|
|
8 |
6 |
6 |
|
|
|
|
|
|
|
|
9 |
7 |
7 |
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
Strategies in yellow are the first
presented in literature for the corresponding values of N and K. We
briefly explain how to read strategies. Let us show it through an
example:
|
N=6, K=4, Mastermind ====== (max 256) guess: 0011====== [0.0.0] ====== (max 46) guess: 2234====== [1.0.0] The solution is: 5555 [1.0.1] ====== (max 3) guess: 5535====== [2.0.0] ==> IMPOSSIBLE [2.0.1] ==> IMPOSSIBLE [2.0.2] The solution is: 3353 ...... |
(max n) before “guess” reports the maximum number n of surviving solutions among all the possible outcomes of the guess. In the first guess, e.g., we know that after playing 0011 the outcome with the maximum number of solutions still possible, will have 256 of them. This parameter is used to pick the guess among all the possible ones. (The one with the lowest max is chosen.)
“guess: m”, is the guess to be played;
[l.b.w] denotes the outcome: level “l” is the number of guesses played before the present one, “b” is the number of blacks and “w” is the number of whites;
aside each outcome there can be: (i) a solution, if only one is possible, (ii) “IMPOSSIBLE” to note that this outcome is not possible or (iii) a new guess representing the next move to perform;
notice that indentation follows the level depth, i.e., the number of played guesses.
The above example can be read as follows:
play 0011
if the outcome is 0 whites and blacks, play 2234
if the outcome is 0 whites and blacks, the solution is 5555 (in fact, 01234 do not belong to the sequence and we have N=6 colors)
if, instead, the outcome is 0 blacks and 1 white we play 5535, and so on....
PIN cracking. The program used to find out the above strategies for Mastermind has been applied to the PIN cracking problem. In particular we have studied the decimalization attack of [2], in order to find strategies to reconstruct the PIN using a minimum number of API calls. The idea is to play an extended Mastermind in which guesses can contain sets of pegs. In fact, it is possible to see that these guesses are implementable via one API call. The return value is boolean: true if the PIN is correct and false otherwise. Answer true corresponds, in the Mastermind game, to 4 blacks.
Our strategies can be read as the above one apart that outcomes have the form [l,a] where “l” is still the level and “a” is the boolean answer. We illustrate via one example.
|
N=10, K=4, PIN cracking .... ====== (max 81) {7,8,9}{7,8,9}{7,8,9}{7,8,9} ====== [5,True] ====== (max 16) {9,7}{9,7}{9,7}{9,7} ====== [6,True] ====== (max 1) {7}{7}{7}{7} ====== [7,True] The solution is: 7777 .... |
The first reported guess is {7,8,9}{7,8,9}{7,8,9}{7,8,9}, which represents an extended guess asking whether (all of) the PIN digits are in the set {7,8,9}. The answer is True (4 blacks). The strategy goes on restricting the set to {9,7} and, if True again, with {7}, which gives the solution 7777.
We report a more interesting fragment of the strategy, with guesses containing two sets: one and its complementary (with respect to the surviving colors):
|
N=6, K=4, S=2, PIN cracking .... ====== (max 1) {7,9}{8}{8}{7,9} ====== [16,True] The solution is: 7889 ====== (max 2) {7,9}{8}{8}{7,9} ====== [16,False] ====== (max 1) {7,9}{7,9}{8}{7,9} ====== [17,True] The solution is: 7989 ====== (max 1) {7,9}{7,9}{8}{7,9} ====== [17,False] The solution is: 7899 .... |
Our strategies have the following average cases, in terms of API calls
|
N\K |
4 |
5 |
|
6 |
||
|
10 |
Results in yellow are new or improve known ones. (Even results for N=6 are new but PINs usually have 10 digits, so PIN cracking with N=6 has never been studied. We start from it as it is the base case for Mastermind). In particular, the previous bound for average case N=10, K=4 was 16.145 [3]. Strategies are downloadable by clicking on the numbers.
Downloads
The python program for PIN cracking. Usage 'python PINcrack.py > outfile'
The amended FUN'10 paper, with correct values for PIN cracking (the original paper appears in FUN'10 proceedings, Springer LNCS 6099)
References
[1] D. Knuth. The Computer as a Master Mind. Journal of Recreational Mathematics, 9:1-6, 1976.
[2] M. Bond and P. Zielinski. 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
[3] G. Steel. Formal Analysis of PIN Block Attacks. Theoretical Computer Science, 367(1-2):257--270, November 2006.