1. Technical Field
The invention disclosed broadly relates to data processing systems and methods and more particularly relates to cryptographic systems and methods for use in data processing systems to enhance security.
2. Background Art
The following patents and patent applications are related to this invention and are incorporated herein by reference:
R. C. Merkle, "Method of Providing Digital Signatures," U.S. Pat. No. 4,309,569, issued Jan. 5, 1982.
R. C. Merkle, Secrecy, Authentication, and Public Key Systems, UMI Research Press, Ann Arbor, Mich., 1982.
R. C. Merkle, Secrecy, Authentication, and Public Key Systems, Technical Report No. 1979-1, Information Systems Laboratory, Stanford University, June 1979.
R. C. Merkle, Protocols for Public Key Cryptosystems, Technical Report, BNR, Palo Alto, Calif., January 1980.
R. C. Merkle, "Protocols for Public Key Cryptosystems," Proceedings of the 1980 Symposium on Security and Privacy, 122-134, Apr. 14-16, 1980.
S. M. Matyas, "Offline PIN Validation with DES," U.S. Pat. No. 4,661,658, issued Apr. 28, 1987, assigned to IBM Corporation and incorporated herein by reference.
B. Brachtl, et al., "Controlled Use of Cryptographic Keys Via Generating Stations Established Control Values," U.S. Pat. No. 4,850,017, issued Jul. 18, 1989, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors," U.S. Pat. No. 4,941,176, issued Jul. 10, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Data Cryptography Operations Using Control Vectors," U.S. Pat. No. 4,918,728, issued Apr. 17, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Personal Identification Number Processing Using Control Vectors," U.S. Pat. No. 4,924,514, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Extended Control Vectors," U.S. Pat. No. 4,924,515, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Key Management Using Control Vector Translation," U.S. Pat. No. 4,993,069, issued Feb. 12, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Key Management Using Programmable Control Vector Checking," U.S. Pat. No. 5,007,089, issued Apr. 9, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors with Multi-Path Checking," Ser. No. 07/596,637, filed Oct. 12, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Secure Cryptographic Operations Using Alternate Modes of Control Vector Enforcement," Ser. No. 07/574,012, filed Aug. 22, 1990, assigned to IBM Corporation and incorporated here by reference.
B. Brachtl, et al., "Data Authentication Using Modification Detection Codes Based on a Public One Way Encryption Function," U.S. Pat. No. 4,908,861, issued Mar. 13, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Method and Apparatus for Controlling the Use of a Public Key, Based on the Level of Import Integrity for the Key," Ser. No. 07/602,989, filed Oct. 24, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "A Hybrid Public Key Algorithm/Data Encryption Algorithm Key Distribution Method Based on Control Vectors," Ser. No. 07/748,407, filed Aug. 22, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Generating Public and Private Key Pairs Using a Passphrase," Ser. No. 07/766,533, filed Sep. 27, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Public Key Cryptosystem Key Management Based on Control Vectors," Ser. No. 07/766,260, filed Sep. 27, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Method to Establish and Enforce a Network Cryptographic Security Policy in a Public Key Cryptosystem," Ser. No. 07/786,227, filed Oct. 31, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Cryptographic Facility Environment Backup/Restore and Replication in a Public Key Cryptosystem," Ser. No. 07/786,237, filed Oct. 31, 1991, assigned to IBM Corporation and incorporated herein by reference.
The cryptographic architecture described in U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, 4,924,515, 4,993,069, and 5,007,089 and in patent applications Ser. No. 07/596,637, Ser. No. 07/574,012, Ser. No. 07/602,989, Ser. No. 07/748,407, Ser. No. 07/766,533, Ser. No. 07/766,260, Ser. No. 07/786,227, and Ser. No. 07/786,237 by S. M. Matyas et al. is based on associating with a cryptographic key, a control vector which provides the authorization for the uses of the key intended by the originator of the key. The cryptographic architecture described in the cited U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, 4,924,515, 4,993,069, and 5,007,089 and cited patent applications Ser. No. 07/596,637 and Ser. No. 07/574,012 by S. M. Matyas et al. is based on the Data Encryption Algorithm (DEA), see American National Standard X3.92-1981, Data Encryption Algorithm, American National Standards Institute, New York Dec. 31, 1981). The cryptographic architecture described in the cited patent applications Ser. No. 07/602,989, Ser. No. 07/748,407, Ser. No. 07/766,533, Ser. No. 07/766,260, Ser. No. 07/786,227, and Ser. No. 07/786,237, by S. M. Matyas et al. is based in addition on a public key algorithm (PKA), i.e., a combination of DEA and PKA. A cryptographic facility (CF) in the cryptographic architecture is described in the above cited patents by S. M. Matyas, et al. The CF is an instruction processor for a set of cryptographic instructions, implementing encryption methods and key generation methods. A memory in the cryptographic facility stores a set of internal cryptographic variables. Each cryptographic instruction is described in terms of a sequence of processing steps required to transform a set of input parameters to a set of output parameters. A cryptographic facility application program (CFAP) is also described in the referenced patents and patent applications, which defines an invocation method, as a calling sequence, for each cryptographic instruction consisting of an instruction mnemonic and an address with corresponding input and output parameters.
Public key encryption algorithms are described in a paper by W. Diffie and M. E. Hellman entitled "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the IEEE, Volume 67, No. 3, March 1979, pp. 397-427. Public key systems are based on dispensing with the secret key distribution channel, as long as the channel has a sufficient level of integrity. In a public key cryptographic system, two keys are used, one for enciphering and one for deciphering. Public key algorithm systems are designed so that it is easy to generate a random pair of inverse keys PU for enciphering and PR for deciphering and it is easy to operate with PU and PR, but is computationally infeasible to compute PR from PU. Each user generates a pair of inverse transforms, PU and PR. He keeps the deciphering transformation PR secret, and makes the enciphering transformation PU public by placing it in a public directory. Anyone can now encrypt messages and send them to the user, but no one else can decipher messages intended for him. It is possible, and often desirable, to encipher with PU and decipher with PR. For this reason, PU is usually referred to as a public key and PR is usually referred to as a private key.
A feature of public key cryptographic systems is the provision of a digital signature which uniquely identifies the sender of a message. If user A wishes to send a signed message M to user B, he operates on it with his private key PR to produce the signed message S. PR was used as A's deciphering key when privacy was desired, but it is now used as his "enciphering" key. When user B receives the message S, he can recover the message M by operating on the ciphertext S with A's public PU. By successfully decrypting A's message, the receiver B has conclusive proof it came from the sender A. Digital signatures can be produced either by decrypting the data to be signed with the private key, which works well when the data is short, or by first hashing the data with a strong one-way cryptographic function and decrypting the so-produced hashed value with the private key. Either method will work. Thus, in the above described method of DEA key distribution, B sends A two quantities: (1) the encrypted key, ePU(K), and (2) a digital signature e.g., of the form (a) dPR(ePU(K)) or dPR(hash(ePU(K))). A method for producing digital signatures based on the hash of the data to be signed is taught in co-pending patent application Ser. No. 07/748,407 ("A Hybrid Public Key Algorithm/Data Encryption Algorithm Key Distribution Method Based on Control Vectors"), cited in the Background Art. Examples of public key cryptography are provided in the following U.S. patents: U.S. Pat. No. 4,218,582 to Hellman, et al., "Public Key Cryptographic Apparatus and Method;" U.S. Pat. No. 4,200,770 to Hellman, et al., "Cryptographic Apparatus and Method;" and U.S. Pat. No. 4,405,829 to Rivest, et al., "Cryptographic Communications System and Method."
U.S. Pat. No. 4,309,569 to Merkle for "Method of Providing Digital Signatures" discloses a method of providing a digital signature for purposes of authentication of a message. This method utilizes an authentication tree function or a one-way function of a secret number. More specifically, the method according to Merkle provides a digital signature of the type which generates a secret number X.sub.i, where X.sub.i =x.sub.i1,x.sub.i2, . . . , x.sub.in computes Y.sub.i =F(X.sub.i) and transmits part of X.sub.i to the receiver as the digital signature. Merkle characterizes his invention as providing an authentication tree with an authentication tree function comprising a one-way functions of Y.sub.i. The root of the authentication tree and the authentication tree function are authenticated at the receiver. The Y.sub.i and the corresponding authentication path values of the authentication tree are transmitted from the transmitter to the receiver. Finally, the Y.sub.i are authenticated at the receiver by computing the authentication path of the authentication tree between the Y.sub.i and the rest of the authentication tree. U.S. Pat. No. 4,661,658 to Matyas for "Offline PIN Validtion with DES" discloses a method of offline personal authentication in a multiterminal system. The method makes use of a secret user PIN, a secret key and other nonsecret data stored on a customer memory card, and a nonsecret validation value and stored in each terminal connected in a network. The nonsecret validation value is just the root of an authentication tree calculated using a Merkle tree authentication function. In each case, U.S. Pat. No. 4,309,569 to Merkle and U.S. Pat. No. 4,661,658 to Matyas, the described inventions make use of a root of an authentication tree calculated on data characterized as a piece of information in a list of information or one item in a list of items that remain constant. Neither U.S. Pat. No. 4,309,569 to Merkle and U.S. Pat. No. 4,661,658 to Matyas teach how a tree authentication algorithm can be used to authenticate data in a dynamically and rapidly changing data file. In effect, U.S. Pat. No. 4,309,569 to Merkle and U.S. Pat. No. 4,661,658 to Matyas make use of a root of an authentication tree calculated on a list of information or items that remain constant, and hence these inventions are characterized by a root of an authentication tree that remains constant. However, there are data processing environments wherein it is desired to authenticate data elements in a data file that is continually updated and changed. Such processing environments are common in transaction based systems, where each processed transaction may cause a central data file to be updated. The present invention described a method for adapting the Merkle tree authentication algorithm so that it may be applied advantageously to solve the problem of authenticating data elements in a dynamically changing data file.
The subject invention describes a cryptographic method for implementing a particular kind of data file called an electronic purse. An electronic purse is a computer data file consisting of the account records of a group of member financial institutions. The member institutions communicate with the purse, located at a central facility, via an Electronic Funds Transfer network. Each purse record contains a member financial institution identifier, an account balance, a transaction sequence number, and other appropriate data not relevant to the present discussion. Account balances can range in the millions and billions of dollars. Hence, the integrity of the purse, and particularly the transaction-driven process of updating the purse, is of critical importance. The integrity of the purse is achieved through use of a tree authentication algorithm. The tree authentication algorithm makes use of modification detection codes calculated with a public one-way cryptographic function.
Since the purse may contain many records, it is impractical for these records to be stored within the secure boundary of a cryptographic facility (i.e., cryptographic hardware). However, when purse records are stored outside the CF, they are exposed to possible change or replacement by an insider adversary. Thus, a method is needed to preserve the integrity of the purse, i.e., an equivalent level of integrity should be achieved. For a purse with records R1, R2, . . . , Rn, the security objectives are these:
1. The CF must permit records in the purse to be authenticated independently. That is, the CF can authenticate record Ri without having access to other records in the purse. PA0 2. The CF must permit purse records to be updated without loss of integrity to the purse. Thus, if Ri' is an updated record produced from record Ri, the CF must recognize Ri' as a valid record and Ri as an invalid record. PA0 3. The CF must permit records in the purse to be updated independently. That is, the CF can update record Ri without having access to other records in the purse.
The security objectives preclude straightforward, or obvious authentication schemes based on message authentication codes calculated with the Data Encryption Algorithm or digital signatures calculated with a public key algorithm (e.g., using the RSA algorithm). To illustrate this, suppose the KD is a clear key, in the cryptographic facility, used to generate and verify message authentication codes. Suppose that the electronic purse consists of entries (R1, MAC1), (R2, MAC2), . . . , (Rn, MACn), where each record Ri has an associated MACi generated on Ri using the key KD. Each (Ri, MACi) is easily validated in the cryptographic facility using KD. But there is no effective way to update purse records using the straightforward method of calculating a new MAC on an updated record. This is so because the process of replacing purse record (Ri, MACi) with updated purse record (Ri', MACi') does not invalidate (Ri, MACi). Thus, an insider adversary with access to the purse and an old copy of (Ri, MACi) may subvert the purse by substituting (Ri, MACi) in place of (Ri', MACi'). The problem is not remedied by changing KD, since then MACs must be recalculated on all the purse records. This could be costly for large files.
The same problem occurs if digital signatures are used instead of message authentication codes, since changing the public and private key pair each time a record in the file is changed will likewise require the signature for record in the file to be re-calculated. This no advantage is gained from a public key algorithm over a private or secret key algorithm.