Probability Theory for Pickpockets--ec-PIN Guessing

This abstract briefly describes an algorithm for determining the most likely 4-digit PINs associated with a debit card used at EuroCheque (ec) ATMs. We determine the probability of every PIN based on knowledge of the PIN-generation method and the data on the magnetic stripe. A card thief could use this strategy to optimally select the three PINs that he can try on a stolen card before it will be invalidated. The analysis shows a signicant security problem of the PIN-generation algorithm, which allows the presented PIN-guess strategy to achieve a considerably higher success rate than a random guess would. The reader is assumed to be familiar with basic probability theory. The analyzed PIN-generation algorithm has been used by German banks from 1981 until 1997 according to documents available to the author.

Users of ec-cards cannot select their own PIN. The bank calculates the PIN for each customer as illustrated in the diagram. A 16-digit decimal number is formed by concatenating ve digits of the bank routing number, the ten digit account number, and a single digit card sequence number. This number is transformed into a 64-bit pattern by encoding each digit with its 4- bit binary value (BCD). The result is encrypted using the DES algorithm with a secret 56-bit institute key KI . The resulting 64-bit ciphertext can be written as a 16-digit hexadecimal number. We take the digits 3{6 and replace all occurrences of the letters A{F by digits 0{5 respectively. If the rst of those four digits is a 0, we replace it by a 1. ATM networks owned by the card-issuing bank know KI . They reconstruct the PIN the same way and compare it with what the customer has entered. ATM networks of other banks use a pool key KP1 instead, which results in a dierent PIN of course. The magnetic stripe of each card contains a 4-digit correction oset O1 that an ATM using KP1 has to add without carry-over to the digits 3{6 of the decimalized DES result, to get the PIN known by the customer. In the decimalized DES result obtained with a pool key, a leading zero is not replaced. Since KP1 is known by all banks in Europe, it could be compromised more easily. Therefore, there exist two backup pool keys KP2 and KP3 and the card stripe stores two corresponding osets O2 and O3. The emergency plan should KP1 be compromised one day is to switch to KP2 and overwrite O1 on all cards at the next ATM visit. The problem that the designer of this PIN-handling system had not understood is that these pool key osets provide valuable hints for someone who tries to guess a PIN.

From track 3 of the magnetic stripe of a card, we know the 12 oset digits

Our goal is to determine four PIN digits

that are most likely the actual PIN for this card.

Let ~ Pj denote the random variable representing the j-th digit of the actual PIN of a card, and let ~Oi;j denote the random variable representing the j-th digit in oset number i. We assume that all hexadecimal digits of the four DES results are mutually independent and that the 16 digits are uniformly distributed, a required characteristic of any good block-cipher algorithm such as DES. Then, the distributions of these random variables are due to the applied decimalization method (see diagram) as follows:
A most likely PIN ^ P is a P for which the conditional probability is maximal. Since all digits of the PIN are determined independently of each other, we can determine a most likely j-th PIN digit ^ Pj as a Pj that maximizes and get a most likely PIN simply as the combination of the most likely digits for each position.

We can turn around this conditional probability as follows (Bayes' theorem)

and since we assumed the DES results with the three pool keys to be mutually independent, we can replace the conditional probabilities for the combination of digits from all three osets
by the product of the probabilities for the individual o set digits, and thus we get

This formula uses only the known distributions given in (1). Based on it, we can easily write
a small program to calculate for all given O1;j , O2;j, and O3;j , and determine a ^ Pj for which this probability is maximal. We do this for all four digit positions j and get this way a most likely PIN candidate ^ P. The probability that this PIN is correct is the product of the probabilities that the individual digits ^ Pj are each
correct, as calculated above. It can get as high as 0:948%1/105.

We have so far described how to nd a most likely PIN for a specic card for which we know the osets, and we can calculate its success probability. We now calculate, what success probability we expect if we do not have the osets of a specic card given, but if we pick a random card. This can be estimated per digit position j with another small program as follows. We try all 164 possible combinations for the four hexadecimal digits (W;X; Y; Z) in each of the four DES results that determine one digit in the PIN and one in each oset. We determine from this quadruple|like a bank does when a new card is issued|the j-th digit of the PIN and the three osets as follows:

This way, we have generated a set of 164 simulated cards that has the same PIN and oset
digit distribution that we expect from the set of all cards in circulation. Now, we determine
a most likely PIN digit ^ Pj as described above for each of those 164 cards. Since we know for
each of these simulated cards the correct PIN digit Pj , we can count which fraction of the 16sq4 calculated most likely PIN digits ^ Pj is correct and equals the corresponding Pj .

The results of this program run are the following probabilities for a correct guess for each of
the four PIN digit positions j:

Note that if the banks had used a good PIN generation algorithm, we would have expected a random guess success rate of 11% for the rst digit (no leading zero) and 10% for the remaining three digits. By multiplying the actual four per-digit success probabilities above, we get a success probability of 0:00233460:233%1=428 for the most likely PIN. Since a thief has at least three attempts, and since most second or third best PINs have a similar success chance, the probability to get access to the account is roughly three times the success probability of the most likely PIN, this means in the order of 0:7%1/150. Had the banks used a good PIN-generation algorithm, we would have expected only a 1=30000:033% success rate in three attempts, because there are 9000 possible PINs (1000 - 9999). In other words, the security of the ec-PIN system is worse than that of a good system with only three digit PINs, where we would expect a 1/3000:33% success rate in three attempts.

This text did not discuss techniques that allow more than three attempts to enter a PIN. It also did not discuss the cost of determining the DES keys using a brute-force search with special hardware. Both are in the author's opinion valid additional serious concerns regarding the security of the EC card system.

The author wishes to thank Bodo and Ulf Moller from the University of Hamburg for their help and for their suggestions in this analysis.

PIN Calculation for EuroCheque ATM Debit Cards