Method and apparatus for transaction and identity verification

• US 4,264,782 A
• Filed: 06/29/1979
• Issued: 04/28/1981
• Est. Priority Date: 06/29/1979
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Konheim, Alan G.
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US06/053,589
• Time in Patent Office: 669 Days
• Field of Search: 178/22, 340/149 R, 340/149 A, 340/152 R, 375/2, 364/200
• US Class Current: 705/75
• CPC Class Codes: G07B 17/00733 Cryptography or similar special procedures in a franking system
• CPC Class Codes: G07B 2017/00741 using specific cryptographic algorithms or functions
• CPC Class Codes: G07B 2017/00766 Digital signature, e.g. DSA, DSS, ECDSA, ESIGN
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method and apparatus whereby the senders and receivers of messages sent over a transmission system including a Host CPU may guarantee the integrity of the data content of the message and also the absolute identity of the sender. Each user of the system as well as the Host CPU contains an identical key-controlled block-cipher cryptographic device with data chaining for encrypting and decrypting messages as required, wherein each user has knowledge of only his own cryptographic key and wherein the Host CPU has access to the unique cryptographic keys of all users of the system stored in a high security storage area available only to said CPU. Stated very generally, the originator of a message A sends a message to a receiver B which includes a transaction or message portion X and a unique digital signature portion Y which is a function both of the message and the senders unique cryptographic key K_A. The receiver then communicates with the CPU for verification of the signature Y. The CPU accesses the sender'"'"'s key K_A from a secure memory and computes the digital signature Y utilizing the message portion X received from B and the key K_A. Upon a successful verification of the signatures by the CPU, the CPU notifies B via an additional message that the signature of A is valid based on the data content of the message and the key K_A. Based on the information received from the CPU, B may be certain that the signature and message originated with A and A may not later deny having sent the message as it would be virtually impossible for the signature to be forged since it is a complex function of the message content itself. A may also be assured that B cannot alter the message as the signature would no longer be valid.

According to other aspects of the invention the interrupting of communications between A and B by an eavesdropper and the subsequent sending of stale messages is prevented. As a still further feature of the invention, an eavesdropper is prevented from sending the "forged" approval from the CPU to the receiver B.

Claims

1. A method for effecting a high security transaction verification operation in a computer based communications system comprising a central Host CPU which includes a high security Verify Unit (VAULT) therein said system including at least two remotely located terminals selectively connectable to said Host CPU and wherein said Verify Unit and each of said terminals includes substantially identical key-controlled block cipher cryptographic devices with block chaining included therein said method comprising:

User A (originator) at a first terminal sending User B (receiver) at a second terminal a message M having a data portion (X) and a signature portion (Y) said signature portion being a block cipher function of A'"'"'s key K_A and the data portion (X), such that M=(X,Y);

User B on receipt of the message (X,Y) reencrypting same under his own key K_B to form a message U, sending said message U to the Host CPU together with the identities of User A and User B (originator, receiver), and requesting a verification operation from said Host CPU,

the Host CPU, after receiving said message, obtaining the keys K_A and K_B from a secure storage means and decrypting U under key K_B to obtain message U which presumptively comprises a message portion U₁ and a signature portion U₂ ;

the Host CPU then forming a signature utilizing U₁ as the data input and K_A as the key input to the cryptographic device and comparing this signature with the signature value U₂ received from User B, and

the Host CPU returning an accept/reject signal to User B depending upon whether or not the two signatures are identical.

2. A method as set forth in claim 1 wherein, after determining the validity of the received signature U₂ the Host CPU then generating a new signature V for the received message U which is a predetermined function of the key K_B and the previously decrypted message U depending upon the result of said signature comparison operation, and

sending the message V to User B;

User B on receipt of the message V computing a signature V'"'"' which is a predetermined function of his own key K_B and the message (X,Y) initially received from User A and comparing same with the message V for correspondence.

3. A transaction verification method as set forth in claim 2, including said Verify Unit utilizing the data ˜

U (the logical complement of U) for generating the signature message V when a valid signature from User A is to be acknowledged and utilizing the data U to produce the signature V when the signature for User A is found to be incorrect, and said User B utilizing the data ˜

(X,Y) (the logical complement of X,Y) to produce the signature message V'"'"' and comparing V'"'"' with the signature message V received from Host CPU.

4. A transaction verification method as set forth in claim 2 whereby the security of the individual user keys K_Z is maintained by storing all said individual user keys in the Host CPU under a master system key K_HV and accessing a particular encrypted key K_Z * belonging to an identified User Z from the Host CPU memory and decrypting same under said master key K_HV in the said Verify Unit.

5. A transaction verification method as set forth in claim 4 including utilizing a master system transmission key K_T for all communications between Users and between any User and the Host CPU subject to eavesdropping and wherein said transmission encryption operation is superimposed upon all messages between such system entities wherein all messages must first be encrypted under the system transmission key K_T before transmission and decrypted under said transmission key K_T upon receipt from another unit.

6. A method for transaction verification as set forth in claim 4 including forming all signatures in the present system by selecting as said signatures a predetermined final number of bytes of the block chained encryption of the full data input to said key controlled block-cipher cryptographic device with chaining wherein said signature is a direct function of and fully dependent upon the entire content of the data input to said cryptographic device.

7. A transaction verification method as set forth in claim 2 including the User A forming the initial message M utilizing the unique counter value from his own terminal (CT_orig) a unique counter value (CT_rec) obtained from the receiver'"'"'s (User B) terminal and, the current date and utilizing this information as a header on the message (X) and said User B, upon receiving said initial message, checking the date, and the value of the counter CT_rec for correspondence with a stored value which was previously sent User A upon the initial contact between User A and User B and aborting said transaction if either of said values fails to agree.

8. A transaction verification method for use in a computer based communication system comprising a central Host CPU which includes a high security Verify Unit therein said system including a plurality of remotely located terminals selectively connectable to each other and to said Host CPU via said communications system and wherein said Verify Unit and each of said terminals includes substantially identical key-controlled block-cipher cryptographic devices with block chaining, said method comprising User A (originator), at a first terminal sending User B (receiver) at a second terminal a message M having a data (X) portion and a signature portion (Y) said signature portion being a block-cipher function of User A'"'"'s key K_A and the data portion (X) such that:

M=(X,Y);

User B on receipt of said message M reencrypting said entire message M under his own key K_B to form a message U, sending said message U to the Host CPU together with the identities of User A and User B and requesting a verification operation from said Host CPU;

the Host CPU, upon receipt of said message from User B, requesting a verify operation from its associated Verify Unit and providing the message information U to said Verify Unit;

said Verify Unit obtaining the keys K_A and K_B from a secure storage means located in said Host CPU and decrypting U under key K_B to obtain message U which comprises a data portion U₁ and a signature portion U₂, the Verify Unit then forming a signature utilizing the data portion U₁ as the data input and the key K_A as the key input to its associated cryptographic device and comparing the signature so generated with the signature value U₂ received from User B, said Verify Unit after determining the validity of the received signature U₂ then generating a new signature V for the message U which signature is a predetermined function of the key K_B and the previously decrypted message U the particular function being dependent upon the result of said signature comparison operation and sending the message V to User B;

User B upon receipt of the message V computing a signature V'"'"' which is a predetermined function of his own key K_B and the message (X,Y) initially received from User A and comparing same with the message V for correspondence; and

wherein all signature generation operations in the previous enumerated signature generating steps comprise selecting as said signatures a predetermined final number of bytes of the block chained encryption of the full data input to said associated key-controlled block-cipher cryptographic devices with chaining wherein each said signature is a direct function of and fully dependent upon the entire data content supplied to said cryptographic device.

9. A transaction verification method as set forth in claim 8 wherein the individual User keys K_Z are stored in the Host CPU system memory in encrypted form under a Verify Unit master key K_HV and said individual keys are obtained from said Host CPU by the Verify Unit by accessing said Host at addresses derived from the identities of the Users A and B supplied to said Verify Unit, and decrypting said keys under the master key K_HV to obtain the original User'"'"'s keys K_A and K_B.

10. A transaction verification method as set forth in claim 9 including User B supplying to User A a counter value CT_rec when User B is first contacted for a transaction by User A, and User B concurrently storing in a local memory said counter value CT_rec, User A forming the initial message M utilizing the unique counter value from his own terminal CT_orig, the counter value CT_rec previously obtained from User B'"'"'s terminal and the current date as a header on the transaction message (X) and said User B, upon receiving said initial message M, checking the date and the value of the counter CT_rec for correspondence with said stored value and aborting such transaction if either the date or the counter values fail to agree.

11. A computer based communications system having a high security transaction verification feature incorporated therein, said system comprising a Host CPU which includes a high security Verify Unit therein, said system further including a plurality of remotely located terminals including means for selectively connecting each terminal to said Host CPU or to another terminal via the communications network associated therewith, said Verify Unit and each of said terminals including substantially identical key-controlled block-cipher cryptographic devices equipped with a block chaining feature, each terminal including means actuable when said terminal is used as an originating device (Terminal A) in a transaction to send a message M to another terminal acting as a receiver (Terminal B) said message M having a data portion (X) and a signature portion (Y), means for actuating the cryptographic device located in said terminal to form said signature (Y) as a block-cipher function of Terminal A'"'"'s key K_A and the data portion (X) such that M=(X,Y);

means in the receiving terminal (Terminal B) actuable on receipt of the message M from (Terminal A) for reencrypting said message under the terminal'"'"'s own key K_B to form a message U and means for sending said message U to the Host CPU together with the identities of the originating and receiving terminals (Terminal A and Terminal B) and means for requesting a verification operation from said Host CPU;

means in said Host CPU actuable upon the receipt of said message for obtaining the keys K_A and K_B from memory and for requesting a verify operation from the Verify Unit associated therewith;

means in said Verify Unit for decrypting the message U under terminal B'"'"'s key K_B to obtain a decrypted message U which comprises a message portion U₁ and a signature portion U₂, means in said Verify Unit for forming a signature utilizing U₁ as a data input and the originating terminal'"'"'s key K_A as the key input to the cryptographic device contained therein and means for comparing the signature so generated with the signature value U₂ received from terminal B;

means in said Verify Unit for returning an accept/reject signal to receiving terminal B depending upon whether the two signatures are identical.

12. A communication system as set forth in claim 11 wherein said means in said Verify Unit for returning an accept/reject signal to the receiving terminal B comprises means for generating a signature V including means for supplying the decrypted data message U, previously received from terminal B as the data input to the cryptographic device in the Verify Unit, and for supplying the key K_B as the key input to said cryptographic device and means for transmitting said derived signature V to the terminal B;

means in said terminal actuable on receipt of the signature V to generate a signature V'"'"' using the logical complement of the original message M as the data input to said terminal'"'"'s cryptographic device and the terminal B'"'"'s key K_B as the key input to said device and means for comparing the generated signature V'"'"' with the signature V received from the Verify Unit.

13. A communication system as set forth in claim 12 wherein said means for generating the signature V within the Verify Unit comprises means actuable in response to the comparison between the signatures U₂ and that generated from U₁ and K_A to supply the logical complement of U to the encryption device in the Verify Unit upon a successful comparison and for supplying the true value of U to said encryption device if said comparison is unsuccessful.

14. A communication system as set forth in claim 13 including key storage means in the Host CPU for storing all of the individual user keys K_Z in system memory in encrypted form under a master storage key K_HV which is resident in a high security storage means within the Verify Unit;

means for generating key storage addresses based on the identity of the particular terminals involved in a given transaction and for transmitting accessed, encrypted keys K_Z to the Verify Unit and means operative therein to decrypt said keys to obtain the actual keys for use in the transaction verification operations.

15. A communication system as set forth in claim 14 including transmission encryption means resident in all terminals of said system and in the Host CPU for encrypting all messages transmitted between terminals and between a terminal and the Host CPU under a master transmission key K_T and means for decrypting all received messages under said same encryption key K_T.

16. A communication system as set forth in claim 14 including means associated with the cryptographic device in said terminals and said Host CPU for forming all signatures utilized within the system by selecting a predetermined final number of bytes of the encrypted output of said cryptographic devices said output being derived from the entire data message input to said cryptographic device whereby said signatures are dependent upon the entire data message being encrypted.

17. A communication system as set forth in claim 12 including counter means resident in each terminal for producing a time dependent count value and means for including a predetermined current count value of the counters in both the originating and receiving terminals as a part of a message header which is incorporated in the data portion (X) of the message M transmitted from the originating terminal A to the receiving terminal B, means resident in each terminal for placing a quantity indicative of the date of a particular transaction as a portion of the header in any message M transmitted to another terminal, and means within each terminal for verifying the proper relationship of the count values and date for any received message wherein a transaction verification is to be requested.