Decimalisation Table Attacks

In this section, we describe three attacks. First, we present a 2-stage simple static scheme which needs only about 24 guesses on average. The shortcoming of this method is that it needs almost twice as many guesses in the worst case. We show how to overcome this difficulty by employing an adaptive approach and reduce the number of necessary guesses to 22. Finally, we present an algorithm which uses PIN offsets to deduce a PIN from a single correct encrypted guess, as is typically supplied by the customer from an ATM.

4.1 Initial Scheme

The initial scheme consists of two stages. The first stage determines which digits are present in the PIN. The second stage consists in trying all the possible pins composed of those digits.

Let D_orig be the original decimalisation table. For a given digit i, consider a binary decimalisation table D with the following property. The table D has 1 at position x if and only if D_orig has the digit i at that position. In other words,

Dj[x]

1 if Dorig [x] = i,

0 otherwise.

For example, for a standard table D_orig = 0123 4567 89012345, the value of D₃ is

0001 0000 0000 0100.

In the first phase, for each digit i, we check the original PIN against the decimalisation table Dj with a trial PIN of 0000. It is easy to see that the test fails exactly when the original PIN contains the digit i. Thus, using only at most 10 guesses, we have determined all the digits that constitute the original PIN.

In the second stage we try every possible combination of those digits. Their actual number depends on how many different digits the PIN contains. The table below gives the details.

Digits	Possibilities
A	AAAA(1)
AB	ABBB(4), AABB(6), AAAB(4)
ABC	AABC(12), ABBC(12), ABCC(12)
ABCD	ABCD(24)

The table shows that the second stage needs at most 36 guesses (when the original PIN contains 3 different digits), which gives 46 guesses in total. The expected number of guesses is, however, as small as about 23.5.

4.2 Adaptive Scheme

The process of cracking a PIN can be represented by a binary search tree. Each node v contains a guess, i.e., a decimalisation table D_v and a pin p_v. We start at the root node and go down the tree along the path that is determined by the results of our guesses. Let p_orig be the original PIN. At each node, we check whether D_v (p_orig) = p_v. Then, we move to the right child if yes and to the left child otherwise.

Each node v in the tree can be associated with a list P_v of original PINs such that p G P_v if and only if v is reached in the process described in the previous paragraph if we take p as the original PIN. In particular, the list associated with the root node contains all possible pins and the list of each leaf should contain only one element: an original PIN

^porig^.

Consider the initial scheme described in the previous section as an example. For simplicity assume that the original PIN consists of two binary digits and the decimalisation table is trivial and maps 0 — 0 and 1 — 1. Figure 6 depicts the search tree for these settings.

The main drawback of the initial scheme is that the number of required guesses depends strongly on the original PIN p_orig. For example, the method needs only 9 guesses for porig = 9999 (because after ascertaining that digit 0-8 do not occur in porig this is the only

possibility), but there are cases where 46 guesses are required. As a result, the search tree is quite unbalanced and thus not optimal.

One method of producing a perfect search tree (i.e., the tree that requires the smallest possible numbers of guesses in the worst case) is to consider all possible search trees and choose the best one. This approach is, however, prohibitively inefficient because of its ex­ponential time complexity with respect to the number of possible PINs and decimalisation tables.

It turns out that not much is lost when we replace the exhaustive search with a simple heuristics. We will choose the values of D_v and p_v for each node v in the following manner. Let P_v be the list associated with node v. Then, we look at all possible pairs of D_v and p_v and pick the one for which the probability of D_v (p) = p_v for p G P_v is as close to ¹ as possible. This ensures that the left and right subtrees are approximately of the same size so the whole tree should be quite balanced.

This scheme can be further improved using the following observation. Recall that the original PIN p_orig is a 4-digit hexadecimal number. However, we do not need to determine it exactly; all we need is to learn the value of p = D_orig(p_orig). For example, we do not need to be able to distinguish between 012D and ABC3 because for both of them p = 0123. It can be easily shown that we can build the search tree that is based on the value of p instead of p_orig provided that the tables D_v do not distinguish between 0 and A, 1 and B and so on. In general, we require each Dv to satisfy the following property: for any pair of hexadecimal digits x, y: D_orig[x] = D_orig[y] must imply D_v[x] = D_v[y]. This property is not difficult to satisfy and in reward we can reduce the number of possible PINs from 16⁴ = 65 536 to 10⁴ = 10 000. Figure 7 shows a sample run of the algorithm for the original PIN p_orig = 3491.

4.3 PIN Offset Adaptive Scheme

When the attacker does not know any encrypted trial PINs, and cannot encrypt his own guesses, he can still succeed by manipulating the offset parameter used to compensate for customer PIN change. Our final scheme has the same two stages as the initial scheme, so

our first task is to determine the digits present in the PIN.

Assume that an encrypted PIN block containing the correct PIN for the account has been intercepted (the vast majority of arriving encrypted PIN blocks will satisfy this criterion), and for simplicity that the account holder has not changed his PIN and the correct offset is 0000. Using the following set of decimalisation tables, the attacker can determine which digits are present in the correct PIN.

D\X\ = J Dorig + 1 if Dorig[x] = i,

1 D_orig [x\ otherwise.

For example, for Dorig - 0123 4567 89012345, the value of D3 is 0124 4567 89012445. He supplies the correct encrypted PIN block and the correct offset each time.

As with the initial scheme, the second phase determines the positions of the digits present in the PIN, and is again dependent upon the number of repeated digits in the original PIN. Consider the common case where all the PIN digits are different, for example 1583. We can try to determine the position of the single 8 digit by applying an offset to different digits and checking for a match.

Guess Offset	Guess Decimalisation Table	Customer Guess	Customer Guess + Guess Offset	Decimalised Original PIN	Verify Result
0001	0123 4567 99012345	1583	1584	1593	no
0010	0123 4567 99012345	1583	1593	1593	yes
0100	0123 4567 99012345	1583	1683	1593	no
1000	0123 4567 99012345	1583	2583	1593	no

Each different guessed offset maps the customer's correct guess to a new PIN which may or may not match the original PIN after it is decimalised using the modified table. This procedure is repeated until the position of all digits is known. Cases with all digits different will require at most 6 transactions to determine all the position data. Three different digits will need a maximum of 9 trials, two digits different up to 13 trials, and if all the digits are the same no trials are required as there are no permutations. When the parts of the scheme are assembled, 16.5 guesses are required on average to determine a given PIN.