Have you ever wonder what would happen if you loose your credit or debit card and someone finds it. Would this person be able to withdraw cash from an ATM guessing, somehow, your PIN? Moreover, if you were who finds someone's card would you try to guess the PIN and take the chance to get some easy money? Of course the answer to both questions should be "no". This work does not deal with the second question, it is a matter of personal ethics. Herewith I try to answer the first question.
All the information used for this work is public and can be freely found in Internet. The rest is a matter of mathematics and programming, thus we can learn something and have some fun. I reveal no secrets. Furthermore, the aim (and final conclusion) of this work is to demonstrate that PIN algorithms are still strong enough to provide sufficient security. We all know technology is not the weak point.
This work analyzes one of the most common PIN algorithms, VISA PVV, used by many ATM cards (credit and debit cards) and tries to find out how resistant is to PIN guessing attacks. By "guessing" I do not mean choosing a random PIN and trying it in an ATM. It is well known that generally we are given three consecutive trials to enter the right PIN, if we fail ATM keeps the card. As VISA PIN is four digit long it's easy to deduce that the chance for a random PIN guessing is 3/10000 = 0.0003, it seems low enough to be safe; it means you need to loose your card more than three thousand times (or loosing more than three thousand cards at the same time until there is a reasonable chance of loosing money.
What I really meant by "guessing" was breaking the PIN algorithm so that given any card you can immediately know the associated PIN. Therefore this document studies that possibility, analyzing the algorithm and proposing a method for the attack. Finally we give a tool which implements the attack and present results about the estimated chance to break the system. Note that as long as other banking security related algorithms (other PIN formats such as IBM PIN or card validation signatures such as CVV or CVC) are similar to VISA PIN, the same analysis can be done yielding nearly the same results and conclusions.
VISA PVV algorithm
One of the most common PIN algorithms is the VISA PIN Verification Value (PVV). The customer is given a PIN and a magnetic stripe card. Encoded in the magnetic stripe is a four digit number, called PVV. This number is a cryptographic signature of the PIN and other data related to the card. When a user enters his/her PIN the ATM reads the magnetic stripe, encrypts and sends all this information to a central computer. There a trial PVV is computed using the customer entered PIN and the card information with a cryptographic algorithm. The trial PVV is compared with the PVV stored in the card, if they match the central computer returns to the ATM authorization for the transaction. See in more detail.
The description of the PVV algorithm can be found in two documents linked in the previous page. In summary it consists in the encryption of a 8 byte (64 bit) string of data, called Transformed Security Parameter (TSP), with DES algorithm (DEA) in Electronic Code Book mode (ECB) using a secret 64 bit key. The PVV is derived from the output of the encryption process, which is a 8 byte string. The four digits of the PVV (from left to right) correspond to the first four decimal digits (from left to right) of the output from DES when considered as a 16 hexadecimal character (16 x 4 bit = 64 bit) string. If there are no four decimal digits among the 16 hexadecimal characters then the PVV is completed taken (from left to right) non decimal characters and decimalizing them by using the conversion A->0, B->1, C->2, D->3, E->4, F->5. Here is an example:
Output from DES: 0FAB9CDEFFE7DCBA
PVV: 0975
The strategy of avoiding decimalization by skipping characters until four decimal digits are found (which happens to be nearly all the times as we will see below) is very clever because it avoids an important bias in the distribution of digits which has been proven to be fatal for other systems, although the impact on this system would be much lower. See also a related problem not applying to VISA PVV.
The TSP, seen as a 16 hexadecimal character (64 bit) string, is formed (from left to right) with the 11 rightmost digits of the PAN (card number) excluding the last digit (check digit), one digit from 1 to 6 which selects the secret encrypting key and finally the four digits of the PIN. Here is an example:
PAN: 1234 5678 9012 3445
Key selector: 1
PIN: 2468
TSP: 5678901234412468
Obviously the problem of breaking VISA PIN consists in finding the secret encrypting key for DES. The method for that is to do a brute force search of the key space. Note that this is not the only method, one could try to find a weakness in DEA, many tried, but this old standard is still in wide use (now been replaced by AES and RSA, though). This demonstrates it is robust enough so that brute force is the only viable method (there are some better attacks but not practical in our case, for a summary see LASEC memo and for the dirty details see Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 and Heys 2001).
The key selector digit was very likely introduced to cover the possibility of a key compromise. In that case they just have to issue new cards using another key selector. Older cards can be substituted with new ones or simply the ATM can transparently write a new PVV (corresponding to the new key and keeping the same PIN) next time the customer uses his/her card. For the shake of security all users should be asked to change their PINs, however it would be embarrassing for the bank to explain the reason, so very likely they would not make such request.
Preparing the attack
A brute force attack consists in encrypting a TSP with known PVV using all possible encrypting keys and compare each obtained PVV with the known PVV. When a match is found we have a candidate key. But how many keys we have to try? As we said above the key is 64 bit long, this would mean we have to try 2^64 keys. However this is not true. Actually only 56 bits are effective in DES keys because one bit (the least significant) out of each octet was historically reserved as a checksum for the others; in practice those 8 bits (one for each of the 8 octets) are ignored.
Therefore the DES key space consists of 2^56 keys. If we try all these keys will we find one and only one match, corresponding to the bank secret key? Certainly not. We will obtain many matching keys. This is because the PVV is only a small part (one fourth) of the DES output. Furthermore the PVV is degenerated because some of the digits (those between 0 and 5 after the last, seen from left to right, digit between 6 and 9) may come from a decimal digit or from a decimalized hexadecimal digit of the DES output. Thus many keys will produce a DES output which yields to the same matching PVV.
Then what can we do to find the real key among those other false positive keys? Simply we have to encrypt a second different TSP, also with known PVV, but using only the candidate keys which gave a positive matching with the first TSP-PVV pair. However there is no guarantee we won't get again many false positives along with the true key. If so, we will need a third TSP-PVV pair, repeat the process and so on.
Before we start our attack we have to know how many TSP-PVV pairs we will need. For that we have to calculate the probability for a random DES output to yield a matching PVV just by chance. There are several ways to calculate this number and here I will use a simple approach easy to understand but which requires some background in mathematics of probability.
All the information used for this work is public and can be freely found in Internet. The rest is a matter of mathematics and programming, thus we can learn something and have some fun. I reveal no secrets. Furthermore, the aim (and final conclusion) of this work is to demonstrate that PIN algorithms are still strong enough to provide sufficient security. We all know technology is not the weak point.
This work analyzes one of the most common PIN algorithms, VISA PVV, used by many ATM cards (credit and debit cards) and tries to find out how resistant is to PIN guessing attacks. By "guessing" I do not mean choosing a random PIN and trying it in an ATM. It is well known that generally we are given three consecutive trials to enter the right PIN, if we fail ATM keeps the card. As VISA PIN is four digit long it's easy to deduce that the chance for a random PIN guessing is 3/10000 = 0.0003, it seems low enough to be safe; it means you need to loose your card more than three thousand times (or loosing more than three thousand cards at the same time until there is a reasonable chance of loosing money.
What I really meant by "guessing" was breaking the PIN algorithm so that given any card you can immediately know the associated PIN. Therefore this document studies that possibility, analyzing the algorithm and proposing a method for the attack. Finally we give a tool which implements the attack and present results about the estimated chance to break the system. Note that as long as other banking security related algorithms (other PIN formats such as IBM PIN or card validation signatures such as CVV or CVC) are similar to VISA PIN, the same analysis can be done yielding nearly the same results and conclusions.
VISA PVV algorithm
One of the most common PIN algorithms is the VISA PIN Verification Value (PVV). The customer is given a PIN and a magnetic stripe card. Encoded in the magnetic stripe is a four digit number, called PVV. This number is a cryptographic signature of the PIN and other data related to the card. When a user enters his/her PIN the ATM reads the magnetic stripe, encrypts and sends all this information to a central computer. There a trial PVV is computed using the customer entered PIN and the card information with a cryptographic algorithm. The trial PVV is compared with the PVV stored in the card, if they match the central computer returns to the ATM authorization for the transaction. See in more detail.
The description of the PVV algorithm can be found in two documents linked in the previous page. In summary it consists in the encryption of a 8 byte (64 bit) string of data, called Transformed Security Parameter (TSP), with DES algorithm (DEA) in Electronic Code Book mode (ECB) using a secret 64 bit key. The PVV is derived from the output of the encryption process, which is a 8 byte string. The four digits of the PVV (from left to right) correspond to the first four decimal digits (from left to right) of the output from DES when considered as a 16 hexadecimal character (16 x 4 bit = 64 bit) string. If there are no four decimal digits among the 16 hexadecimal characters then the PVV is completed taken (from left to right) non decimal characters and decimalizing them by using the conversion A->0, B->1, C->2, D->3, E->4, F->5. Here is an example:
Output from DES: 0FAB9CDEFFE7DCBA
PVV: 0975
The strategy of avoiding decimalization by skipping characters until four decimal digits are found (which happens to be nearly all the times as we will see below) is very clever because it avoids an important bias in the distribution of digits which has been proven to be fatal for other systems, although the impact on this system would be much lower. See also a related problem not applying to VISA PVV.
The TSP, seen as a 16 hexadecimal character (64 bit) string, is formed (from left to right) with the 11 rightmost digits of the PAN (card number) excluding the last digit (check digit), one digit from 1 to 6 which selects the secret encrypting key and finally the four digits of the PIN. Here is an example:
PAN: 1234 5678 9012 3445
Key selector: 1
PIN: 2468
TSP: 5678901234412468
Obviously the problem of breaking VISA PIN consists in finding the secret encrypting key for DES. The method for that is to do a brute force search of the key space. Note that this is not the only method, one could try to find a weakness in DEA, many tried, but this old standard is still in wide use (now been replaced by AES and RSA, though). This demonstrates it is robust enough so that brute force is the only viable method (there are some better attacks but not practical in our case, for a summary see LASEC memo and for the dirty details see Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 and Heys 2001).
The key selector digit was very likely introduced to cover the possibility of a key compromise. In that case they just have to issue new cards using another key selector. Older cards can be substituted with new ones or simply the ATM can transparently write a new PVV (corresponding to the new key and keeping the same PIN) next time the customer uses his/her card. For the shake of security all users should be asked to change their PINs, however it would be embarrassing for the bank to explain the reason, so very likely they would not make such request.
Preparing the attack
A brute force attack consists in encrypting a TSP with known PVV using all possible encrypting keys and compare each obtained PVV with the known PVV. When a match is found we have a candidate key. But how many keys we have to try? As we said above the key is 64 bit long, this would mean we have to try 2^64 keys. However this is not true. Actually only 56 bits are effective in DES keys because one bit (the least significant) out of each octet was historically reserved as a checksum for the others; in practice those 8 bits (one for each of the 8 octets) are ignored.
Therefore the DES key space consists of 2^56 keys. If we try all these keys will we find one and only one match, corresponding to the bank secret key? Certainly not. We will obtain many matching keys. This is because the PVV is only a small part (one fourth) of the DES output. Furthermore the PVV is degenerated because some of the digits (those between 0 and 5 after the last, seen from left to right, digit between 6 and 9) may come from a decimal digit or from a decimalized hexadecimal digit of the DES output. Thus many keys will produce a DES output which yields to the same matching PVV.
Then what can we do to find the real key among those other false positive keys? Simply we have to encrypt a second different TSP, also with known PVV, but using only the candidate keys which gave a positive matching with the first TSP-PVV pair. However there is no guarantee we won't get again many false positives along with the true key. If so, we will need a third TSP-PVV pair, repeat the process and so on.
Before we start our attack we have to know how many TSP-PVV pairs we will need. For that we have to calculate the probability for a random DES output to yield a matching PVV just by chance. There are several ways to calculate this number and here I will use a simple approach easy to understand but which requires some background in mathematics of probability.