Offline PIN validation with DES4661658Abstract A method of offline personal authentication in a multi-terminal system uses a secret user PIN, a secret key and other nonsecret data stored on a customer memory card and a nonsecret validation value stored in each terminal connected in a network. The technique of "tree authentication" is used which employs an authentication tree with an authentication tree function comprising a one-way function. An authentication parameter is calculated as a function of a personal key and a user identifier read from the user's card and the PIN entered by the user. The calculated authentication parameter is mapped to a verification value using the one-way function to the root of the authentication tree. The verification value obtained by mapping the calculated authentication parameter is then compared with a global verification value stored at the terminal. If the comparison is favorable, the system is enabled for the user; otherwise, the user is rejected. Claims I claim: Description BACKGROUND OF THE INVENTION
______________________________________
level 3 XXXXXXXX
level 2 XXXX
level 1 XX
level 0 X
______________________________________
If the left branch is denoted by "0" and the right branch by "1", then the tree looks like this:
______________________________________
Index Position
000 001 010 011 100 101 110 111
______________________________________
level 3 01010101
level 2 0101
level 1 01
level 0 0
______________________________________
The "path" followed in the tree can be represented as a string of "1's" and "0's". For example, starting from the root, if we go up to a left branch, then to a right branch, and then to a right branch again, the path is given by the number 011. If, on the other hand, we go up to a right branch, and then up to a right branch again, and then up to a left branch, the path is given by the number 110. Thus, the numbers 000, 001, . . . , 111 describe the eight paths in this binary tree. It should be apparent that these path numbers also represent the index positions, in binary numbers, of the values at the highest level of the tree. The index position always starts from level zero. Now, it is assumed that the problem to be resolved is to calculate a single non-secret verification value V from a set of n predefined authentication parameters AP.sub.0, AP.sub.1, AP.sub.2, . . . , AP.sub.n. Suppose for the sake of this example that log.sub.2 (n)=20, i.e., that there are 2.sup.20 =1,058,576 customers. Note that one can always fill in the tree with dummy entries if need be; that is, where the number of customers is not equal to 2.sup.i for some integer i. The n values of AP are mapped to a single root value using a one-way function that involves log.sub.2 (n) iterations. At the first iteration, the n=1,048,576 values are mapped to 524,288 values, the second iteration maps 524,288 values to 262,144 values, and so on until the 20th iteration maps two values to one value. Each application of the one-way function maps two 56-bit values (denoted Y.sub.left and Y.sub.right) to a single 56-bit value denoted Y.sub.new as illustrated in FIG. 1. A suitable one-way function that maps Y.sub.left and Y.sub.right to Y.sub.new is given by Equation 3. Right56[Y.sub.left .sym.E.sub.Right56[Ci] (Y.sub.left)]=U Right56[Y.sub.right .sym.E.sub.U (Y.sub.right)]=Y.sub.new (3) where Ci is a 64-bit variable computed using Equation 4 given hereinafter. At the first iteration, Equation 3 is used to map AP.sub.0, AP.sub.1 and a unique codeword C to Y.sub.new ; i.e., Y.sub.left is AP.sub.0 and Y.sub.right is AP.sub.1. This output Y.sub.new may be denoted AP.sub.0,1. Then, AP.sub.2, AP.sub.3 and a different codeword C are mapped to AP.sub.2,3 using Equation 3, and so forth. At the second iteration, AP.sub.0,1, AP.sub.2,3 and yet a different codeword C are mapped to AP.sub.0,1,2,3 using Equation 3, and so forth. The operations are fairly simple and straightforward. In all, there are n-1 calculations involving Equation 3. The final 56-bit value so produced is stored in each EFT/POS terminal and is used as a global verification value V. In the example where n=2.sup.20, the 1,048,576 values of AP, namely AP.sub.0, AP.sub.1, . . . , AP.sub.1,048,575, are stored in a table designated Table 20, in that order. The 524,288 values AP.sub.0,1, AP.sub.2,3, . . . , AP.sub.524286,524287, which are produced at the first iteration in that order, are stored in a table at a next level designated Table 19; the 262,144 values AP.sub.0,1,2,3, AP.sub.4,5,6,7, . . . , AP.sub.262140,262141,262142,262143, which are produced at the second iteration in that order, are stored in a table at a next level designated Table 18; and so on. Thus, the values in Table 20 are processed sequentially using the mapping in Equation 3 to produce the values in Table 19, the values in Table 19 are processed sequentially also using the mapping in Equation 3 to produce the values in Table 18, and so on. In a simple example where n=3, only three tables would be required. The values AP.sub.0, AP.sub.1, . . . , AP.sub.7 would be stored in Table 3; the values AP.sub.0,1, AP.sub.2,3, AP.sub.4,5, and AP.sub.6,7 would be stored in the table at the next level, namely, Table 2; and the values AP.sub.0,1,2,3 and AP.sub.4,5,6,7 would be stored in the table at the next level, namely Table 1, as shown in FIG. 2. Each customer is issued a PIN and a bank card on which is recorded a user identifier ID, a unique secret personal key KP, and other information including information that allows a verification value V to be calculated from that customer's authentication parameter AP. The customer's AP value is a function of PIN, KP, ID, and KGb1 as described above, and is calculated via Equations 1 and 2. In the example given in FIG. 2 where n=3, the other information stored on the bank card necessary to allow a verification value V to be calculated would consist of a 56-bit value selected from each of the three tables, i.e. Table 1, Table 2 and Table 3, and a 3-bit index position of the customer's AP value in Table 3. The rule for determining which 56-bit values must be selected from Tables 1, 2 and 3 for storage on the bank card depends on the index position of AP in Table 3. If, for example, AP.sub.2 is the authentication parameter to be authenicated, then the 3-bit index position equals 010 in binary, and the values AP.sub.3, AP.sub.0,1, AP.sub.4,5,6,7, and 010, represent the necessary information that must be stored on the bank card to allow the verification value V to be calculated. Referring now to FIG. 3, there is a diagram illustrating the selected path for obtaining the root or verification value for this tree. The diagram shows the value of the index positions for Tables 1, 2 and 3 and the associated AP value at each such position in each table. Thus, for the given example, the starting index position is 010 and the value of AP is AP.sub.2. The path traced through the tree is represented by the AP values enclosed in triangles whereas the AP values stored on the bank card are enclosed in rectangles. The rule for selecting the three values AP.sub.3, AP.sub.0,1, and AP.sub.4,5,6,7 is as follows. Starting with the index position of AP.sub.2, i.e. 010, the rightmost bit is inverted and this 3-bit number 011 is used as the index position of the AP value selected from Table 3. This results in selecting AP.sub.3, since the index position of AP.sub.2 in Table 3 is just 011. For convenience, let the value AP.sub.3 selected from Table 3 be denoted by Y.sub.3 where the subscript on Y is the number of the table. The number 011 is now shifted one bit to the right, thus producing 01, and the rightmost bit is again inverted, and this 2-bit number 00 is used as the index position of the AP value selected from Table 2. This results in selecting AP.sub.0,1 since the index position of AP.sub.0,1 in Table 2 is just 00. For convenience, let the value AP.sub.0,1 selected from Table 2 be denoted by Y.sub.2. The number 00 is now shifted one more bit to the right, thus producing 0, and the rightmost bit is again inverted, and this 1-bit number 1 is used as the index position of the AP value selected from Table 1. This results in selecting AP.sub.4,5,6,7 since the index position of AP.sub.4,5,6,7 in Table 1 is just 1. For convenience, let the the value AP.sub.4,5,6,7 selected from Table 1 be denoted by Y.sub.1. Thus, the values Y.sub.3, Y.sub.2, Y.sub.1, and the index position 010 are the values which would be written on the bank card for the example where the associated AP value is AP.sub.2. In the case where n=20 described above, i.e. where 1,048,576 bank cards are issued to customers, each card would have stored on it the values Y.sub.20, Y.sub.19, . . . , Y.sub.1, and a 20-bit index position in Table 20 of the AP value to be authenticated. Thus, the amount of information stored on the bank card is variable and depends on the number of customer AP values to be authenticated and therefore on the size of the authentication tree so produced. Referring again to FIG. 3, the calculation of the verification value V from AP, Y.sub.3, Y.sub.2, Y.sub.1, and the index position number (010 in the example) is as follows. This is the calculation performed in the EFT/POS terminal to authenticate a cardholder. The information on the card is, of course, first read into the EFT/POS terminal. If the rightmost bit of the index position is 0, then Y.sub.new is calculated with Equation 3 using as inputs Y.sub.left =AP and Y.sub.right =Y.sub.3. This is the calculation performed in the present example, since the rightmost bit of 010 is 0. On the other hand, if the rightmost bit of the index position number is 1, then Y.sub.new is calculated with Equation 3 using as inputs Y.sub.left =Y.sub.3 and Y.sub.right =AP; that is, the assignment of values is reversed. Now the index position number is shifted one bit to the right, which in the example illustrated in FIG. 3, produces the value 01. If the rightmost bit of this shifted number is 0, then Y.sub.new is calculated with Equation 3 using as inputs Y.sub.left =Y.sub.old and Y.sub.right =Y.sub.2, where Y.sub.old is the value of Y.sub.new produced in the previous step. On the other hand, if the rightmost bit in the shifted number is 1, then Y.sub.new is calculated with Equation 3 using as inputs Y.sub.left =Y.sub.2 and Y.sub.right =Y.sub.old. This is the calculation performed in our present example, since the rightmost bit in the shifted number 01 is just 1. The shifted number is again shifted one bit to the right, which in the example illustrated in FIG. 3, produces the value 0. If the rightmost bit of the shifted number is 0, then Y.sub.new is calculated with Equation 3 using as inputs Y.sub.left =Y.sub.old and Y.sub.right =Y.sub.1, where Y.sub.old is again the value of Y.sub.new produced in the previous step. This is the calculation performed in our present example, since the rightmost bit in the shifted number is 0. On the other hand, if the rightmost bit of the shifted number is 1, then Y.sub.new is calculated with Equation 3 using as inputs Y.sub.left =Y.sub.1 and Y.sub.right =Y.sub.old. Thus, the index position number stored on the card defines how each value of Y.sub.i, also stored on the card, is to be used in the calculation of Y.sub.new using Equation 3; i.e., whether it is substituted for Y.sub.left or for Y.sub.right in Equation 3. Moreover, once this order of substitution has been determined, either AP or the value of Y.sub.new produced at the previous step is substituted for the other parameter Y.sub.left or Y.sub.right. The value of AP is used only at the first step in the calculation of V whereas a value of Y.sub.new is used in all subsequent steps in the calculation of V. The value of C in Equation 3 is derived from the index postion number stored on the bank card using the following algorithm. Let Q be a 64-bit constant and KA and KB two constant, nonsecret cryptographic keys. Q, KA and KB are stored in each EFT/POS terminal and are universal constants whose values are established by the card issuer. If X.sub.1, X.sub.2, X.sub.3, . . . , X.sub.m denotes the index position number on the card, represented in binary, then these m bits are used to calculate the following m values of C: C.sub.1, C.sub.2, . . . , C.sub.m, using Equation 4. ##EQU1## For example, if the index position number is 10110 01101 10001 11010, then the following 20 values of C are calculated and used with Equation 3 to calculate V: ##EQU2## Twenty encryptions are required to calculate the 20 values of C for a particular 20-bit index position number. C.sub.20 is used with Equation 3 to make the transition from level 20 to level 19 in the tree, C.sub.19 is used with Equation 3 to make the transition from level 19 to level 18 in the tree, and so forth, there being a different value of C used at each fork in the tree. The reason for using different values of C is because of security. If a constant value of C were used at each fork in the tree, then an adversary could launch a birthday type of attack in which a set of Y.sub.new values is calculated by chaining one value after the other until there is a match with one of the actual Y.sub.new values in the tree. By opening several accounts, an adversary could collect a fairly large set of such actual values and thus reduce his work factor by using the mentioned attack. However, by forcing different values of C, the attack is thwarted. For the authentication step at the EFT/POS terminal, assume that the information on the bank card is as follows:
______________________________________
ID User Identifier
______________________________________
KP Secret Personal Key 56 bits
IPN Nonsecret Index Position No.
20 bits
Y.sub.20, Y.sub.19, . . ., Y.sub.1
Nonsecret Data to Calculate Y
1120 bits
VS Verification Selection Number
______________________________________
The difference between secret and nonsecret with regard to card data refers to how that data is treated when it resides somewhere off the card. By definition, the card must be protected if any data stored on the card is defined as secret. Other nonsecret data on the card receives the same degree of protection as the secret data. It may be desirable to store a number of verification values and a positive file of AP values in each EFT/POS terminal and to authenticate a card-holder using one of these verification values which is selected on the basis of a verification selection number stored on the card-holder's card or to authenticate the card-holder on the basis of a positive file of AP values. To account for the possibility that some customers will lose their cards or a compromise of either their card or PIN may occur, which will require a new card with a new AP value to be reissued to the card-holder, it may be desirable to authenticate an AP value associated with a reissued card on the basis of a different verification value V. Each EFT/POS terminal therefore stores a value T, which is interpreted as follows. If the verification selection number VS is less than or equal to T, then the value of VS is used by the terminal to select the verification value V to be used to authenticate the card-holder's AP value. Assume that the EFT/POS terminal stores the following:
______________________________________
Q Nonsecret Constant 64 bits
KA Nonsecret Cryptographic Key
56 bits
KB Nonsecret Cryptographic Key
56 bits
V Verification Value 56 bits
KGbl Secret Global Cryptographic Key
56 bits
T Number of Verification Values Stored in Terminal
______________________________________
It should be noted that there may be multiple verification values depending on the particular implementation. The steps involved in the authentication process are illustrated in FIG. 4. First, the card-holder enters his or her PIN into the EFT/POS terminal. The card-holder also submits his or her bank card to the EFT/POS terminal as depicted in block 1. Then, in block 2, the terminal reads the quantities stored on the card. Before proceding with any calculations, a "hot list" is checked in block 3 to determine if the ID read from the card is invalid. In decision block 4, a determination is made as to whether the ID is valid, and if it is not, then the reject indicator is set in block 5. An ID is invalid if a value equal to the value of the ID is found in the "hot list". Otherwise, the process continues to block 6. At this point, the EPIN is calculated from the ID, PIN and secret KGb1 key using Equation 1. In addition AP is calculated from EPIN, KP and ID using Equation 2. A "hot list", which may be the same "hot list" mentioned above, is also checked to determine if the AP is invalid. The AP is invalid if a value equal to the value of AP is found in the "hot list". If the AP is invalid, then the reject indicator is set in block 5. Otherwise, the process continues to decision block 8 where a determination is made as to whether the verification selection number VS is greater than the value of T stored in the EFT/POS terminal. If it is, then the card-holder is authenticated on the basis of a positive file in block 9 instead of on the basis of a verification value V. Such a file can be implemented by storing in the positive file the values of ID and AP for each such user to be authenticated by the positive file. In decision block 10, a determination is made as to whether a positive authentication is made from the file, and if not, then a reject indicator is set in block 5. More particularly, the card-holder's ID is first used to access and obtain a corresponding AP value stored in the positive film, and the cardholder is then authenticated by comparing this AP of reference value for equality with the AP value calculated in block 6. Returning to block 8, if the verification selection number is less than or equal to T, then the constants C.sub.1, C.sub.2, . . . , C.sub.20 are calculated, in that order using Equation 4, from Q, KA, KB, and the index position number (IPN) read from the card, and these generated quantities are stored in a table and later accessed when calculating V. Once the constants C.sub.i have all been calculated, V is calculated from AP, Y.sub.20, Y.sub.19, . . . , Y.sub.1, C.sub.20, C.sub.19, . . . , C.sub.1, and the 20-bit index position number, represented by IPN=X.sub.1, X.sub.2, . . . , X.sub.20, using Equation 3 repeatedly, as follows: ##EQU3## The foregoing calculations are made in block 12. The verification selection number is decoded at block 13 to select a particular one of the T global reference values stored at the terminal. Then in decision block 14 a determination is made as to whether the calculated value of V is equal to the particular selected global reference value stored in the terminal. If it is not, then the reject indicator is set in block 5. Otherwise, the accept indicator is set in block 11. Returning briefly to decision block 13, by way of example, let T=2. Then if the verification selection number is 1, a first global reference value is used in making the determination to authenticate the user. However, if the verification selection number is 2, then a second global reference value is used. As already described with reference to decision block 8, if the verification selection number is greater than 2, the user is authenticated on the basis of a positive file in block 9. Obviously, the numbers chosen here are governed by practical considerations, and those skilled in the art will recognize that modifications can be made without departing from the spirit of the invention. Summarizing, the method according to the present invention has the following security properties: First, compromising a card does not compromise the PIN. Second, compromising the global secret key does not compromize the PIN nor does it allow someone to forge cards and defraud the system. The process of personal authentication is based on a nonsecret global value stored in each EFT/POS terminal. Added PIN protection is achieved through the use of the global secret key also stored in each EFT/POS terminal. Compromising this key does not by itself compromise PINs. The justification for employing a global secret key is that with short PINs, there is no way to maintain PIN secrecy if a user's card is compromised and the EFT/POS terminal stores only nonsecret quantities. Although a global secret key has a decided disadvantage, it is better to employ such a key when there is no other alternative to strengthen PIN secrecy, especially when it can be anticipated that many user cards will be lost and thus fall into the hands of potential adversaries. As long as the integrity of the global nonsecret verification value in the EFT/POS terminal is maintained, there is no global attack against the system. Even if the integrity of a terminal is compromised, then only that one terminal can be attacked. Since the global secret key does not lead to a global attack against the system, there is less motivation for an opponent to go after it. As described, a "hot list" is required with the procedure according to the invention. This is no different than what would be required with a public key solution or with a DES solution involving only a global secret key for user authentication. The "hot list" is needed because the bank has to have a way to invalidate an account. For example, an opponent could open an account under a phony name and then proceed to duplicate his card and sell the cards and PINs for profit. A user's PIN can be changed, but this involves reissuing the customer's bank card. Basically, when the PIN is changed, compensating changes must be made on the bank card which involves recalculation of an offset or certain nonsecret parameters on the card. If a user's card and PIN have been compromised, then a new card and PIN must be issued. In this case, an entry on the "Hot List" must be made to effectively invalidate the authentication information stored on that card and the user's PIN. This does not necessarily mean that the ID is invalidated. The method is such that a customer's assigned ID can remain the same even if a new card and PIN are issued, although it is more efficient if a new ID is issued. While the invention has been described in terms of a preferred embodiment in the environment of a banking multi-terminal network, those skilled in the art will recognize that the principles of the invention can be practiced in other environments where it is desired to provide for the offline personal authentication of users of a system. For example, the invention could be used in a security system that would allow access to secure areas only to users of the system who are properly authenticated at a terminal. The important feature of the invention is the use of an authentication tree with an authentication tree function comprising a one-way function.
|
Same subclass Same class Consider this |
||||||||||