Cryptographic system and method with key escrow feature

CRYPTOGRAPH1C SYSTEM AND METHOD WITH KEY ESCROW FEATURE

BACKGROUND OF THE INVENTION

This invention relates to cryptographie communications Systems. More particularly, this invention relates to the secure génération, certification, storage and distribution of cryptographie keys used in cryptographie communications Systems. Still more particularly, this invention relates to a system of cryptographie key escrow and public-key certificate management enforced by a self-certifying chip device.

The development and prolifération of sophisticated computer technology and distributed data processing systems has led to a rapid increase in the transfer of information in digital form. This information is used in financial and banking matters, electronic mail, electronic data inter15 change and other data processing Systems. Transmission of this information over unsecured or unprotected communication channels risks exposing the transmitted information to electronic eavesdropping or alteration. Cryptographie communications Systems preserve the privacy of these trans20 missions by preventing the monitoring by unauthorized parties of messages transmitted over an insecure channel. Cryptographie communications systems also ensure the integrity of these transmissions by preventing the alteration by unauthorized parties of information in messages transmitted over an insecure channel. The cryptographie communications Systems can further ensure the integrity and authenticity of the transmission by providing for recognizable, unforgeable and document-dependent digitized signatures that can prevent déniai by the sender of his own message.

Cryptographie systems involve the encoding or encrypting of digital data transmissions, including

010456 digitized voice or video transmissions, to render them incompréhensible by ail but the intended récipient. A plaintext message consisting of digitized sotmds, letters and/or numbers is encoded numerically and then encrypted using a complex mathematical algorithm that transforms the encoded message based on a given set of numbers or digits, also known as a cipher key. The cipher key is a sequence of data bits that may either be randomly chosen or hâve spécial mathematical properties, depending on the algorithm or cryptosystem used. Sophisticated cryptographie algorithms impiemented on computers can transfora and manipulate numbers that are hundreds or thousands of bits in length and can resist any known method of unauthorized decryption. There are two basic classes of cryptographie algorithms: symmetric key algorithms and asymmetric key algorithms.

Symmetric key algorithms use an identical cipher key for both encrypting by the sender of the communication and decrypting by the receiver of the communication. Symmetric key cryptosystems are built on the mutual trust of the two parties sharing the cipher key to use the cryptosystem to protect against distrusted third parties. The best known symmetric key algorithm is the National Data Encryption Standard (DES) algorithm first published by the National Institute of Standards and Technology. See Fédéral Register. Mar. 17, 1975, Vol. 40, No. 52 and Aug. 1, 1975, Vol. 40, No. 149. The sender cryptographie device uses the DES algorithm to encrypt the message when loaded with the cipher key (a DES cipher key is 56 bits long) for that session of communication (the session key). The récipient cryptographie device uses an inverse of the DES algorithm to decrypt the encrypted message when loaded with the same cipher key as was used for encryption. However, the adequacy of symmetric key cryptosystems in general has been questioned because of the need for the sender and the récipient to exchange the cipher key over a secure channel to which no unauthorized third party has access, in advance of the desired communications between the sender and οι 0 456 récipient. This process of first sequrely exchanging cipher keys and only then encrypting the communication is often slow and cumberspme, and is thus unworkable in situations requiring spontaneous or unsolicited communica5 tions, or in situations requiring communications between parties unfamiliar with each other. Moreover, interception of the cipher key by an unauthorized third party will enable that party to eavesdrop on both ends of the encrypted conversation.

The second class of cryptographie algorithme, asymmetric key algorithms, uses different cipher keys for encrypting and decrypting. In a cryptosystem using an asymmetric key algorithm, the user makes the encryption key public and keeps the decryption key private, and it is not feasible to dérivé the private decryption key from the public encryption key. Thus, anyone who knows the public key of a particular user could encipher a message to that user, whereas only the user who is the owner of the private key corresponding to that public key could decipher the message. This public/private key system was first proposée in Diffie and Hellman, New Directions in Cryptography,” IEEE Transactions on Information Theory, Nov. 1976, and in U.S. Patent No. 4,200,770 (Hellman et al.), both of which are hereby incorporated by reference.

An early type of asymmetric key algorithm allows secure communication over an insecure channel by interactive création by the communicating parties of a cipher key for that session of communication. Using the asymmetric key algorithm, two interacting users simultaneously and independently generate a secure cipher key that cannot be deduced by an eavesdropper and that is to be used symmetrically to encode that session of communications between the users. This interactive method of generating a secure cipher key was described by Diffie and Hellman in their 1976 paper. Under this prior art method, known as the Interactive Diffie-Hellman scheme, shown in FIG. 2, each of the two users A,B randomly chooses a secret number 21,22 and then computes an intermediate number 23,24 using

010456

K' two publicly-known numbers and the secret number 21,22 chosen by that user. Each user next transmits the intermediate number 23,24 to the other user and then computes the secret (symmetric) cipher key 25 using his own secret number 21,22 and the intermediate number 24,23 just received from the other user. The interactively generateà cipher key 25 is then used sfmmetrically by both users as a DES or other symmetric cipher key to encrypt and decrypt that session of communications over an otherwise insecure channel in the manner of symmetric key algorithm communications. This interactive process requires only a few seconds of real time, and including digitized Sound particular session can be ail digital communications, or video transmissions, in a encrypted merely by pushing a button at the outset of a session to initiate the interactive key exchange process. Because ail the numbers chosen in the Interactive Diffie-Hellman key génération scheme are very large, the computations are infeasible to invert and the secret cipher key cannot be computed by an 20 eavesdropper, thus preserving the privacy of the communication. Because the computations are infeasible to invert;, each user knows that any communication received using this algorithm was not altered and could have been sent only by the other user, thus preserving the integrity and authenticity of the communication. This interactive key exchange method, however, requires the parties to interact in real time in order to create the cipher key and may nor be useful for unsolicited communications or unfamiliar parties. In particular, the Interactive Diffie-Hellman key exchange scheme does not work for store-and-forward electronic-mail style messaging or for long-term storage of documents in an electronic data storage system, because the récipient is not on-line to negotiate the session key.

A modified, non-interactive form of the Diffie-Hellman scheme, known as Certified Diffie-Hellman, can be used when the communicating parties are not on-line together. The initial, certification step of the Certified Diffie-Hellman session key génération scheme is shown in FIG. 3. One

Û1Ü456 user, the recipient-to-be, randomly chooses a seciret number (his private key) and then computes an intermediate number 33 using two pufclicly-known numbers 32 and the secret number 31 chosen by that user· That user then sends proof of identification along with the intermediate number and the two public numbers, which numbers together form his public key 34, to a certifying authority that then issues a public key certificate 35 digitally signed 36 by the issuing certifying authority binding the user's identity te 10 the user's Diffie-Hellman public key information 34. The public key 34 publicized by that user remains the same until he décidés to rekey and choose another private key

31. Messaging using the Certified Diffie-Hellman method is shown in FIG. 4. In order to transmit a message to that user, a sending user first obtains the receiving user's certificate 35 and vérifiés the certifying authority's signature 36. The sender next computes the session key 42 for that communication session using the récipient's intermediate number 33 (from the récipient's certificare) 20 and the sender's own secret number 41 (nis private key) , which he chooses at random. The sender then encrypts a message 43 using the session key 42 and places his own intermediate number 40 unencrypted at the head of the communication. Upon receiving the communication, the récipient computes the session key 42 using the sender's unencrypted intermediate number 40 and his own secret number 31 (or private key), and then uses the session key 42 to decrypt the message 43. As with the Interactive Diffie-Hellman scheme, the session key generated in the

Certified Diffie-Hellman scheme is then used by both parties to encrypt and decrypt communications during that session over an otherwise insecure channel using a conventional symmetric algorithm, such as DES. The Certified Diffie-Hellman scheme, however, requires that a trusted entity or a certifying authority sign the receiving user's public key certificate so that a sending user can trust that the information contained within is correct. In addition, the private key randomly chosen by the sender,

010456 with which he computes both the session key and the intermediate number for that communication, must not be identical to the private key that is connected to th.e sender's own public key certificate; in order to avoid others learning his permanent private key numbers (corresponding to the public key numbers that hâve been certified) , the sender should keep them distinct from any ephemeral private keys or intermediate numbers that are generated only for spécifie messages.

Another asymmetric key algorithm, named the RSA algorithm after the inventors Rivest, Shamir and Adleman, is described in U.S. Patent, No. 4,405,829 (Rivest et al.), which is hereby incorporated by reference, and involves the difficulty of factoring a number that is the product of two large prime numbers. As with the Interactive DiffieHellman scheme, the RSA algorithm is relatively straightforward to compute but practically infeasible to invert. Thus, it is not feasible to dérivé the private key from the public key and, in this way, the privacy of the communication is preserved. Once a message is encrypted with the public key using the RSA algorithm, only the private key can decrypt it, and vice versa. As with the Certified Diffie-Hellman scheme, the RSA algorithm requires a trusted entity to certify and publicize the users' public keys. In contrast to both Diffie-Hellman schemes, however, the RSA algorithm does not itself generate a. session key to be used symmetrically by the parties. Instead, the public encryption key for a particular user directly encrypts communications to that user and that user's private decryption key decrypts those communications encrypted with the user's public key. In this way, the RSA algorithm is a pure asymmetric key algorithm.

However, because the RSA algorithm is complex and involves exponentiation of the message by very large numbers, encrypting or decrypting a message of even moderate length using the RSA algorithm requires a great deal of time. Thus, it is much simpler, faster and efficient to use the RSA asymmetric algorithm to transport

Û10456 a DES cipher key for use in a symmetric algorithm. This prior art mode of operation is known as RSA key transport and is shown in FIGS. 5 and 6. For example, referring to

FIG. 5, a user could generate a random DES key 51 and encrypt a message 52 with that DES key. The user would then encrypt the DES key 51 with an intended receiving user's public RSA encryption key 53 and transmit the DESencrypted message 54 along with the RSA-encrypted DES key 55 to the receiving user. After receiving the transmission, as shown in FIG. 6, the récipient decrypts the DES key 51 using his private RSA decryption key 56 and uses that DES key 51 to decrypt the message 52. Because the DES algorithm requires much less time and expense to compute than does the RSA algorithm, the symmetric DES key 15 is used to encrypt and decrypt the actual message, while the asymmetric RSA keys are used to encrypt and decrypt the symmetric DES key.

The RSA public/private key cryptosystem also provides for a digital signature that is both message dépendent 20 and signer dépendent, and can be used to certify that the received message was actually sent by the sender and that it was received unaltered. RSA digital signature is based on the additional property of RSA that, in addition to allowing the user's private key to decrypt only those 25 communications encrypted using that user's public key, permits a user's private key to encrypt messages that can be decrypted only by that user's public key. Because. only the user has the private key, use of the private key to encrypt allows for proof of origin that can be verified by 30 anyone with access to the user's public key. In practice, the sender first uses his private key to encode the message text into a signed message, which can be decrypted by anyone but could hâve corne only from the sender. If desired, the sender may then optionally use the récipient's 35 public encryption key to encipher the signed message to be transmitted. Upon receipt of the ciphertext, the récipient decrypts the ciphertext with his private decryption key, if necessary, and décodés the signed message with the sender's a

010456 public encryption key. Because only -the sender knows his unique private key, only the sender could hâve sent the particular signed message; the signature thus vérifiés the identity of the sender. Also, because the récipient 5 has only the sender's public key, the sender cannot claim that the récipient or an unauthorized third party altered or fabricated his message; the signature thus prevents répudiation of the message by the sender. Furthermore, because only the sender's private key transforms the original message and only the sender knows his unique private key, neither the récipient nor an unauthorized third party could hâve altered the message; the signature thus certifies the integrity of the message.

The RSA algorithm also provides for another type of digital signature that uses a hashing function to create a short message digest that is unique to each document.

FIGS. 7 and 8 show RSA signature création and RSA signature vérification, respectively, using a hashing function. A hashing function is another complex mathematical algorithm that is one-way, i.e. so that it is infeasible to reconstruct the document from the hash resuit, and is collision-free,” i.e. so that it is infeasible to produce another document that will hash to the same digest. As shown in FIG. 7, the sender first passes the message 72 through a hashing algorithm 73 to produce the message digest 74 and then encrypts the digest with his RSA private key 75, forming a compact digital signature 76 that is attached to the message 72. After receiving the transmission of the message 72 and the message digest 76, as shown in FIG. 8, the récipient decrypts the sender's RSA encrypted message digest 76 (the digital signature) using the sender's RSA public key 77. The récipient also uses the same hashing algorithm 73 to produce a message digest 74 from the received message. The two message dlgests resulting from the two transformations performed by the récipient should be identical, thus verifying that the message was signed by the sender.

Û 1 Ü 456

Another system of digital signature, called DSA for Digital Signature Algorithm, may also be used for· seruder vérification. The DSA, Algorithm was disclosed in U.S. Patent Application Serial No. 07/738,431, which is hereby incorporated by reference in its entirety. The DSA Algorithm has properties that are similar to those of the RSA signature algorithm in that the sender passes the message through a hashing algorithm to produce a message digest and then encrypts or signs the message digest using 10 his private key; the récipient vérifiés the encrypted digest using the sender's public key. However, unlike the RSA signature algorithm that returns the original message digest when the récipient decrypts the signature block, the DSA vérification algorithm results only in a positive confirmation of the validity of the signature; communications encrypted using an intended récipient''s public key cannot later be recovered by decryption with the récipient's corresponding private key. For this reason, the DSA algorithm may be used quite capably for digital signatures, but not for key transport or for direct message encryption.

In order for the public/private key system to operate efficiently, users must trust a centralized key certifying authority to be responsible for publicizing and updacing a 25 directory of public encryption keys. The key certifying authority must be trusted by ail users, both senders and récipients, to distribute the correct public keys for ail users so that no messages are transmitted to unintended récipients. To this end, as discussed above and elàborated 30 below, the certifying authority would distribute each user's name and public encryption key information, and would affix its own digital signature to the distributed information in order to certify the correctness of the information. However, when more than one entity, or a hierarchy of entities, is involved in the certification process, there are several different méthodologies or trust models for determining how a user will process the certificates. The three main models are (1) a pure

010456 hierarchical model, (2) a model using-cross-certification between multiple hiérarchies, and (3) a local trust model. These models are described in detail in the standards document American National Standard X9.30, Public Key Cryptography Using Irréversible Algorithms for the Financial Services Industry: Part 3: Certificate Management for DSA (American Bankers Assn., Washington, D.C., 1992), which is hereby incorporated by reference in its entirety. Although there is not yet a general consensus as to which of the above-mentioned trust models is best, it is assumed throughout this disclosure that an appropriate, generally accepted certification trust 'model will be established and adhered to whenever certificates issued by more than one entity are involved.

The public/private key system described above takes into account the privacy interests of the users who wish to transmit and receive communications privately. In addition, however, there are also the law enforcement and national security interests of governments to be considered. The ability of the government to monitor or eavesdrop on otherwise private electronic transmissions for law enforcement and national security purposes must be preserved so that suspected criminals, terrorists and foreign spies are not permitted to conspire beyond the reach of the law. Whereas téléphoné communications can be monitored through wiretapping, cryptographie algorithms make the enciphered data unable to be deciphered even by powerful code-breaking computers. The increase in the volume and percentage of digital and digitized transmissions encrypted with advanced algorithms will, therefore, serve to frustrate and thwart the lawful government electronic surveillance of these communications, especially if cryptographie devices are widely implemented in téléphonés, computers, facsimile machines and ail other data processing equipment.

One way to enable the government or other authorized investigators to monitor communications of suspected criminals is to require ail users of cryptographie û 1 Ο 456 communications to escrow their private decryption. keys with either a private authority or the government,. i.e- allow either the private authority or the governnent ta be the trusted custodian of the users' private decrypticm keys.

When necessary for surveillance, the government then will hâve access to or will be able to gain access to the private keys in order to monitor ail encrypted communications. This method, however, is unworkable because it contains insufficient safeguards against abuse by the government of the private decryption keys and against possible leaking of the private decryption keys to unauthorized third parties either by theft fron the. government or the private authority or by corruption of government or private authority personnel.

Another method of escrowing private decryption keys to preserve both user privacy interests and law enfercernent security interests is by using a system such as uhe method described in Pair Public Key Cryptosystens, proposed by Silvio Micali at CRYPTO 92 in March 1993 and pubiished by the Laboratory for Computer Science of the Massachusetts Institute of Technology on October 13, 1993, and in ü.S. Patent No. 5,276,737, both of which are hereby incorporated by reference. By this method, shown in FIGS. 9-11, a user who wishes to certify his public key for encryption purposes must escrow his private key in the following manner. As shown in FIG 9, the user first breaks his private key 91 into several “pièces 92, each of which can be individually verified 90 to be a valid part cf the complété private key 91. The private key can be reconstructed only with knowledge of ail the pièces or some specified number of them. The user then sends 93 each piece to a different escrow agent or agency 94, who, as shown in FIG. 10, vérifiés 95 the piece as a correct part of the private key 91 using a spécial algorithm and communicates this vérification 96 to a master escrow center. Referring to FIG. 11, after receiving vérification

96,97 that each piece of the private key is correct, the master escrow center can then issue a certificaue 9S for

010456 the user's public key 99, allowing itsto be used in a privacy system with the assurance that, if need be and pursuant only to a warrant or court order, law enforcement agencies will be able to obtain the secret pièces of the private key from the user's chosen escrow agents, recombine them and monitor the communications of that user. By this system, users can be assured of the privacy of their encrypted transmissions, and government can be assured of its ability to gain access to encrypted transmissions upon a showing of need. Because no one entity normally ever has access to the complété private key and because the user chooses entities that he trusts, the chances of unlawful or corrupt actions are greatly reduced. Also, because a wider range of entities would be eligible as escrow agents, the chances of simultaneously compromising ail the escrow agents, and thereby disrupting ail trusted commerce, is even further reduced.

The master escrow center, as a trusted authority certifying the authenticity of the user's public key, periodically issues a publicly-available certificate attesting or notarizing the connection between the public encryption key and its owner's identifying information. The certificate of authenticity assures the sender that transmissions to that named public key user will in fact be received and read only by the intended récipient. The certificate is usually in an internationally recognized electronic format, such as the one specified in CCITT Recommendation X.509 and issued as an international standard by the International Standards Organization (ISO). An example of a public encryption key escrow certificate format is shown in FIG. 12. The certificate contains, among other things, the name of the organization or key management center that created the certificate (the issuer) 121, the owner's public key 122, the owner's identifying information 126, a certificate serial number 123, and validity starting and ending dates 124. The issuer's digital signature 125 seals the certificate and prevents its alteration.

B

Q1ü 456

The U.S. government, however, has proposed as a government (and possible industry) standard another method to enable it to escrow .private decryption keys and to monitor communications. The U.S. government has developed a microcircuit, called the Clipper chip, that can be built into government and comnercially-produced téléphonés and computer devices. The Clipper chip is a low-cost chip that may be used for bulk encryption and key management;

the Capstone chip is a more advanced version of the Clipper chip that adds digital signature and message digest capabilities. Like other encryption Systems, the Clipper chip uses a symmetric encryption algorithm, albeit a classified algorithm called Skipjack, that scrambles téléphoné and digital computer data communications in a manner similar to DES, but using an 80-bit key. Each Clipper chip has a unique serial number, a Clipper family key common to ail Clipper chips and its own symmetric private device key that will be needed by authorized government agencies in order to décodé messages encoded by a device containing the chip. When the device containing the chip is manufactured, the unique private device key will be split into two components (called key splits) and deposited separately with two key escrow data bases or agencies that will be established within the government.

Law enforcement agents can gain access to these private device keys by obtaining a warrant or other legal authorization to wiretap or monitor the communications and by presenting the warrant to the two escrow agencies.

When users of Clipper chip devices wish to communicate, they first agréé on a symmetric session key with which to encrypt the communications. Any method of deriving the symmetric session key, such as Interactive Diffie-Hellman key dérivation process, and any method of transporting the DES session key between users, such as RSA transport, may be used. At the start of each communication, each user sends to the other a Law Enforcement Access Field (LEAF) that contains enough information to allow law enforcement agents to wiretap or monitor the communication.

U

010456

The believed format of the Clipper LEAF is shown in FIG. 13 (note that because the précisé details of the LEAF format, création and vérification are currently classified secret by the U.S. government, this discussion and FIG. 13 are both somewhat spéculative) . To form the LEAF, the session key is first encrypted using the private device key; then the device-key-encrypted session key, the sender device⁷s serial number and a checksum (a verifying value) of the original unencrypted session key are together encrypted with the Clipper family key to complété the LEAF. The message is then encrypted using the chosen session key. The session-key-encrypted message and the family-keyencrypted LEAF are together transmitted to the récipient. Upon receiving the communication, the receiving user first loads the received LEAF into his Clipper chip in order to check whether the LEAF is valid and whether the session key encrypted within the LEAF matches the session key previously received. If the LEAF is valid, the Clipper chip will decrypt the message with the chosen session key that was previously received.

A law enforcement agent lawfully wiretapping or monitoring the communication, however, does not know the session key and thus must first decrypt the LEAF in order to obtain the session key. The agent intercepts the desired LEAF, decrypts it using the Clipper family key and then présents the chip serial number from the LEAF and a court-ordered warrant or other legal authorization to the two government escrow agents, receiving in return the two key splits of the wire-tapped user's private device key. The agent combines the two escrowed device key components and uses the resulting device key to decrypt the devicekey-encrypted session key from the LEAF. The session key can then be used to decrypt the actual messages from the communications. The requirement that the sender and récipient each create a LEAF and validate the other*s LEAF insures that law enforcement agents will hâve a reasonable chance at intercepting the LEAF, since each LEAF is expected to pass between the users over the same communica15

Û i ü 4 5 6 tions medium. Further, it allows law enfcrcement to selectively monitor only one suspected user by decrypxing the LEAF generated by that user, regardless of wriich user originated the communication.

Unfortunately, there are many technical proviens with the government's Clipper chip proposai, mcstHy sxemmizig from the fact that the private keys to be esxrowed are permanently embedded in the Clipper chips during manufacture. Because the private encryption key fer a particular device is burned into the chip and cannot be changed, the chip and probably the entire device that contains it must be discarded if compromised. It is préférable for the user of a particular device to be able to rekey, reescrcw and recertify the device at will if compromise is suspected or at regular intervals to avoid potential compromise. In addition to the inability of the user to rekey and reescrow, the user of the Clipper device has no ohoice of the number or the identities of the key escrow agents employed by the government to safeguard his private key. Instead, the private key splits are deposited in two escrow data bases or agencies established by the gcvernnnent. Users may not trust the Clipper chip devices due to the risk that the government may hâve complété access to any transmission or transaction through the device, access that could be abused or corrupted. Users may also desire that their keys be escrowed with more trustées than the gevernment provides, in order that their private keys will be more secure. If the concept of key escrow is te hâve significance, each user must be able to choose his ovn trustées with whom to escrow his private keys, based upon the level of trust desired.

Also, it is believed that the government Clipper system allows users to communicate only symmetrically and in real time, and does not provide any direct support for store-and-forward electronic-mail type messaging. Prior to encrypting communications, the sender and récipient must first agréé on a symmetric session key with which to encrypt the communications. Typically, this key exchange

U

010456 is done using the Interactive Diff ie-Jîellman scheme, the only key exchange method believed to be supported by the Clipper chip. Thus, unless they wish to arrange their own key management system, users are restricted to simultaneous, interactive communications, such as real-time voice or facsimile communications. In order to use storeand-forward electronic-mail type messaging, however, a user must be able to access the intended récipient's public key, such as by using a Certified Diffie-Hellman or a certified 10 RSA key transport scheme, even if the intended récipient is not available for an interactive on-line communication. Because it is believed that the government's Clipper system does not facilitate this, store-and-forward messaging is difficult. The government's proposed standard system thus 15 may tend to limit the communications capabilities of users to on-line interaction.

Moreover, under the government system, the users' employers hâve no access to the encrypted-data or transmissions of their employées. Employers, on whose behalf the 20 employées are developing, communicating or transmitting confidential or proprietary data, must retain the right to gain access to their employées' data or transmissions. Many situations could arise wherein encrypted information would be available only to the spécifie employées directly 25 engaged in using the cryptographie Systems and not to the management or boards of directors who are responsible for those employées and who own the corporate data resources. By encrypting data or communications, employées could develop or appropriate for themselves new programs, pro30 ducts and technologies or could conduct illégal activities and transactions, ail without their employers' knowledge. Also, movement or reorganization of staff and changes of storage facilities could resuit in the loss of massive amounts of information that was important enough at the

3.5 time of encryption to be encrypted. See Donn B. Parker, Crypto and Avoidance of Business Information Anarchy (Invited speaker présentation at First Annual AC Conférence on Computer and Communication Security, November 3-5, 1993,

1T

UίÜ456

Reston, VA), which is hereby incorporated by reference. Aside from the originator of the data or the sender of the transmissions, the Clipper chip allows only the government to hâve access to the transmissions. Although employers could seek a court-issued warrant in order to monitor their employées' communications, employers may wish to monitor their internai officers in a more discreet fashion than by initiating a fédéral investigation any time suspicion is aroused.

Furthermore, mandating a classified algorithm that is embedded in the chip and thus available only in hardware and only from government-authorized chip manufacturers injects the government into the rapidly changing and highly compétitive market for communications and computer hardware. A government agency or a government-authorized manufacturer may be unable or unwilling to design and market advanced devices and products specially tailored for partîcular companies as would a private manufacturer. If the government authorizes only certain vendors to manufacture the chips having the classified algorithm, compétition will be reduced and the technology will be prevented from being incorporated into other products. Additionally, because the details of the Skipjack algorithm hâve not been made public, suspicion has arisen as to whether the algorithm could be insecure, due either to an oversight by its designers or to the deliberate introduction by the government of a trap door. An important value of cryptosystem design is that the privacy and security of the encrypted messages should dépend on the secrecy of the relevant key values, not on the secrecy of the system's details.

It is, therefore, désirable to provide a commercial key escrow system that uses published algorithme, opérâtes in a manner that inspires the users' trust and confidence, and solves the problems posed by national security and law enforcement demands.

οl0456

It is also désirable to provide a commercial key escrow system that uses private keys that may be changed by the user at will or at regular intervals.

It is further désirable to provide a commercial key escrow system that allows the user to choose the key escrow agents to safeguard his private key or the separate pièces of his private key.

It is still further désirable to provide a commercial key escrow system that contains safeguards against unrestricted government access, yet allows access by the employers of the users or by the countries of which .the foreign users are citizens.

It is also désirable to provide a commercial key escrow system that offers an alternative to the U.S. Government's proposed Clipper chip system.

SUMMARY OF THE INVENTION

It is one object of this invention to provide a commercial key escrow system that uses published algorithms, opérâtes in a manner that inspires the users' trust and confidence, and solves the problems posed by national security and law enforcement demands.

It is another object of this invention to provide a commercial key escrow system that uses private keys that may be changed by the user at will or at regular intervals.

It is a further object of this invention to provide a commercial key escrow system that allows the user to choose the key escrow agents to safeguard his private key or the separate pièces of his private key.

It is still a further object of this invention provide a commercial key escrow system that contains safeguards against unrestricted government access, yet allows access by the employers of the users or by the countries of which the foreign users are citizens.

ο 1ϋ 456

It is yet another object of this invention to provide a commercial key escrow system that offers an alternative to the U.S. Governmentis proposed Clipper chip system.

These and other objects of the invention are accomplished in accordance with the principles of the invention by providing a cryptographie key escrow system that uses a method, such as the Micali Fair escrow method, for verifiably splitting users' private encryption keys into components and for sending those components to trusted agents chosen by the particular users, and by providing a system that uses modem public key certificate management, enforced by a chip device that also self-certifies. In a preferred embodiment of this invention, the new chip encrypts or decrypts only if certain conditions are met, namely, (1) if a valid sender certificate and a valid récipient certificate are input, where valid means that the particular user's private decryption key is provably escrowed with a specified number· of escrow agents and that the master escrow center is registered and certified by the chip manufacturer, and (2) if a valid Message Control Header is generated by the sender and validated by the récipient, thereby giving authorized investigators sufficient information with which to request and obtain the escrowed keys. Because this invention relies upon a system of certificate management, it can be made very flexible and independent of location and time, unlike purely on-line Systems. The methods for escrowing a private decryption key and receiving an escrow certificate are also applied herein to a more generalized case of registering a trusted device with a trusted third party and receiving authorization from that party enabling the device to communicate with other trusted devices.

A further preferred embodiment of this invention provides a method for generating verifiably trusted communications among a plurality of users, comprising the steps of escrowing at a trusted escrow center a plurality of asymmetric cryptographie keys to be used by a plurality of users; verifying each of said plurality of keys at the

01Ü456 escrow center; certifying the authorization of each of said plurality of keys upon vérification; and initiating a communication from each of said plurality of users using a respective one of said plurality of keys contingent upon said certification. Further embodiments of this invention provide for decoding of communications by authorized law enforcement agents, based upon use of the Message Control Header included with each communication, using a spécial law enforcement décoder box and auditing of the law enforcement wiretaps to prevent abuse by law enforcement and other officiais. Further preferred embodiments provide for rekeying and upgrading of device firmware using*a certificate system, and encryption of stream-oriented data.

BRIEF DESCRIPTION OF THE DRAWINGS

The above and other objects and advantages of the invention will be apparent upon considération of the following detailed description, taken in conjunction with the accompanying drawings, in which the reference characters refer to like parts throughout and in which:

FIGS. IA - IG are lists of symbols and abbreviations that are used in the figures of this invention;

FIG. 2 is a flowchart showing the steps of the prior art Interactive Diffie-Hellman key dérivation method;

FIG. 3 is a flowchart showing the steps of the certification portion of the prior art Certified DiffieHellman method;

FIG. 4 is a flowchart showing the steps of the messaging portion of the prior art Certified Diffie-Hellman method;

FIG. 5 is a flowchart showing the steps of encryption using the prior art RSA key transport method;

FIG. 6 is a flowchart showing the steps of decryption using the prior art RSA key transport method;

FIG. 7 is a flowchart showing the steps of signature création using the prior art RSA method;

01Ù456

FIG. 8 is a flowchart showing the steps of signature vérification using the prior art RSA method;

FIGS. 9-11 are fldWcharts that together show the steps of the prior art Micali key escrow process;

FIG. 12 is an example of the format for a prior art public encryption key escrow certificate;

FIG. 13 is an example of the believed format of the Clipper device Law Enforcement Access Field (LEAF);

FIG. 14 is an example of the format for a device certificate issued by the manufacturers of the device of the présent invention;

FIG. 15 is a flowchart showing the steps of a method of verifiably escrowing a key with only one escrow agent;

FIG. 16 is a flowchart showing the steps of a method of verifiably escrowing a key, based on the trusted device alone;

FIG. 17 is a flowchart showing the steps of a method of sending an encrypted message with a Message Control Header (MCH);

FIG. 18 is an example of a MCH in RSA key transport format;

FIG. 19 is a flowchart showing the steps of a method of receiving an encrypted message with a MCH;

FIG. 20 is an example of a MCH décoder box and a flowchart for its process flow;

FIG. 21 is an example of a self-certifying trusted timestamp device;

FIG. 22 is an example of the format for a device owner certificate issued by the manufacturer of the device of the présent invention;

FIG. 23 is a flowchart showing the steps of a method of re-escrowing a key (rekeying) by the owner of the device of the présent invention; and

01Ü456

FIG. 24 is a flowchart showing the steps of a method for registration of the trusted device of the présent invention with a trusted third party.

DETAILED DESCRIPTION OF THE INVENTION

Public key cryptosystems, including the use of digital signatures, can potentially be the cornerstone of the création of national, or even global, paperless electronic document Systems. Use of these Systems will hâve enormous commercial significance in terms of costs savings. The critical element in the development and widespread acceptance of these Systems is the reliance placed upon the underlying cryptosystems and the digital signatures by governments, banks, corporations and other users, including individual users. Reliance on these Systems should arise not from trust by each user of its own internai system or of other users, but rather from trust by each user of the public key cryptosystem and of the certification mechanisms it provides. The commercial cryptosystem of the présent invention satisfies these concerns by using self-certifying and, therefore, trusted, encryption devices as the impartial arbiters of trust.

In a preferred embodiment of the présent invention, the tamper-resistant chip, or a tamper-resistant trusted device containing the chip, that perforas the encryption, decryption and digital signature is embedded with a nonmodifiable public/private signature key pair unique to that chip and with a manufacturer's certificate. The embedded manufacturer's certificate enables the device containing the chip (a) to digitally sign documents and communications (data structures) using its own private device signature key proving that they uniquely originated from that device and (b) to prove by appending the manufacturer' s certificate to documents and communications that those data structures can be trusted because the originating device is one of known and trusted type and is made by that trusted manufacturer. The manufacturer's certificate in effect says, The device whose private key ο 1 0 456 matches the public key certified herein is of type XXX. Signed, Manufacturer. Because the private signature key is embedded in a tamper-resistant manner and because the manufacturer is trusted, documents and communications issued by the device and signed using the private signature key will also be trusted.

A preferred embodiment of the présent invention contains eight major phases of use: (1) création or manufacture of the chips contained in the device, (2) registration of the device's encryption key with escrow agents, (3) normal encryption and decryption of user messages, (4) decoding of communications by authcrizeà law enforcement agents, (5) rekeying and upgrading or the device by the owner or employer, (6) auditing of law enforcement wiretaps, (7) encryption of stream-oriented data, and (8) national security safeguards.

Manufacture of the Trusted Device

Manufacture of trusted devices of the présent invention is based on the presence of the following general features:

(1) An embedded microprocessor (or microcontroller), a miniature computer that médiates ail outside access and perforas various computational and programming operations;

(2) An optional cryptographie coprocessor, which can perfora standard mathematical encrypting and decrypting operations at much higher speed than can a general purpose microprocessor and which will preferably contain a hardware noise source, such as a diode noise source, to assist in the génération of certifiably random numbers as needed for cryptographie key génération;

(3) An input-output interface or subsystem to assist in handling the flow of data and commands to and fron the microprocessor, which may include a status display or monitor; and

0t0456 (4) A memory subsystem that may^potentially employ several types of memory storage technology, each having a different characteristics of permanence and accessibility, such as (a) Read Only Memory (“ROM) that can contain. permanent and unchangeable programs and data, (b) Electrically Erasable Programmable Read Only Memory (“EEPROM”) or FLASH” memory, that can contain semipermanent programs and data, i.e. they can be changed but nevertheless are not lost when device power is lost or shut off, and (c) Random Access Memory (”RAM”), which can be used for temporary calculations and temporary data storage but is lost when power is shut off.

The entire device is designed and manufactured in such a way that ail its éléments, including especially the permanent and semi-permanent memory areas, are shielced from tampering that might reveal their contents or alter their modes of operation. One way to shield the device éléments from tampering is through the use of spécial coatings that are difficult to remove without destroying the information that underlies the coatings. In addition, there are other features that can cause the memory to be erased if any alteration to the physical enclosure of any of the memory areas is attempted or if suspicious actions that may signal tampering attempts, such as cooling the device to abnormally low températures in an attempt to deactivate and defeat the device's internai>defense mechanisms, occur. Some of these protective features may require a constant source of battery power, such that the device can take electrical actions to delete important data if tampering is suspected. The présent invention does not specify any particular preferred method of making the devices tamper-resistant, but rather relies on existing or future technologies that may be or may become generally regarded as providing an acceptable degree of protection from unauthorized disclosure or modification of the data contained in the devices. A device with such characteristics is sometimes referred to as a tamper-resistant secure module (TRSM), of which a current example is the Clipper/3

010456

Capstone device, discussed earlier, cpmmercially avaiiable from Mykotronx, Inc.

The manufacturer of the chips may be any of the many major computer microprocessor chip manufacturers. The manufacturer should preferably be one who is known to the cryptographie industry and is trusted with respect to chip quality and security and the integrity of its manufacturing process.

The chips manufactured. in order to be used in an embodiment of this invention would include the following capabilities. The chip would first include an embedded device public/private key pair for device signatures to be issued by the device, where the private signature key is non-readable and tamper-resistant. The cryptographie signature keys may be of any acceptable cryptographie type, such as RSA. However, because RSA has both encryption and signature capabilities and because it is désirable to isolate the signature and encryption processes, the cryptographie signature key should preferably be DSA. The chip would also include an embedded and tamper-resistant manufacturer's certificate for the device signature key, an example of the format for which is shown in FIG. 14. The device containing the chip can append this certificate to its signatures in order to prove that the signatures originated from a device of known and trusted type having the qualifies described below. >

. A chip manufactured for use in an embodiment of the présent invention would also include the manufacturer's public signature vérification key embedded within the chip in a tamper-resistant manner. The manufacturer's public signature key can be used by the user to verify instructions received from others by checking whether those instructions hâve attached a valid digital signature created by the manufacturer's private signature key, in order to détermine whether those instructions originated with the manufacturer or one trusted by the manufacturer. The chip may also include embedded and tamper-resistant

Ü1Ü456 public instructions keys that can be used by the user to verify instructions received from others. The public instructions key could «be the public key of some other trusted entity, such as Bankers Trust Co., selected by the manufacturer or could be the public key of a trusted national or global system-wide authority, and may optionally be embedded into the chip by the manufacturer for use as a short-cut to avoid having to verify the extra manufacturer-to-trusted-entity certificate. The manufacturer could install several instruction keys of various qualified key escrow houses that the manufacturer selects and believes to be capable and trusted.

Furthermore, the chip used in an embodiment of the présent invention would hâve the ability to generate a public/private key pair for encryption and decryption of data and communications by the individual user. The cryptographie encryption keys may be of any acceptable asymmetric cryptographie type, such as RSA. The cryptographie keys should, however, preferably be of the DiffieHellman type, i.e. the user's secret number is the private key and the user's publicized intermediate number is the public key, which are together used in the Certified Diffie-Hellman scheme to generate a session key that is used to encrypt and decrypt communications. The private key so generated is then stored inside the chips in a nonreadable and tamper-resistant manner. In addition, the chip would also hâve the ability, once a public/private encryption key pair for that device has already been generated, to rekey and generate a new public/private encryption key pair in place of the previous key pair. In another embodiment, Interactive Diffie-Hellman key génération can also be used, as discussed later, in order to ensure that ail senders and récipients contribute new random numbers to generate the message session keys.

In the preferred embodiment of this invention, the trusted device will hâve the ability to decrypt encrypted communications only on two conditions. The first condition is that valid master escrow center certificates for both

1 ù456 the sending and the récipient devices^ must hâve been f ed into the device prior to its receiving the encrypted transmission. Each certificate is valid if it is signed by a master escrow center certifying that the private decryption key of that device has been escrowed with one or more qualified escrow agents, and preferably with two or more Micali-style agents that employ a vérifiable key-spli-tting protocol. This master escrow center certificate either must be accompanied by another certificate issued by the manufacturer establishing the named master escrow center as a valid escrow agent, or must be signed by a third party (a trusted national or global system-wide authority) nàmed as a holder of a public instructions key embedded into the chip by the manufacturer. The second condition for decryption is that the message to be decrypted must be preceded by a valid Message Control Header (MCH) data field (the format for which will be described later) so that law enforcement or employer security personnel will hâve sufficient data from which to obtain the récipient's escrowed private keys and therewith monitor the communication.

In another embodiment of this invention, the chip will also hâve the ability to generate a public/private key pair to be used for user signatures, distinct from the embedded key pair that is used for device signatures. As with the device signature key pair, the cryptographie user signature keys may be of any acceptable cryptographie type, such as RSA, but should preferably be DSA, again to avoid any possible confusion with the keys used for message encryption. The user signature private key should be non-readable and tamper-resistant. The user would use the signature private key to sign his communications for sender vérification and non-repudiation purposes. In still another embodiment of this invention, the chip also has the ability to use the device signature key in order to sign a request for certification of the user public signature key that it has generated for the user, thus proving that the user signature key pair was generated by, and the private key is being safeguarded by, a device of known tamper-resistant

010456 properties. In further embodiments of this invention, the chip may also hâve a hardware noise source, such as a diode noise source, to generate random numbers during key génération, and a unique physical device serial number to allow the device or its actions to be tracked in accounting, network management and inventory Systems. In this erübodi— ment, the device signature would certify not only that the user's device is of known tamper-resistant properties but also that every key or random number generated by the device was randomly generated anew each time using a highquality random number generator, preferably a diode noise source.

In manufacturing the trusted device containing the chip of the présent invention, the chip's memory is divided 15 into at least three general areas as follows: (1) permanent and non-modifiable memory space containing data and firmware embedded into the chip during manufacture; (2) semi-permanent and modifiable memory space containing data, such as the user's private encryption and signature keys, 20 generated for the user and held in trust for the user by the chip, which data and keys may be utilized by the chip to make digital signatures or to decrypt on the user's behalf but which are never disclosed outside the device;

and (3) non-permanent and temporary memory space containing 25 work area used for temporary storage of the inputs, intermediate results and final results of various data processing operations. Depending on the design, these three general areas could each résidé in a different type of memory storage system, such as ROM for permanent data,

EEPROM or FLASH memory for user data held in trust, and RAM for volatile temporary storage. Another approach might be to use FLASH memory for both permanent and non-permanent data. Yet another option is to utilize a chip operating system that would manage the microprocessor's memory using a directory of objects. Under this approach, one portion of memory can be devoted to a table or directory of the other items in memory and may include standard!zed information for each object, such as:

3)

010456 logical name (e.g., manufacturer's public key);

type (e.g., key, certificate, code routine, etc.);

start address and length of data (in bytes);

- date last modified (optional);

protection level (permanent, user or volatile) ; disclosure level (externally readable or not externally readable).

In this manner, so long as the whole memory is equally tamper-resistant, no spécial areas need be designated for protected or non-protected data because the microprocessor can readily enforce the desired level of protection based on the code contained in the relevant directory entry for the data object. This scheme can also apply to firmware code routines just as easily as to data, and may be advantageously applied when upgrading or replacing trusted firmware code routines without needing to physically replace the device or any of its memory units.

The protected memory areas of a device of a preferred embodiment of the présent invention might contain the following types of information, including both data and firmware program code.

A. Permanentlv Embedded bv Manufacturer

1. May Be Externally Disclosed

a. system-wide authority public key (optional)

b. manufacturer public key

c. manufacturer certificate from system-wide authority

d. device public key

e. device certificate from manufacturer

f. device unique serial number

g. firmware version numbers

h. trusted bank public instruction keys

2. May Not Be Externally Disclosed

a.

device private signature key

0456

3. Firmware

a. operating system and file system

b. basic cryptographie library routines

c. escrow system routines

d. other trusted applications code

B. Generated by User Operations and Held in Trust for User

1· May Be Externallv Disclosed

a. user's public encryption key

b. user's public encryption key escrow certificate

c. user's public signature key

d. user's public signature key certificate

2. May Not Be Externally Disclosed

a. user's private decryption key

b. user's private signature key

C. Other Non-Volatile Read-Write Storage (Optional)

a. correspondants' signature certificates

b. correspondents' escrow certificates

c. correspondents' device certificates (for

MCH vérification)

D. Working Storage (Could Be Volatile)

Public keys (ail types), certificates (ail types), •hash values, signature blocks, other data structures being processed.

Key Escrow Process

After the chip of the présent invention has been manufactured and prior to using the chip to encrypt or decrypt communications, the user's public decryption key must be registered with a master escrow center or with escrow agents approved by the chip manufacturer. Either the user may perform this operation himself or the manufacturer may initialize and register the chip with an à

i 04 56 escrow agent during manufacture, thus^relieving the user of the requirement to escrow his keys by himself. However, the manufacturer could ,still leave the user the option to rekey by himself at a later time. For many individual users, allowing the manufacturer to register the chip, either with or without a rekey option, will be sufficient. In addition, consumers would most likely trust in the escrow agents chosen by the chip manufacturer. Corporations or other employers could program their own chips and 10 the chips of their employées, and could register the chips with escrow agents of their own choice. Corporations, however, would generally not permit their employées to -rekey on their own, because this could resuit in loss of control over corporate information and assets, as discussed above.

In order to generate and register a decryption key, the user (or whatever entity is performing the operation) invokes a firmware program that has been embedded into the chip and that instructs the chip to perform the partîcular steps of the Micali key escrow method or of the spécifie key escrow method that is used. See FIGS. 9-11, 15 and 16. Using whichever method is chosen for escrowing the private key with one or more escrow agents, the chip will first randomly generate, or choose, a secret number that will be the private decryption key for that user (as well as the other, public numbers that will be required, if those numbers hâve not already been set by some other prior random génération). The chip will store the private key in a non-readable and tamper-resistant manner. As shown in FIG. 15, the private decryption key can be escrowed with a single escrow agent. The trusted device 150 first generates a public/private encryption key pair 151 for the user and then sends to the escrow center 153 an encrypted and signed message 152 consisting of the encryption key pair 151 and the device serial number 154, with the manufacturer's certificate 155 for signature vérification. The escrow center 153 vérifiés the signatures, decrypts the message packet and stores the user's private decryption key. The escrow center 153 also sends to the user a signed

010456 certificate 156 consisting of the user's device serial number 154 and the user's public encryption key 151 and the device's public signature vérification key 157, with the escrow center's certificate 158 for signature vérification. Once the user's device vérifiés the escrow center's signature, registration is complété.

If the private key is to be escrowed with more than one escrow agent, then the chip will then break the private key into several pièces called key splits, according to a spécifie formula. Using the Micali escrow method and algorithm described earlier and shown in FIG. 9, the chip will next compute certain values 90 using the spécial Micali algorithm such that each value is based upon a mathematical transformation of one of the private key pièces 92. The chip then forms one share packet for each trustée or escrow agent 94 designated by the user, each share packet 93 containing the unique serial number of the user's device, one private key split and the set of certain values that enable the particular trustée to verify the received private key split as a valid part of the complété private key, without giving the trustée knowledge of the complété private key. As discussed later, if the user is not the owner of the device but rather, for example, an employée of the employer-owner, the trustée share packet would also include the unique identification number of the owner of the device and the device's owner certificate so

A that employer-owner would be able to obtain the private key of the employee-user without having to first obtain a warrant. The chip then signs each trustée share packet using the unique device private signature key and attaches the manufacturer's certificate for the transmitting chip, thereby attesting that the information transmitted originated from a device of known and trusted type. Finally, the chip will output each signed trustée share packet for delivery by the user to a trusted escrow agent.

There is another, preferred way for the master escrow center to verify the separate key splits, without using the Micali method, by relying upon the trusted device alone.

010456

Using this method of verifying the key splits, shown in FIG. 16, the chip generates one random number for each key split of the private encryption key. The chip then forrns one share packet 161 for each trustée or escrow agent 163 designated by the user, each packet containing the unique number of the user⁷s device, one private key split and one of the random numbers. The chip signs each trustée share packet using the unique device private signature key and attaches the manufacturer's certificate 162 for the transmitting chip, thereby attesting that the information transmitted originated from a device of known and trusted type. As with the Micali method, the chip will then output each signed trustée share packet 161 for delivery by the user to a trusted escrow agent 163. In addition, the chip must also create a message (encrypted) 164 to the master escrow center 165 containing, among other things, the user's public encryption key and the names of the escrow agents designated by the user and along with the random number given with the key splits to each respective escrow agent.

It is possible, however, because each trustée share packet contains a private key split, that a third party with access to communications from a user to the escrow agents could read the contents of ail the user⁷s share packets and recombine the private key splits within those packets in order to reassemble the complété private key.

y

Then, using the private key, that third party could decrypt and encrypt communications in the name of the user. The best way to avoid this situation is by using encrypted communications Systems when sending share packets from users to escrow agents. The user would obtain the public encryption key certificate 166 of each escrow agent selected for escrowing the user⁷s private key, where each certificate is signed by the master escrow center certifying that the particular escrow agent is trusted by the master escrow center to receive and store a key split packet, and would then verify the master escrow center⁷s signature either using a certificate from the device⁷s

Μ

01Ü456 manufacturer (or from a system-wide authority) or using a preembedded instructions key. The device would then encrypt for each escrow agent based upon that agent's certified public encryption key a transmission 161 that includes the user's private key share packet. Alterna.tively, the manufacturer could embed into the chip the public encryption keys of several trusted escrow agents matched with an instructions key for each, as discussed earlier, in order for the user to send his private key splits to escrow agents trusted by the holder of the instruction keys, which is typically the master escrow center. This way, ail the escrow agents in the master escrow center's or the manufacturer's family could decrypt user requests for escrow, while sparing the user the burden of obtaining the public encryption key certificates of ail escrow agents.

Once each escrow agent or trustée 163 receives the appropriate share packet 161 from the user or from the user's device, the trustée inspects the private key split received in the trustée share packet 161 from the user's device and, together with the master escrow center 165, vérifiés that it is a valid and correct part of the complété private key. It is necessary for the escrow agents and the master escrow center to hâve a reliable means of proving or verifying that the fragments of the user's private decryption key hâve in fact been deposited. It is désirable that vérification of the key splits be accomplished by the escrow agents and the master escrow center without ever inspecting or possessing those fragments itself, or ever bringing them together in one location. The Micali Fair° escrow system provides one highly trusted way for the escrow center to verify the separate deposits of the key fragments. In the Micali method, shown in FIGS. 10 and 11, this vérification is done with the set of certain values that were computed by the user's chip during préparation of the share packet through use of a spécial Micali algorithm and that were included with the key split in each share packet to the escrow

010456 agents. The Micali algorithm and key. split verifi-cat.ion are known in the art and need not be repeated here. Each trustée 94 then stores,the device's manufacturer's certificate for later use in decoding, and approves the key split 93 by sending an appropriate signed message 96 to the master escrow center, along with the user's name and device certificate, and by signing and storing the key split 90. Only when presented with either (a) a warrant or court order or (b) a signed request from the lawful owner of the device will the trustée reveal the piece (or pièces) of a given private decryption key in its possession.

Using the preferred escrow and vérification method relying on the trusted device alone, shown in FIG. 16, each trustée 163 transmits a message 167 to the master escrow center 165 identifying the user's name, public encryption key, device number and the random number it received. In addition, the user device sends a packet to the master escrow center 165 containing the random numbers used for vérification of the private key splits, and that packet should be encrypted using the master escrow center's public encryption key. The master escrow center 165 receives the messages 164,167 from the user device and from the trustées 163, and vérifiés that the individual random number received from each trustée matches the random number that the user device stated was given to that trustée. Note that under this method the escrow agents 163 and master escrow center 165 rely solely upon the trusted device's signature on the share packets 161 to assure themselves that the escrow is proper. This escrow and vérification method does not need to perform any secondary mathematical operations in order to verify that the escrow is proper or that the public key presented for certification matches the deposited key fragments. Although from the standpoir.t of public, user or systemwide trust, it might still be désirable to utilize a vérifiable key escrow algorithm such as the Micali process, it is clearly not necessary and may be dispensed with when the added cost of using such a process cannot be justified. In addition, by this method

010456 of relying upon the trusted device alone, there is no limit to the complexity of the key splitting schemes that can be devised, because there is no need to devise complex secondary algorithms to verify correct performance of any given scheme. It is necessary only to trust the integrity of the device manufacturer that embedded the firmware code and to trust that the device will resist tampering.

After verifying ail the user's private key splits, the master escrow center itself further approves the public encryption key that corresponds to the private decryption key that was approved by ail the user's trustées; the master escrow center 165 approves the public key by issuing a signed certificate 168 (called the master escrow center certificate, the public encryption key certificate, or simply, the escrow certificate) certifying that the private key corresponding to the public key being certified has already been escrowed in the proper fashion. The public signature key of the user's device, obtained from the device's manufacturer's certificate, can also be placed in the master escrow center certificate, thus eliminating the need to send or reverify the device manufacturer certificate at later points in the process. The master escrow center certificate could be formatted as follows:

Version Number

Escrow Certificate Serial Number Master Escrow Center Country Code Master Escrow Center Name Master Escrow Center Public Encryption Key (for use in creating LEAF) User Distinguished Name User Public Encryption Key (hereby being certified) User Device Public Signature Vérification Key (to verify device signature) Validity Date (start/end) Master Escrow Center Signature [Master Escrow Center System-wide Certificate]

010456

Public encryption key certificates that hâve been issued by the master escrow center are distributed and can be used either by the device owner in order to activate his device to originate encrypted messages or by others to encrypt messages to the owner of the device containing that user⁷s public/private encryption key pair.

It should be noted that the présent invention does not require more than one escrow agent to be the récipient of the user⁷s private encryption key splits; in some cases, it 10 might be enough merely to deposit the user⁷s private decryption key with a single escrow agent (or escrow center). However, in order to enhance user and public trust in the system, it is désirable to split the user⁷s private decryption key among several escrow agents such 15 that ail the key splits, or some specified number of them, are required in order to reassemble the user⁷ s key and decrypt his communications. It is further désirable that each escrow agent be an independent, trusted business operation, thereby effecting split knowledge, so that in 20 the event of attempted corruption, bribery, extortion or abuse, it will be much more difficult to wrongfully obtain the user⁷ s private decryption key than it would be if the private key were stored with a single entity. It is also désirable that the entities be separated geographically in 25 order to further suppress attempted subversion or corruption.

Encryption of Communications

A user who desires to send an encrypted communication to another user must hâve an escrow certificate for his own 30 device and an escrow certificate for the intended récipient⁷s public encryption key, because the device of the présent invention will neither encrypt nor decrypt if either is missing. First, the sender must load his own valid certificate into the device, typically when he first 35 receives it from the master escrow center. Then, the intended récipient⁷ s public key certificate can be obtained either from the intended récipient directly, .from a

010456 directory service listing public key certificates, or from the sender's local file, e.g. a file of users witb whoan the sender has previously exchamged encrypted communications. In one embodiment of the présent invention, because th.e sender's device will not encrypt and the récipient's device will not decrypt unless the récipient's public encryption key certificate is ”valid,” in order for the recipient's device to decrypt the encrypted message, the recipient's public encryption key certificate must be signed by either (a) the récipient device's manufacturer (this is unlikely to be the case because device manufacturers will most probably not be escrowing user's private keys) ; (b) -th.e master escrow center, and accompanied by a manufacturer's certificate approving the master escrow center as a valid trustée; or (c) a trustée or master escrow center whose instructions key was embedded into the device during manufacture. Using the intended recipient's certified public encryption key as set forth in the recipient's public encryption key certificate, the sending user then generates a session key for use by both the sender and the récipient to encrypt and decrypt the communication. This session key can be generated preferably using the Certified Diffie-Hellman method or, alternatively, any other équivalent system. In the Certified Diffie-Hellman method, the user first randomly generates his ephemeral private key for that message and then computes the session key based upon his own private key and the recipient's. public key (i.e., the recipient's intermediate number and the two public numbers, which are all contained with the recipient's public encryption key certificate). Then, using the session key, the sender encrypts the message to be sent to the récipient user.

However, in deciding whether or not to send an encrypted message to the intended récipient, the sender may be unable to verify the properties of the recipient's public encryption key certificate or of the digital signatures thereon if the sender's device were made by a manufacturer different from the one that made the

Û1ύ456 récipient's device. The fact that the récipient's device was made by a different manufacturer would prevent the sender's device from easily verifying either the manufacturer's signature or the certificate of the manufacturer (that certified the master escrow center that signed the récipient's key escrow certificate) stating that the récipient's master escrow center is valid and approved by that manufacturer. Likewise, the récipient's chip would be unable to verify these conditions with respect to the sender's certificate before decrypting. Enforcement of the escrow restriction on both parties is needed in order to enable law enforcement agents to lawfully intercept- and decrypt messages being both sent and received by a given suspected user, without necessarily obtaining the other, non-monitored party's private decryption key and, thereby, access that non-monitored party's unrelated messages.

One way to address this issue, while still allowing more than one manufacturer to make cryptographie devices, is to embed into the device or into a certificate issued by either the user's master escrow center or the chip manufacturer a public key from a trusted national entity, for example the Fédéral Reserve Bank (”FRB), which could be used to verify yet another certificate issued by the FRB to each of the other various master escrow centers or manufacturers. Such a certificate would verify the trustworthiness of the particular master escrow center or manufacturer and would be signed by the FRB. A sending user could then obtain the public encryption key certificate of an intended récipient and could trust the master escrow center that issued the certificate because the master escrow center was accredited by the FRB, rather than by the chip manufacturer, as certified by the FRB public key or certificate. Also, the signature of a particular device could be trusted because the other manufacturer that certified that device was accredited by the FRB, as certified by the FRB certificate or public key. In order to deal with this issue on a less parochial United States-based level and promote a more international and

010456 worldwide system, the public key of trusted global entity, such as the Bank for International Settlements in Switzerland, could be embedded into either the trusted device, the FRB certificate or the master escrow center or manufacturer certificate (depending upon the trust model employed), and could operate the same way discussed regarding the FRB key, in order to accredit master escrow centers and manufacturers on a worldwide basis. Another way, albeit one not involving U.S. or world authorities, for one device to trust the escrow centers certified by another manufacturer is for the device manufacturers or master escrow centers to cross-certify each other. -This would allow the sender's device to help enforce the récipient's escrow restrictions by allowing the sender's device to verify the certification path of the récipient's escrow certificate back through the récipient's device manufacturer or master escrow center to his own. In the preferred embodiment, the public key of a trusted systemwide entity would be embedded into the trusted device and would operate the same way discussed above regarding the FRB or global entity key, in order to accredit ail the master escrow centers and manufacturers on a system-wide basis.

Whenever any user, entity or device vérifiés a digitally signed certificate, whether a manufacturer's certificate or an escrow certificate, issued by a certifying authority or manufacturer, it is common practice in most or ail actual and proposed public key certificate management systems (and it is assumed throughout this disclosure) that the user, entity or device also checks any applicable certificate révocation list (CRL) in order to détermine whether the certifying authority or other issuer has distributed, propagated or otherwise made available a list of revoked certificates that is updated in accord with an appropriate security policy and whether, based upon the issuer name and certificate number, the certificate has been revoked. A certificate issued to a user could be revoked for death, name or employaient change,

01û 45 6 or loss, theft or destruction of the device (the personal smart card) containing the private key. A certificate issued to an entity may be revoked due to cessation of business, name change, or loss, theft or destruction of the 5 device containing the private key. A certificate issued to a device may be revoked due to loss, theft, removal frcm service or destruction of the device. The checkina of CRLs during certificate vérification is well-described in the public literature (e.g., ANSI X9.30 - Part 3) and does not 10 require further discussion. Ail users, entities and devices will normally hâve access to appropriate télécommunications facilities and can retrieve CRLs or perfora inquiries as desired. Likewise, under the présent invention, ail entities issuing CRLs are presumed to make 15 them avaiiable to ail interested parties.

Message Control Header Format

When sending an encrypted communication, the sending user must also form a suitable Message Control Header (MCH) field containing the following information:

(1) The sender's intermediate number for the encrypted message, computed by the sender using the sender's randomly generated ephemeral private key that was also used by the sender to compute the session key with which the message was encrypted. The récipient user must hâve this inter25 médiate number in order to compute the session key for decrypting the message.

(2) The name and country code of the sender's master escrow center.

(3) The name and country code of the recipienr's master escrow center, obtained from the récipient's public key certificate.

(4) The sender's escrow certificate number, encrypted using the public encryption key of the sender's master escrow center (obtained from the sender's escrow certificate) so that only the sender's master escrow center may decrypt it.

010456 (5) The sender's intermediate nimber (different from the sender's previous intermediate number) that was used by the sender to compute the ephemeral session key with which the sender's certificate number was encrypted to the sender's master escrow center. The sender's master escrow center must hâve this number in order to compute the ephemeral key for decrypting the sender's certificate number.

(6) The session key for the encrypted message, encrypted using the sender's own public key (the intermediate number from the sender's own public certificate), so that in effect the sender sends the message session key to himself. Law enforcement can gain access to this message session key once it obtains the sender's private key components from the sender's escrow agents.

(7) The sender's intermediate number (different from the sender's two previous intermediate numbers) that was used by the sender to compute the ephemeral key with which the message session key was encrypted to himself- Law enforcement must hâve this number in order to compute, using also the sender's private key (his secret number) obtained from the sender's master escrow center, the ephemeral key for decrypting the message session key.

(8) The récipient's certificate number, encrypted using the public encryption key of the récipient's master escrow center (obtained from the récipient's escrow certificate) so that only the récipient's master escrow center may decrypt it.

(9) The sender's intermediate number (different from the sender's three previous intermediate numbers) that was used by the sender to compute the ephemeral key with which the récipient's escrow certificate number was encrypted to the récipient's master escrow center. The récipient's master escrow center must hâve this number in order to compute the ephemeral session key for decrypting the récipient's certificate number.

010456 (10) Timestamp (optional), for tracking purposes and possibly to assist in the enforcement of warrant date and time restrictions.

Λ (11) The signature of the sender's device.

(12) The sender's public key escrow certificate issued by the sender's master escrow center. The sender's escrow certificate contains the sender's device public signature key, which the master escrow center had pre-verified and then copied from the sender's device's manufacturer's certificate.

(13) The master escrow center's certificate from the FRB, the manufacturer or whatever system-wide authority is trusted, if the récipient's chip is made by a different manufacturer, appended to the sender's escrow certificate. The certificate of the manufacturer, the FRB or the systemwide authority is needed only for the first communication between the two parties. The certificate could also be a cross-certificate from the récipient's manufacturer or master escrow center.

The MCH thus described could be summarized as follows:

Sender Intermediate Number (to allow the récipient to decrypt the message)

Sender Master Escrow Center Country Code Sender Master Escrow Center Name

Récipient Master Escrow Center Country Code Récipient Master Escrow Center Name

Sender Escrow Certificate Number, encrypted for Sender Master Escrow Center

Sender Intermediate Number (for encrypting the sender certificate number)

Message Session Key, encrypted for sender Sender Intermediate Number (for encrypting the message session key to the sender) Récipient Escrow Certificate Number, encrypted for Récipient Master Escrow Center Sender Intermediate Number (for encrypting the récipient certificate number)

Timestamp

Sender Device MCH Signature

010456 [Sender Escrow Certificate] [Escrow Center Certificate]

FIG. 17 shows a process for sending an encrypted message 176 with a MCH. The entire MCH 172 (the appended certificates 173,174,175 are not technically part of the MCH) is signed by the sender's device 171, using the device private DSA signature key, with the embedded certificate of the manufacturer appended thereto (within the sender's escrow certificate) in order to certify the device's public signature key. This guarantees that the entire MCH is delivered intact to the récipient and that the récipient's chip can easily verify that the MCH has not been modified. The manufacturer's certificate might be accompanied by an national (FRB) or a world-authority certificate to certify the trustworthiness of the manufacturer of the sender's chip in case the récipient's device was manufactured by a different manufacturer.

In another embodiment of this invention, a second, shorter MCH format could be used for the case in which total privacy is not crucial. In this MCH, neither the Sender Certificate Number nor the Récipient Certificate Number are encrypted for the respective master escrow center. Not encrypting the certificate numbers saves much time and space in création of the MCH. In still another embodiment of this invention, a third, even shorter MCH format could be used for the common case in'which the sender and the récipient both utilize the same master escrow center for key escrow purposes, by making ECl identical to EC2. By eliminating the need in the MCH for identifying information of the second master escrow center and for the spécial intermediate number that is used for encrypting the récipient certificate number to the second master escrow center, the MCH can be made significantly shorter. Furthermore, the size of the MCH could be further reduced by using RSA key transport to encrypt a DES key for the message and for each of the three encrypted inner LEAF components. According to this method, each sender

U456 intermediate number would be replaced by a smaller RSAwrapped DES key. Thus, the sender could RSA-encrypt the message session key for the récipient and eliminate the need for the first intermediate number in the MCH. The sender could also RSA-encrypt the message session key for himself (actually, for law enforcement to decrypt later) and thus eliminate the need for the third intermediate number in the MCH. The sender could further RSA-encrypt his own and the récipient's certificate numbers and thus eliminate the need for the second and fourth intermediate numbers in the MCH. As shown in FIG. 18, eliminating the four intermediate numbers and its associated encryption and replacing each intermediate number with a smaller RSA transport encryption 181 saves a significant amount of space of the MCH size.

Contribution of Random Material

Some may be concerned that a message session key exchanged using only the RSA key transport method or the Certified Diffie-Hellman scheme is not sufficiently secure because, with either of these two methods, although both the sender and the récipient provide information, only the sender generates the message session key. However, under military standards for secure communication, both sender and récipient must contribute random material in generating a session key prior to each communication session, apparently in order to reduce the chance that the sender might use a weak key or use the same key repeatedly and thereby subject the récipient to an undesired security risk against his will. The system of trusted devices contemplated under this invention can alleviate this fear in two ways. First, it can ensure that the sending device will generate each key separately using random numbers derived from the noise of a built-in hardware noise source, such as a reverse-bias diode, as discussed earlier. Then, so long as the device signs the MCH or message control header, the récipient would be assured that each message session key and the random numbers used in generating it are strong and

010456 unique. Still, those insistent upon .greater security may demand contribution of random material by both sides of the communication, as defined for Type-1 military Systems for classified information.

Thus far in this disclosure, the sender has been described as generating message session keys based on the récipient* s public encryption key as contained in his escrow certificate, but not based on random material received from the récipient during the setup phase of the communication. Arranging for the sender to receive a contribution from the récipient, however, créâtes a new problem. The récipient cannot simply be allowed to generate a Diffie-Hellman intermediate number on his own and send it to the sender for use in generating a message session key, because the récipient then would no longer be using the escrowed private key within his trusted device to decrypt messages and because their communications could never be monitored by law enforcement. Continued success in enforcing the escrow scheme requires that neither sender nor récipient be able to read a message without using a registered trusted device.

In order to allow a situation in which both the sender and the récipient contribute random material to the message session key prior to communicating, the initial keyexchange protocol may be modified to allow a would-be récipient⁷s device to generate a new ephemeral DiffleHellman secret number, separate and apart from that récipient⁷s escrowed private key, that will be used to compute a new intermediate number that will, in turn, be sent to the sender for use computing the message session key for encrypting the message. The récipient⁷s escrowed private key would still be used to generate the intermediate numbers (included in the MCH) and the ephemeral session keys that are used to encrypt the various portions of the MCH. This modification requires, however, that génération of the new secret number occur inside the wouldbe récipient⁷s device, that this new secret number remain inside the trusted device, and that the new intermediate

010456 number be signed by the would-be récipient's device prior to being sent to the sender's device for the purpose of attesting that the new ^ephemeral secret number is indeed confined securely inside the récipient's device. As before, the sender's device generates a new secret number that is separate and apart from the sender's escrowed private key and, using that new secret number and the récipient's new intermediate number, generates th.e message session key for decrypting the message. The sender's device will also use the sender's new secret number to generate the sender's new intermediate number, which will be sent to the récipient's device as an element of the MCH for wiretapping purposes. In this method, the message session key would, therefore, include random material contributed by both the sender and the récipient, as desired.

However, under this modified key-exchange protocol, because the récipient and sender in effect use new DiffieHellman private keys for each message, the escrow feature still “disappears,” as law enforcement and corporate management would never be able to obtain those ephemeral message session keys from the escrow agents. Therefore, the needs of the escrow system and the community of interest require that the message session key be transported in the MCH as before. In fact, in order to assure equality of tapping, ail fields that were before disclosed as part of the MCH remain so. The field transporting the message session key to the sender (which is the only way for law enforcement agents who are wiretapping the sender to read the message) must still be included in the MCH in order to preserve the principle of equality of tapping. The message session key will be encrypted into the MCH, as before, using the sender's public encryption key, to which law enforcement will still hâve access. The sender's new intermediate number will be sent to the récipient as the first element of the MCH, as before, in order to allow law enforcement to wiretap the récipient and compute the message session key. Thus, in order to accommodate the

010456

Interactive Diffie-Hellman key exchange technique, this protocol requires that the would-be récipient's new intermédiate number be generated inside and be signed by his device, and requires that the sender's new intermediate 5 number be added to the MCH, not used in place of the previously stated key transport methods, as that is the only way the community of interest (law enforcement, employers, and others) can read the message. This method, however, would not be economical for transactions besides 10 on-line phone, network, or dial-up transactions, because the device would hâve to remember too much, i.e. the spécial intermediate numbers for each counterparty.- This method is preferably to be used in cellular phone, network logons, etc., through which a purely real-time interactive 15 session is desired.

Community of Interest Headers

The MCH will generally be placed before the encrypted message, as a message header. In many current electronic mail and document systems, several récipients are enabled 20 to read one encoded message, using the RSA transport embodiment of the MCH design as discussed above, by RSAencrypting the message session key using the public encryption key of each récipient. That is, when several récipients are intended to receive the same encrypted 25 message, the MCH header can include, for each intended récipient, the intended récipient's name followed by the message session key, RSA-encrypted to each intended récipient using that récipient's public encryption key. Thus, each intended récipient can locate his entry in the 30 MCH header, decrypt his copy of the message session key and read the message. Even with several intended récipients, the correctness of the MCH is enforced on both ends of the communication: on the sending end, the MCH output is enforced by the internai logic of the sender's device, i.e. 35 the requirement that it create a valid MCH prior to encrypting a message; on the receiving end, the MCH correctness is enforced by vérification by the receiver's

010456 device of the digital signature of the sender's device. As previously noted, because the récipients' copies of the message key are intégral to the MCH, no récipient can decrypt the message unless the MCH is sent and received intact, unlike the Clipper system in which the MCH is not itself linked to the key transport mechanism.

Under this MCH formatting concept, the MCH could be summarized as shown in FIG. 25. As in previous MCH formats, the authenticity of the MCH is guaranteed by the digital signature of the sender's device 258. Furthermore, as before, the escrow certificate numbers of the sender and the récipient are encrypted under the public encryption keys of their respective master escrow centers 251,252. In this format, however, the MCH, signed by the sender's device, becomes a modified list of récipients that is more flexible and easier to understand in relation to the way contemporary encrypted electronic mail Systems work. For example, the sender's and récipient's names (or system IDs or addresses) are now shown unencrypted in the MCH 253,254. Although this impinges on the anonymity of the sender and the récipient, as a practical matter it is difficult to send messages in an electronic mail system without tagging the messages with the names and addresses of the senders and récipients. Hence the loss of privacy is slight. In addition, the names of the sender's and récipient's employers 255,256 (or their unique IDs, such as tax numbers or DUNS numbers) are also shown ùnencrypted, thus greatly reducing the burden on the employers' security staffs to find messages sent and received by their respective employées. Alternatively, instead of leaving the sender, récipient and employer name blocks unencrypted, these entries could just as well read sender, addressee, sender's employer and recipient's employer (or their équivalents) unencrypted, with the actual identifiers inside the encrypted areas, as before. Thus, an intended récipient of the communication would look in the MCH for his unencrypted identifying abbreviation and in this way will attempt to decrypt and read only the portions of the MCH that are directed to and encrypted for him.

In addition, this -MCH format as shown in FIG. 25 allows access by possible sub-units within the employer organization, by defining secondary employer lines (a, b, etc.). For secrecy-conscious employers, the MCH could read sender empl sub-unit b unencrypted, as discussed above, and contain the actual company unit identifier in the encrypted area. Because each MCH entry is labeled, there is no limit on how many layers of employer access there can be; ail of them become in some sense authorized récipients” of the message. Furthermore, in contrast to previous MCH formats, this MCH format can include the message session key encrypted directly to the employer 257 so that the employer need not go to the master escrow center and agents in order to obtain the message session key for decrypting the message. Although possibly impinging on employée expectations of privacy in the workplace, this format can allow employers to check or recover their employées' files with minimal effort.

In order to create a MCH in this format prior to sending a communication,_:.the sender must first obtain ail the necessary names/codes and public keys of the intended récipients and their employers. This information can be garnered from the récipient's escrow certificate and from his own escrow certificate. However, in order to generalize this approach and make this information available to a user who desires to send a communication, the master escrow centers must include into each user's standard form escrow certificate, as discussed earlier, the unique identification or code number and public encryption key of both his employer and any employer sub-units. The escrow certificate layout could be desiqned by using repeating subgroups, for efficient handling of variable numbers of community-of-interest parties. Each communityof-interest party entry would hâve a unique identification number, a public encryption key and, possibly, an instruction code (or policy code, as discussed below) instructing the sender's device how to encode that^ party's MCE entry. The instruction code could include éléments of chcice giving the sending device the options of including (1) the party's unique identification number either unencrypted or using an alias, e.g., empl-a;^M (2) the message session key in the coded area or not; (3) the party's unique identification number in the coded area or not; and (4) the tisaestamp or a random number at the start of the coded area or not. These (and possibly other) instruction codes could be defined as bitmask flags. The list of parties (and/or their codes), their public encryption keys and the instruction flags would tell the sender's device how to format the community-of-interest portions of the MCH in accord with the desires of each party for partial or total anonymity. It is anticipated that in practice, many community-ofinterest parties will not bother with anonymity, because it will be much easier for them to search for and identify their employées' messages if they keep their own marnes and identification numbers in the clear.

Decrvption bv Récipients

When the intended récipient receives the encrypted message 191 and the MCH field 192, several things must be done in order for the récipient to read the message, as shown in FIG. 19. First, the récipient must load his own valid escrow certificate 193 into his chip 190 because, under the preferred embodiment of this invention, the chip will not decrypt without it. Typically, the récipient's escrow certificate will already be stored in the device's memory in a pre-verified state. The récipient next loads the MCH 192 and the sender's escrow certificate 194, which also contains the sender's device's public signature vérification key (with the appropriate system-wide, national or world authority certificate 195, if necessary) into his chip 190. The récipient's chip 190 checks the sender's escrow certificate 194 in order to verify that the sender's private decryption key has been escrowed. This is done by using the public key of the manufacturer to verify r%>

010456 the signature of the manufacturer on the device certificate or, if necessary, the signature of the system-wide authority on the escrow center certificate and by checking whether the escrow center's signature on the sender's escrow certificate is valid. In the preferred embodiment, the public signature key 196 of the system-wide authority is used to directly verify the escrow certificate 195. The récipient's chip then checks the MCH signature before proceeding in order to verify that (1) the sending device is trusted, (2) the sender's key is escrowed, as also verified by the sender, and (3) the MCH 192 is valid, i.e. the MCH is in the proper format and contains ail the requisite information. This is done by verifying the sender's device signature, the sender's device manufac15 turer's certificate signature and, if necessary, the manufacturer's system-wide authority certificate. The manufacturer's and the system-wide authority's public keys could be embedded into the récipient's chip 190 to facilitate this vérification process. In the simples^ case, the récipient need validate the sender's escrow certificate 194 only once, against its own embedded manufacturer's public key or system-wide trusted entity instructions key. Once those are shown to be valid for a particular sender, the récipient needs only to use the sender's pre-validated device public key to validate the

MCH signature, resulting in only a single signature validation per message. If either the sender's certificate 194 or the MCH 192 is invalid, the récipient's chip will not decrypt the message. Finally, after verifying these certificates and signatures, the récipient computes the message session key based upon the sender's intermediate number, which was included in the MCH, and the récipient's own private key (his secret number) corresponding to his public key as publicized in his public encryption key certificate 193. Using the session key, the récipient decrypts the message sent by the sending user.

Û10456

Decryption by Law Enforcement

In order to intercept and decrypt communications to and from a particular user, law enforcement must hâve court authorization or a warrant to monitor that particular user's communications. The court authorization will, in ail probability, include (1) a start monitoring date and time at which law enforcement may begin to monitor the user's communications, (2) an end monitoring date and time after which law enforcement may not monitor the user's 10 communications, and possibly (3) a grâce period to foilow the end monitoring date, during which grâce period the law enforcement may retain the user's private key in order only to decrypt the previously-intercepted communications but not to intercept or monitor any additional communica15 tions of that user. In monitoring the communications of the sending user, law enforcement intercepts the communication and identifies from the MCH the name and country of the sender's master escrow center in order to détermine from whom to request the sender's private decryption key.

Law enforcement then présents the court authorization and the MCH from the intercepted communication to the sender's master escrow center, which uses its private key to decrypt the sender's certificate number that was encrypted inuo the MCH. Using the sender's certificate number, the sender's 25 master escrow center looks up the sending user's name and the names of the sender's escrow agents, and reveals them ail to the law enforcement agent along with.the sender's device manufacturer certificate, which law enforcement will need later during decoding. The law enforcement agent then 30 contacts each of the sender's escrow agents and présents to it the sender's name and the warrant, and obtains from each escrow agent the key splits entrusted to it by the sender. Because the preferred method of intercepting and decrypting encrypted communications by law enforcement in this mven35 tion is by using the décoder box specified below, the law enforcement request to the escrow agents will also include the public encryption key of the law enforcement deccder box, so that the key splits can be sent directly to the law

010456 enforcement décoder box and not to the law enforcement agents themselves. Each escrow agent sends the sender⁷ s key split in its possession to the law enforcement décoder box as an encrypted message having a start monitoring date, an “stop monitoring” date and an opticnal grâce period so that the décoder box can enforce the terms of the warrant. The décoder box then decrypts the encrypted key split messages, combines the key splits and uses the sender's reassembled private key to obtain the session key for the communication, which session key was encrypted by the sender into the MCH as a message sent to himself. The décoder box can then monitor and intercept communications to and from the sender only during the monitoring period specified in the warrant, and can continue to decrypt those intercepted communications only until the end of the grâce period specified in the warrant.

A similar procedure is used to monitor communications to and from the récipient. From the MCH of the intercepted communication, law enforcement identifies the name and country of the récipient⁷ s master escrow center and then présents the warrant and the MCH from the intercepted communication to the récipient⁷s master escrow center, which uses its private key to decrypt the récipient⁷ s certificate number that was encrypted into the MCH. Using the récipient⁷s certificate number, the récipient⁷s master escrow center looks up the récipient⁷ s name and the names y

of his escrow agents and reveals them ail to the law enforcement agent. The law enforcement agent then contacts each of the récipient⁷ s escrow agents and présents to it the récipient⁷s name and the warrant. Each escrow agent sends the key split entrusted to it by the récipient user to the law enforcement décoder box as a message encrypted to the décoder box having a start monitoring date, a stop monitoring date and a grâce period for enforcement of the terms of the warrant by the décoder box. The décoder box then decrypts the encrypted key splits, combines them and uses the récipient⁷ s resulting reassembled private key, along with the sender's intermediate number,

010456 which is at the head of each MCH, to compute the session key for the communication. The décoder box can then monitor and intercept communications to and from the récipient only during the monitoring period specified in the warrant, and can continue to decrypt those intercepted communications only until the end of the grâce period specified in the warrant.

In another embodiment of the présent invention, the format for each escrow agent's encrypted key split message to the law enforcement décoder box might be as foilows:

User's Certificate Number Private Key Fragment: X(i) Begin Monitoring Date and Time Stop Monitoring Date and Time Court-allowed Grâce Period (days/hours) Date and Time (of this key split message) Escrow Agent Signature [Escrow Agent Certificate]

In this format, ail information except for the Certificate Number would be encrypted under the encryption key of the décoder box. Because the key split messages from the escrow agents are encrypted for that particular décoder box, no other user or décoder box can read them. Further more, the Begin Monitoring” and Stop Monitoring” dates and times instruct the décoder box when to begin monitoring and decoding communications and when to stop- monitoring; the Grâce Period allows the décoder box an additional, specified time period to décodé any backlog of the previously intercepted communications, after which time period the décoder box must stop decoding and must erase the subject's private key. Thus, the décoder box can be used to decrypt the monitored user's communications until the date specified in the warrant, at which time the décoder box and its embedded time clock prevent any further decryption. The décoder box could also refuse to process key split messages having a Message Date and Time older than

010456 twelve (12) hours (or some other specified time period) or having an Expire Date and Time that has already passed.

Décoder Box Implémentation

In a preferred embodiment of this invention, law enforcement employs a spécial tamper-resistant décoder box for intercepting and decrypting the communications of monitored users under certain defined and controlled conditions. An example of a décoder box and its process flow is shown in FIG. 20. The décoder box 200 is désignée to be a trusted device of a similar design within the system of trusted devices of the présent invention and, therefore, can enforce various conditions in order te prevent improper action by law enforcement agents. The décoder box 200 has a private device signature key embedded by the manufacturer and a manufacturer's public signature key certificate 202 for the public signature key that matches the device private signature key. In addition to the manufacturer's certificate 202, the décoder box may also hâve a certificate 203 issued by (or on behalf of) a law enforcement authority or corporate security department that owns the décoder box, attesting or notarizing the connection between the décoder box and the law enforcement or security authority, and attesting that the décoder box is under its sole possession and control. The décoder box 200 also has the ability to generate a public/private key pair, just like the regular user chip of the présent invention, for encryption and decryption of administration and control messages to the décoder box. The décoder box 200 further has the abilities to store its private key securely and to issue the corresponding public encryption key within a certificate 201 signed by itself, with its device certificate 202 signed by the manufacturer attached. Having this ability to generate (and use) the public/private key pair enables the escrow agents 206 of a wiretapped user, upon présentation by law enforcement agents to the master escrow center of a warrant to monitor the user's communications, to send the key splits 204 of that wireS?

010456 tapped user to the décoder box encrypted using the décoder box's public encryption key and enables the décoder box to decrypt those key splits using its private decryption key. However, unlike a regular user chip of the présent invention, which decrypts a message and returns the unencrypted resuit to the user, the décoder box never outputs the wiretapped user's private key to the law enforcement agents. Instead, the décoder box stores this information securely until the end of the Grâce Period specified in the warrant and in the key split messages, at which time the décoder box erases the information permanently.

Accordingly, in order to perfora its duties as-a trusted device and enforce the date and time restrictions imposed by the wiretap authorization, the décoder box 200 must also contain a trusted, calibrated and certified date/time clock 205. The décoder box manufacturer certifies and attests to the validity and the calibration of the clock 205 when the manufacturer issues a device certificate 202 with its list of known device properties. When the décoder box 200 receives from the escrow agents 207 the key splits 204 containing time limits (based upon the warrant) before or after which the warrant is not valid, the décoder box 200 uses its internai time clock 205 to verify that the law enforcement warrant is still valid. If the warrant is not yet valid, the décoder box will not monitor or decrypt the communications of the wiretapped user. If the warrant (and any applicable grâce period) has expired, the wiretapped user's private key is erased and will not be recreated again under that warrant by the décoder box (unless a new warrant having a new time period is issued). It should be noted that, although the trusted time clock 205 is optional for a regular user chip of the présent invention, it is mandatory for the décoder box 200 in order to allow the décoder box to enforce the date and time limits of the wiretap warrant. However, the user of the regular user chip can assist in the time limit enforcement by maintaining the calibration of his chip's time clock. If the user's clock is not calibrated, the MCH

010456 generated by the user's device during^communications will contain a null value in the timestamp field. In that case, the décoder box intercepting the communication will be able

Λ to enforce only the Stop Monitoring Date of the warrant by refusing to decrypt after the expiration of the warrant and grâce periods. Then, the décoder box cannot enforce the Begin Monitoring Date because, as long as the warrant is still valid, the warrant allows decrypting of ail MCHs submitted with null timestamp values even if they were intercepted prior to the warrant period Begin Monitoring Date and Time. But, if the user's clock is calibrated, the law enforcement décoder box can and will refuse to decrypt ail MCHs containing a valid and trusted timestamp for a date and time prior to the warrant Begin Monitoring Date and Time. Most preferably, the décoder box of the présent invention will decrypt only communications that are reliably timestamped during the warrant time periods. It is anticipated that this added immunity from potential abuse of warrant time periods by law enforcement may motivate users of the chip of this invention to maintain their chips in a calibrated state. Indeed, where the system is used to encrypt large numbers of messages in a data storage system, the enforcement of time periods for a later warrant or discovery order may be highly désirable, because otherwise many messages outside the lawful scope of the order might become subject to inspection.

Law Enforcement Auditing Features

With an escrowed encryption system, there is a concern that law enforcement agents might be easily bribed in order to obtain cryptographie keys that protect data of high économie value. For example, members of a well-funded criminal enterprise might be able to steal a set of valuable industrial plans from a particular company, first by illegally tapping that company's communications in order to obtain some message headers and escrow agent names, then by bribing a low-paid police official to request a warrant for a drug investigation in order to obtain the company's

010 456 private decryption key from the escrow agents, and finally by using the private decryption key to steal the plans. Because encryption is now used for secure communication between many computers, it is no longer acceptable for law enforcement to wiretap a télécommunications system with minimal safeguards. A much stronger set of safeçruards is needed in order to bring police procedures and centrais up to the level of modern corporate computer security practices and prevent this type of situation fron occurring.

One such safeguard for the trusted device is an internai counter for numbering each message control-header, which counter will increase sequentially after each access. The message sequence number (MSN) can be placed in each message header encrypted so that it would not be visible to an outsider. This can be done by encrypting the number either (1) under the sender's public encryption key, along with the sender's copy of the message session key, (2) under the public encryption key of the escrow agent of either the sender or the récipient, or (3) preferably under at least the sender, receiver, and their escrow agents, and possibly under ail parties in the community of interest. However, the sender's escrow agent could also, as a natter of policy, elect to allow the sequence number to be displayed in the clear, on the grounds of economy of space and the low risks of exposing it. It is critical to avoid

Λ duplicate numbers of message control headers, and gaps in numbering should also be avoided to the extent possible.

Another safeguard feature might be to allow the user to include an optional secret title line in the message control header. If a user feared illégal tapping under improper warrants, the user could encode a short title, such as Plan #123, in order to alert himself and others to the contents of the message. Altematively, a user could simply keep his own log (through a mail software system) relating the device-assigned message sequence numbers and the user-assigned titles. In order to save

010456 space, the title line would be of length zéro if no title was entered, as would often be the case.

A third protection is to add to the signed portion of the message control header a digest or hash of the message 5 contents in order to prevent either the user or law enforcement from later claiming that the contents of the decrypted message were other than as actually sent. That is, for example, the user could not later substitute a harmless message for the drug deal message that had 10 previously been sent, nor could corrupt law enforcement officiais later substitute a drug deal or harmless message for the valuable industrial plans the officiais werê stealing.

These safeguards could be used as additional security 15 measures. First, the sender device-generated message sequence number would be used to track the message, by both sender and receiver, as well as by law enforcement and the court system. Although law enforcement access may be difficult to effectively control, especially during the hot 20 of pursuit of criminals, and although the court system may not always be able to carefully analyze law enforcement requests prior to issuing wiretap authorizations, diligence after the fact can be exercised in order to audit the results of a wiretap, either of every wiretap, of a random 25 sample of wiretaps, or of wiretaps that in some way appear unusual. The trusted device of the law enforcement agents, the décoder box, is therefore modified to include a secure internai log of the message sequence numbers and message digests (and title lines, if any) of the messages that it 3 0 has monitored and allowed to be read by law enforcement.

The electronic authorization sent to the décoder box by the escrow agents of a wiretapped user with that user's key splits may also include the public encryption and signature keys of the court that issued the warrant. The décoder box 35 is then able to respond to a request to print out the log of message sequence numbers and title lines, possibly encrypted under the key of a suitably authorized récipient such as the court that issued the warrant.

010456

In another embodiment, the décoder box will not start to decrypt the monitored communications until it receives a spécifie court order that matches the key splits received from the escrow agents. For example, the key split messages that are received from the escrow agents and encrypted using the décoder box's public encryption key can be enhanced to include (from each escrow agent) the public encryption and signature keys of the court that issued the warrant. Or, the escrow agents might refer in their key split messages to the date and number (if any) of the warrant, and the décoder box might then receive from the court the court's public encryption and signature keys, as well as the court's public key certificate that had been attached to the original wiretap authorization. For example, the court authorization to the escrow agents can be enhanced to convey the following data, which is needed for the key split message:

Master Escrow Center Name or ID Number

Monitored User's Certificate Number

Court Name or ID Number Warrant Number (if any) Date and Time of Warrant Begin Monitoring Date and Time Stop Monitoring Date and Time Maximum Number of Messages (optional) [Judge Signature] Judge Certificate

Judge Certifier Certificate (e.g., court, etc.)

The escrow agents could then recertify the court's public encryption and signature keys to the décoder box by having the encrypted key split messages from the escrow agents to the décoder box include the following additional information, which must be présent in each key split from each escrow agent:

Master Escrow Center Name or ID Number Monitored User's Certificate Number Escrow Agent Name or ID Number (sending this key split message)

Ο456

Court Name or ID Number . Court Public Encryption Key Court Public,Signature Key Warrant Number (if any) Date and Time of Warrant Maximum Number of Messages (optional) Escrow Agent Signature [Escrow Agent Certificate]

The décoder box thus receives the assurance that ail the key split messages came from the same judge and the same warrant.

The fact that décoder box also has the judge's public encryption and signature keys allows the judge to request and receive (in confidence) the log of ail message sequence numbers and message title lines intercepted and decrypted by the décoder box during the wiretap period, as a postwiretap audit to safeguard against unjustified, unlawful or corrupt conduct of law enforcement agents. Furthermore, the décoder box will not delete, erase, or reuse any memory assigned to the monitored message log until the décoder box receives a separate order from the judge or court, verified against the previously received public signature key, stating that the décoder box may do so. Such an order will be issued either because the court has already received from the décoder box the monitored message log that it previously requested, or because the court has decided that no audit is needed in this instance. If the monitored message log memory storage area becomes full, the décoder box will not decrypt any more messages until the log is sent to the judge or court and an order signed by the court is received allowing the décoder box to erase the monitored message log. Law enforcement can continue to intercept new messages pending clearing of the monitored message log, although the new messages will not be decrypted until the full message log has been cleared for audit. The décoder box will also hâve a feature alerting law enforcement that the monitored message log is nearing capacity, so that they can request that the message audit log be uploaded so that

010456 the décoder box will not cease decrypting. These transactions and communications may be fully automated and nearly instantaneous.

Each entry in the audit log may contain, in addition to a digest of the message, a second digest that is the product of (a) the message digest plus (b) the full text of the previous log entry concatenated together and redigested. This can prevent any dishonest court personnel from adding, deleting or resequencing the entries in the log. This concept is discussed in U.S. Patents Nos. 5,136,646 and 5,136,647, which are hereby incorporated by reference.

As a followup action, the court could later request that law enforcernent submit the message headers and the full content of the message digests in the audit log that the court has received. Also, in its wiretap authorization, the court could artificially limit to less than full message log capacity the number of monitored messages that may be decrypted by the décoder box before the monitored message log and message headers must be audited. Although this type of limit would hâve no effect on the overall ability of law enforcement to investigate, because downloading of the log to the court for auditing is almost instantaneous, it might alert the court to unusual circumstances. In spécifie cases that require controls that are stronger than merely sending the monitored message log to the court, the court might limit law enforcement to less than full message log capacity before law enforcement must seek a new warrant to monitor additional communications.

Thus, if (1) both sender and receiver keep track of the sequence numbers of the messages they send and receive, and either associate title lines in the message control headers or log the messages in their local software Systems, (2) both law enforcement and the court retain a complété log of each message decrypted by law enforcement, and (3) each message header includes a digest of the message in order to prevent any party from later altering

010456 €4 the message to cover up its actions, ..then a crédible posttapping audit can détermine whether there might hâve been any abuse or corrupt action by the law enforcement agency. Although this system still cannot prevent, a priori, the stolen plan scénario mentioned above, the knowledge by the criminal enterprise that its actions can be fully audited by both the court and the subject users can provide a worthwhile check on improper police actions. It might also be made a matter of régulation that the law enforcement agency record and submit to the court ail messages intercepted under a warrant and allow the wiretapped parties to request an audit of the wiretap, particu-larly where the subject is associated with a business enterprise and no criminal charges are filed based upon that wiretap.

Stream-Oriented Data

In communications involving stream-oriented data, such as a téléphoné call, in which each communication consists of a stream of several message packets from two or more users, it is impossible for the sender device to hash and sign the entire message as part of the MCH. Although it might be possible to send a MCH with each packet of a communication, doing so would be very costly in tenus of processing time and network bandwidth. Hence, the MCH should thus be transmitted only once, at the time of call setup. A preferred way to handle continuons streams of encrypted data is to designate the calling user as the sender·' and to negotiate the MCH at the start of communication, as before, including the message sequence number (MSN) and hash of the first packet (if any) signed by the device. Then, the sender⁷s device could generate a sériés of unique packet sequence numbers (PSN), whose sequence begins with zéro at the start of each communication. For ail subséquent packets, the device needs only to hash and sign that particular packet, and to include (and sign) the hash, MSN (same for entire message) and the PSN for the packet. The callee will perform similar actions for each packet it sends, by referencing the caller's MSN for the

Ü 456 communication, seguentially numbering. its own packets starting with zéro, and having the callee device sign a group consisting of the packet hash, the caller's MSN and the callee⁷s PSN, thereby forming a packet control header 5 (PCH). The devices might optionally include the current time as an offset from the time start of the communication (in seconds or milliseconds), which is already présent in previously disclosed versions of the MCH. This could enable the call to be replayed more realistically.

In order to further distinguish the caller's and callee⁷s packets after the communication, it will also be désirable to include a call party code (CPC) with a simple coding scheme assigning numbers to the parties to the communication, such as caller=0, callee=l, and any additional parties to the same encrypted session receiving higher numbers. Or, in place of the CPC, a unique identification number, such as the device serial number, the device serial number plus the device manufacturer ID number, or the hash of the foregoing, may be used.

These methods could also be generalized as a method for multi-party session key génération. For example, a caller could generate a session key and use that same key to initiate calls with several callees simultaneously using RSA key transport. There will then be a separate MCH for each added party after the first two parties (caller and callee). The caller's device could treat the multi-party call as separate calls or as a single call having the same session key but having multiple CPCs. Each callee would then be responsible for using the caller's MSN and for maintaining its own CPC and PSN. Alternatively, assuming use of conventional two-party session key génération methods (such as Diffie-Hellman methods), conférence calls could exist in which a central party (e.g., a system operator) places ail the calls and performs real-time decrypting and re-encrypting of each party⁷s packets for ail the others. The central party could also be the individual who patches in the next callee, in which case that callee⁷ s packets would be decrypted by that

010456 individual's device and then re-encrypted using the session key(s) that the callee is using to communicate with the other party (or parties). See also B. Schneier, Applied Crvptographv, J. Wiley 1994, p. 276, regarding use of Diffie-Hellman with three or more parties.

A Packet Control Header (PCH) could be formulated as follows:

Original Caller's MSN

User Call Party Code (CPC) (caller=0, etc.)

User Packet Sequence Number (PSN) Time Offset from call setup (msec) Hash (of this packet) [Device Signature]

It might be préférable not to send a PCH with each packet of communication, due to resulting heavy overhead in some systems that use short packets, but rather to send the PCH only periodically. This is akin to the technique known as “sliding Windows in network communications, in which packet sequencing and retries are not performed for each packet but only for large numbers of packets. Usually such systems dynamically adjust the “window, or the number of packets that are sent between error checks, based on line noise, i.e. making the window large for a clear line but making it small for a noisy line that is causing many error retries. If errors occur often, a small window would require the user to resend only a small amount of data; if errors are rare, checking can be performed infrequently, albeit with a high cost to resend lost data in case of an error. Packet control headers could be directly integrated into the sliding window scheme of a communication system, thereby providing the desired capacity to audit law enforcement actions down to the packet level, while also allowing maximum system throughput in a modern communications network.

To further strengthen the auditability of the wiretap process, it is advantageous to positively mark the end of a communications session with some spécial packet. This tr

010456 packet may be sent automatically by çach device to the others prior to disconnecting, unbeknownst to the users, in order to prevent either the users or law enforcement agents from later claiming that a conversation either had or had 5 not ended, when the opposite in fact occurred. This could be accomplished by instructing each device to accept a ”want to hang up now input from its human user, whereupon the device would send out a préparé to disconnect packet, which would then stimulate the other device(s) to do the 10 same. The device(s) would terminate their data streams with a final packet containing no additional data but preferably inciuding the totals of ail packets sent- and received, call duration, etc.

Timestamp Device

Another feature of this invention in its preferred embodiment, as discussed above regarding the décoder box, is a trusted and tamper-resistant timestamp device that self-certifies that it can issue (or affix) digitally signed timestamps (or data structures containing such timestamps) that can be considered trustworthy by third parties. Such timestamp devices are described in U.S. Patents Nos. 5,001,752 and 5,136,643, by Addison M.

Fischer. In its preferred embodiment, shown in FIG. 21, the timestamp device 210 (or subsystem) can be calibrated 25 and set into operation only by a trusted authority, such as the manufacturer or one trusted by the manufacturer, in much the same way that a postage meter can be set only by the local United States Postal Service branch office and is from then on trusted by the public and the postal system to 30 dispense postage-meter stamps only up to the prepaid amount. Once calibrated, the timestamp device 210 (or subsystem) will respond to a time-set instruction 211 (or recalibration) only if that instruction is signed either by the manufacturer itself or by an entity that has attached a 35 certificate 212 from the manufacturer, or one trusted by the manufacturer, stating that the entity is trusted to set and calibrate the timestamp device (or subsystem) of the

Û1U456 «B host device. The time-set instruction operation would probably need to be perforated in person with the time setting authority taking momentary physical possession of the device and immediately erasing the time-set instruction 211 in order to prevent the possibility of a device owner capturing the instruction and replaying it at a later cime in order to “back-date a device * s clock.

Once calibrated and for as long as it is undisturbed, the timestamp device 210 will affix timestamps 21~ cr complété timestamp data in structured data fields baseà upon its internai clock mechanism, signing 214 the resulting data structures with its private device kèy and furnishing its manufacturer certificate 215. If the host device should lose power, be tampered with or receive an instruction to deactivate itself, the timestamp device will cease issuing timestamps. In that case, in order to avoid. impairing other possibly useful functions that do not as an absolute matter require trusted timestamps, the timestamp device will utilize a convention, such as filling the timestamp field with a pre-agreed “null value, such as ail binary zéros or binary ones (or an équivalent convention), when a structured data field calls for a timestamp to be entered. However, when a structured data field or the host device requires that an actual timestamp be issueâ, such as in the case of a law enforcement décoder box, if rhe timestamp device has ceased to issue timestamps, the host device functions that require timestamps will not operate; in the case of the décoder box, the box will refuse te decrypt intercepted communications. In order to avoid or minimize the occurrence of the situation of lost host device power, each trusted timestamp device should preferably be equipped with its own separate long-lived battery 216 for clock use only, some “low battery warning indicator to prevent timestamp device loss of power before a battery change and some means of retaining an adéquate electrical charge (such as a storage capacitor, a second battery compartment or an optional external power supply) during battery change operations.

010456

For each timestamp issued by the timestamp device, there could be a timestamp device certificate issued by the manufacturer (or another time-setting authority) stating the quality and reliability of the timestamp clock, the date on which it was last set, as well as its expected time drift. When a récipient user receives a data structure that has been digitally signed by the host device, that récipient knows that, if the timestamp field is completed with a valid value, the device's signature and certificate certify that the time was correct when the data structure was created, signed and issued. This certification is based on (1) the trustworthiness of the authority that most recently calibrated the timestamp clock, (2) the clock's drift tolérances as stated by the manufacturer in the device certificate, and (3) the clock's ability to deactivate itself upon tampering or a loss of power. The récipient further knows that, if the timestamp field contains a null” value, then the timestamp clock was not in a state of trusted calibration at the time the device created, signed and issued the data structure. This information concerning the trusted properties of the timestamp device and its internai clock mechanism can be preferably encoded directly into the device certificate using a suitable attribute-value coding scheme. However, this information could also be implied from the manufacturer name and device type, which could be published by the manufacturer in a spécification and performance certification as part of a publicly stated policy statement at the time the device certificate is issued.

Such timestamps could also be issued by the device as part of other message handling operations beside MCH création and decoding. These timestamps could be attached to the personal signature of the device's user when the user signs another document or transaction using his Personal signature key, which is securely confined inside the device. The device would sign or co-sign the timestamp element of the user's signature, or might altematively sign over the user's entire signature block (which

010456 contained the timestamp, also signed^by the user, along with the hash-result message digest of the document). The device could then supply its certificate in order to make the timestamp believable and trustworthy to a third party who knows the manufacturer's public key.

Trusted Upqradinq, Replacing and Rekevinq

Another feature of this invention is a tamper-resistant trusted device that contains an embedded manufacturer 's public key, a protected non-volatile memory area and a secure central processor unit (CPU) and can upgrade or supplément in a trusted manner any firmware rcut'ines embedded by the manufacturer. The trusted device does the upgrading or supplementing by accepting as input a body of data containing new or additional firmware code that is suitable for that type of device and is digitally signed with the manufacturer's signature, which signature assures the device that the new firmware code has been developed, tested and approved by the manufacturer and that the device should therefore either (a) overlay one or more currently embedded firmware routines with the new firmware code or (b) add the new firmware code as one or more new routines in a currently unused area of protected memory. In the preferred embodiment, the protected memory would be of the FLASH type, which can retain its information indefinitely while powered down but can also be erased by the device (albeit, relatively slowly) and reused if desired. The protected memory could also include any data storage area (such as a disk drive), whether or not tamper-resistant, in which the code to be upgraded or supplemented could be stored in an encrypted form for which the decryption key is known only by the trusted device. By storing the programs in an encrypted form, the device effectively prevents them from being modified by anyone without knowledge of the decryption key. When the device receives such a signed body of new firmware (or software) code, the user inputs the code along with the manufacturer's signature and issues a process firmware upgrade'· instruction to the device.

010456

The device then vérifiés the manufacturer's signature using the public signature key of the manufacturer, which was embedded in the device during manufacture. If the

Λ manufacturer's signature vérifiés, the code is accepted and the device perforas the desired upgrade.

The process of a trusted upgrade to the firaware of a trusted device as described above can be further extended to accommodate authorized third parties that desire to upgrade firaware routines that pertain to device functions relevant to those third parties, including functions such as the présent key escrow systern, which may be largely designed and administered by a bank master escrow center independently of the trusted device manufacturer. In an instance of third party upgrade, the manufacturer could sign a firaware upgrade certificate containing a public key of the third party firaware provider and issue it to that third party. The third party could then develop, test, and approve replacement or additional firaware routines, sign them with the third party's private signature key, and attach its upgrade certificate from the manufacturer thereto. Upon receiving such an upgrade, the user would load both the signed code routines and the manufacturer' s upgrade certificate into the device and then issue a process third party firaware upgrade instruction. The device would then verify the third party's signature on the new code routines against the manufacturer's upgrade certificate and then verify the upgrade certificate against the manufacturer's public signature key that was embedded in the device during manufacture. If both signatures verify, the upgrade is accepted and the device perforas the desired upgrade.

In addition to accepting instructions to upgrade or supplément device firaware routines, a tamper-resistant trusted device can also accept instructions to replace or supplément instructions public keys that were embedded during manufacture. As discussed earlier, a trusted device may hâve public keys besides those of the manufacturer embedded during manufacture of the device. Such

010456 instructions public keys might include those of one or more master escrow centers as described in the presenr invention. These embedded keys, including those of the manufacturer or other trusted third parties, can be used to 5 verify various certificates such as escrow certificates, device certificates, upgrade certificates, time-set instruction certificates and others that may be presented to the device for it to act upon. In addition to relying only on public keys embedded during manufacture, the device 10 can also accept external instructions to embed new public keys or to replace existing ones. In order for a device to accept and store in a non-public area the public signature key of a trusted third party, the manufacturer will enclose the new public key in a signed instruction data packet (or 15 certificate) signed by the manufacturer instructing the device to discard the enclosing certificate and store the designated public instructions key within. The spécial packet may also instruct the device as to what types of transactions the new key is trusted (e.g., for use with a 20 key escrow application, car rental application, médical data application, or other use). Upon receiving such a public key data packet from the manufacturer, the device would first verify the manufacturer's signature and then accept and store the new public key along with the 25 restriction on the public key⁷s use.

The manufacturer may also designate at the time of embedding a third party public instructions key, either during manufacture or later as part of an instructions data packet, that one of the transactions for which that third 30 party key is approved is the replacement of the manufacturer ⁷ s own underlying public signature vérification key. Although such a replacement of the manufacturer' s own public signature key should almost never be required, there is the chance that the manufacturer⁷ s corresponding private 35 signature key (for issuing device certificates and other instructions to the device) might be compromised through theft. Theft of the manufacturer⁷s private signature key would allow the thief to issue seemingly valid instruc73

010456 tions, to approve new escrow centers^(of dubious trustworthiness) and to approve new time set authorities. Altematively, and more likely, the manufacturer's private signature key might simply be lost or destroyed, thus preventing the issuance of any further valid instructions. Either of these events would be classified as a disaster in computer Systems terms and could resuit in ail of that manufacturer's devices having to be recalled. However, through the present invention, the expense of such a recall could be prevented or mitigated by allowing a trusted third party to replace the manufacturer's compromised signature key. Assuming that the manufacturer had already embedded the instructions keys of one or more trusted third parties into the device, either during manufacture or later using an instructions data packet, and had included the replacement of its own public key among the transactions that the third party's public instructions key could approve, the manufacturer could then turn to that trusted third party and request that it issue an instruction data packet to ail of the manufacturer's devices authorizing the replacement of the manufacturer's public signature key, thus saving itself and its users the potentially huge expense of physically replacing ail the physical devices. Because ail the device certificates issued by that manufacturer would also hâve to be replaced, this could be accomplished by having each device issue a certificate request for the device's own public device signature key. If the manufacturer's private key was lost or destroyed, and not compromised, then ail previous signatures would still be valid and a user would need only to present his old device certificate in order to hâve a new device certificate issued for the same information signed by the manufacturer's new signature key. The manufacturer would then return new device certificates (most likely via an on-line or an electronic-mail transaction). While this would still be expensive, it would be far cheaper and less detrimental to the réputation of the manufacturer than the wholesale

01Ü456 physical replacement of ail of that manufacturer's trusted devices in the field.

The incorporation, into the trusted device ef the présent invention of a mechanism to replace a manufacturer 's public key or any other trustée public instructions key could mitigate some of the systemic security risks that are posed by the use of system-wide root public keys. This would allow greater reliance upon purely hierarchical trust models, which generally allow shorter and simpler certification paths requiring fewer certificates, less effort to détermine which certificates to utilize and less computational time to verify the signatures.

Owner-Controlled Rekeyinc

As previously described, the user also has the option of rekeying his device as to its user encryption key pair at any time after manufacture. The user does this by issuing a firmware instruction to the trusted device to perform the particular steps of the key escrow method, i.e. to generate a new private and public encryption key pair, send the key splits to the escrow agents and ultimately receive a new escrow certificate from the master escrow , center. However, it is also désirable to permit a user's employer or sponsor (or owner, if the user is another device or process) to control the key and rekey processes in order (a) to make sure that the user selects escrow agents that the employer deems acceptable and (b) to assure that the employer, as the true owner of the device, will remain known to those selected escrow agents and hence will be able to request the user's key splits from the escrow agents without having to first obtain a warrant or court order. The employer may require access to a particular device's keys for any number of reasons, such as to conduct internai surveillance or to recover encrypted proprietary data after the relevant device has been lost, stolen or destroyed. The employer may also need to rekey the device for any of a number of reasons, such as for a device whose previous encryption or signature keys hâve been compromised

010456 or erased, for a device that has been given to a different employée, or for a device whose owner-organization rekeys ail cryptographie devices at periodic intervals as a matter of policy.

In the preferred embodiment, the trusted device is pre-set by the manufacturer such that it will not initiate the key génération and escrow process uniess the device first receives an owner's certificate for the device 220, such as one shown in FIG. 22, containing the particular device's permanent serial number 221 and signed 225 by the manufacturer. The owner's certificate 220, issued at the time of purchase by the manufacturer to the corporàte purchaser of the device, also contains the corporation's name 222, the corporation's unique identification number

223 (such as Internai Revenue Service Employer Identification Number (EIN) or Dun & Bradstreet Number (DUNS)) and the corporation's public signature vérification key 224, which corresponds to the private signature key retained by the corporation and which will be used to verify rekey or other instructions issued by the corporation to the device. Subséquent to receiving this information, the device will respond only to rekey or other instructions that are signed using thé corporàte owner's private signature key corresponding to the public key contained in the device's owner's 25 certificate.

Referring now to FIG. 23, when the employer (the owner of the device) desires to rekey the device 230, the employer issues a signed instruction 231 to the device 230, including (1) the device's serial number 232, the unique owner identification number 233, (2) the names of the escrow agents 235 and the master escrow center 234, (3) the date and time of the rekey instruction, (4) the date and time of the rekey instruction expiration 236 and (5) the rekey instruction unique serial number 237, and signs the instruction using the employer's private signature key 238. Upon receipt of a valid owner's certificate 239 and a valid rekey instruction 231, the chip within the trusted device 230 first vérifiés the manufacturer's signature on the

Ίί

l) 1Ü 456 owner's certificate 239 and the employer's signature on the rekey instruction 231. The trusted device then complétés the key génération and_ escrow process, as before, including the owner's unique identification number 233 within each 5 escrow share packet, and sends the share packets only to the escrow agents 235 designated by the employer in the rekey instruction 231. Subséquent replay of these instructions (which may be issued electronically) can be limited by designing the device so that the device retains in non10 volatile storage the serial numbers of the last several rekey instructions it received and refuses to execute the instructions again. Assuming the device's time clock is maintained in good order, subséquent replay of the rekey instructions can also be limited merely by instructing the 15 device's time clock to honor the expiration date and time in the instruction. In a preferred embodiment, a device whose clock is uncalibrated would refuse to process a rekey instruction that has a non-null expiration date/time but would proceed if the expiration date/time were left null.

Upon receiving from a user device the key (or rekey) split share packets containing a unique owner identification number, the escrow agents and master escrow center would record that unique identification number in their respective databases and would subsequently honor requests 25 from that owner for access to the private encryption key.

In a preferred embodiment, the escrow agents and escrow center would each require that a key split share packet that désignâtes a unique owner identification number must also be accompanied by the respective device owner 30 certificate signed by the manufacturer. This device owner certificate would allow the escrow agents and the master escrow center to act upon key request messages signed with the owner's private signature key corresponding to the owner's public key in the device owner's certificate.

In another embodiment, the trusted device can be allowed to accept rekey, reescrow, ownership transfer or other instructions from the device owner without having to use a separate device owner's certificate. The requirement

010456 π

of having to use a separate owner's certificate for instructions to the device is an administrative burden, because the owner must maintain a database of certificates for ail its owned devices and locate the appropriate certificate each time it wants to rekey a device or send the device some other instructions. A better approach, as shown in FIG. 26, is to hâve the manufacturer issue the owner a single certificate for the owner's public instructions key for a given family of devices, let the seller install its public instructions vérification key 261 inside the device 260 when the device 260 is sold, and then institute a system based on the internai storage of those keys. Upon initial sale of the device by its manufacturer to an owner, the device 260 will first verify the validity of the owner's manufacturer certificate 262 using the manufacturer 's public instructions key 263 that wad embedded within the device by the manufacturer. If the owner public instructions key area 264 within the device is blank, the device will copy the owner's public instructions key 261 from the owner's manufacturer certificate 262 into the owner public instructions key area 264 of the device. If an owner public instructions key already exists in the device and is different from that of the owner attempting to initialize the device, the device assumes that the manufacturer has sold the device to another entity. Because each device will hâve at most one primary owner, ownership of that device will be determined by the presence or absence of an owner's public instructions key 261 inside the device 260, in lieu of (or in addition to) the prior concept of an owner's certificate.

If no owner public instructions key is installed, the device is considered to be a single-user consumer device that is unrestricted with regard to rekeying or ownership transfer of the device; as such, the device will consider 35 the non-existence of an installed owner's key as a signal to obey the user's instructions without invoking the rekey, reescrow and ownership transfer rules discussed above. If an owner public instructions key 271 has been installed

010456 within the trusted device 270, as shown in FIG. 27, then user rekey, re-escrow and ownership transfer instructions 272 will not be procesped unless those instructions are signed 273 by the corresponding owner private signature key 274. Once the owner's signature 273 has been verified, the trusted device 270 perforas the steps of the re-escrow procedure, as described previously. Thus, the owner need not append an owner's certificate proving his ownership of a given numbered device when instructing that device. However, the owner's signed instructions must of course be limited to a numbered device or perhaps to some class of devices whose device numbers confora to a given rule or template, in order to prevent the instructions from being fed into every device owned by that owner.

In addition, as shown in FIG. 28, the owner can send an instruction to transfer device ownership by replacing the originally-installed owner public instructions vérification key with another (from the buyer, the new owner of the device). The device owner sends an ownership transfer instruction 282 to the device 280, including the new owner's name and public instructions vérification key, signed using the current owner's private instructions signature key 283. The device vérifiés the ownership transfer instruction 282 using the current owner's public instructions key 281, replaces that key with the new owner's public instructions key 284 and thereafter responds to instructions only from the new owner. In addition, the owner could also add another secondary owner by installing a second public instructions key. This second public instructions vérification key would hâve a rights field, indicating for which operations it is authorized to accept instructions. Among those rights might be: rekey, addition of another owner, délétion of an owner (same as a conditional sale), délétion of ail owners, and reverting back to a consumer device having no stated owner. However, these defined rights may include more or fewer rights than, or the same amount of rights as, the original or primary

010456 instructions vérification key, including the right to replace or remove the primary owner instructions key.

Λ

Generalized Device Registration

Note that the foregoing general methods for escrowing a private decryption key and receiving an escrow certificate can also be applied to the more general case of registering a trusted device with a trusted third party and receiving an authorization from that third party enabling the device to communicate with other trusted devices, not necessarily limited in scope or purpose to the key escrow situation. In this general process, depicted in FIG. 24, a programmable trusted device 240 that communicates with a trusted third party (TTP) 241 is equipped with a private signature key and a manufacturer's certificate 242 for the corresponding public signature key. It also contains secure copies of the manufacturer's and systemwide (or global) authority's (SWA) public keys, which could be the same, and secure system-level firmware that can support the remote installation of additional application-level firmware and related public keys, as discussed elsewhere in this disclosure. The device 240 can register with any one of a potentially unlimited number of TTPs 241 that are admitted into this general registration system by having been issued a certificate of authority 243 signed by the SWA (the SWA could also appoint an additional tier of certifiers to authorize TTPs to be admitted to the system, in accord with well known principles of public key certification hiérarchies). Once users hâve registered their devices with a given TTP, they can then engage in specialized transactions with other trading partners.

In the first step of this process, the user initiâtes a request 244 to register his device 240 with a given certified TTP 241. This request 244 contains some information 245 to identify the user and the nature of the registration request and is signed by the device and accompanied by the manufacturer's device certificate 242 in order to vouch for the signature and the known type of the device.

010456

The seiected TTP 241 may also requestr other information and assurances from either the user or from other parties to verify the user's iden^ity, affiliation, creditworthiness, etc., which are outside the scope of this protocol but may influence the TTP's decision to grant or deny the desired authorization to perfora transactions. The TTP 241, using the appropriate public keys, vérifiés the manufacturer's signature on the device certificate 242 and the device signature on the information 245 in the user⁷s registrauion request 245.

When satisfied that the user can be peraitted to engage in the requested class of transactions, the TTP 241 then issues a response 246 containing a certificate 247 specifically authorizing the device to perfora those transactions on behalf of the user. The TTP's device authorization certificate 247 will typically contain information identifying the TTP, the user, the user⁷s device, and the transactions for which permission is granted, as well as a recertified copy of the user⁷ s device public signature key as a matter of convenience (and as later discussed) so that the user need not submit his device certificate 242 in each subséquent transaction with trading partners. The TTP response 246 may also contain downloadable firaware and or public keys 248 to be loaded into the user⁷s trusted device to enable it to perfora the authorized transactions. Where the TTP response 246 calls for the user to securely load new firmware or public keys into^- his device, the response 246 will also include the TTP⁷s certificate of authority 24 3 issued by the SWA certifying the TTP⁷s public signature key and conveying firaware and public key upgrade authority. When the user's trusted device 240 receives the TTP⁷s response 246, it uses its embedded SWA public signature key to verify the TTP⁷ s certificate of authority 243 and uses the TTP public signature key contained therein to verify the firmware and public key upgrades 248 and the TTP⁷s device authorization certificate 247.

010456 βι

Referring again to FIG. 24, when the user wishes to perfora a transaction with a trading partner 250, its device will foraulate .the transaction data 249 in accord with the rules embodied in the firaware program installed on the device (either at time of manufacture or upon subséquent downloading), as has been extensively discussed throughout this disclosure, and will sign the transaction 249 and attach a certificate for its corresponding public key. This certificate could be the manufacturer's device certificate 242 but will more likely be the TTP's device authorization certificate 247, which contains a copy of the device public key recertified for convenience. The’ trading partner 250 will typically utilize the public key of the TTP to verify the TTP's signature on its device authorization certificate 247 and then use the device public signature key contained therein to verify the device's signature on the transaction 249, thereby confiraing the device's compliance with the transaction protocol requirements imposed by the relevant firaware. In the event that the trading partner 250 does not already hâve the spécifie TTP's public signature vérification key, the user can include in his transaction 249 the TTP's SWA certificate of authority 243, which the trading partner can verify using the SWA public key, which it must already possess in order to be a participant in this system.

The generalized process thus far described is general enough to allow (a) the escrowing of a private encryption key in return for an escrow certificate signed by an escrow center (TTP), where the information contained or implied in the user device certificate conveys to the escrow center that the device is already equipped with firaware that is capable of perforaing the specialized functions of the herein-described key escrow encryption system, or (b) if such device is not so equipped but is capable of becoming so equipped, the downloading of a secure software upgrade that upon installation will enable the device to fulfill the escrow system transactional requirements. The transaction data 249 sent to the trading partner 250 can be an û1ù 45 6 encrypted message prefixed by a message control header and accompanied by an authorization 247 (the user's escrow certificate) , as issued by a TTP 241 (the master escrow center).

The generalized system of FIG. 24 therefore possesses many highly désirable properties which can facilitate complex forms of business and government transactions in open communication network environments. In particular, there can be many different device manufacturer s, as long as each participating device is able to execute secure multi-step transactions, download firmware to perfora additional types of secure multi-step transactions, and sign the transactions so created. Also, there can be any number of trusted third parties, each issuing a different type of transactional authorization and each creating and certifying a different class of firmware application, such as key escrow, digital cash management, car rental or user medical records management. Thus, although a trading partner may be required (by the user device's firmware and protocols) to utilize a comparably equipped trusted device, that device may be made, issued and equipped by different parties than those of the original user, yet the original user's transactions will still be accepted and processed in accord with the system rules, so long as the partner possesses a copy of the SWA public signature vérification key 247, which enables ail versions of the devices and their programs to recognize each other and work together, if so certified by the SWA and its TTPs. Some examples of business purposes that can be fulfilled by this protocol include Systems that enforce transactional requirements for (a) encryption using provably escrowed keys, (b) management of digital représentations of cash or other high-value documents, and (c) access to and use of medical or other Personal information of the user.

Unique Owner Identification Number

Depending on the need to balance ease of use with privacy rights, the unique owner identification number may

010456 also optionally appear in either (a)-the user⁷s escrow certificate or (b) MCHs issued during normal communications, as well as in the key split messages to escrow agents. It would be désirable for an investigator attempting to decrypt communications to be able to détermine by looking at a MCH containing the owner identification number whether one or both of the devices involved in the communication from which the MCH was taken belong to a given owner. However, other privacy interests, including those of certain owners, might suggest that the owner identification number be omitted from the MCH in order to enhance the privacy of communications. In cases in which the owner identification number is included only in the device escrow certificate and not in the MCHs of communications, an investigator, hired by a particular employer in an attempt to détermine whether a particular communication originated from employées of that employer, confronted with many MCHs that hâve no listed device owners, would inquire of a master escrow center listed in a given MCH whether that MCH originated from a device owned by the employer. The master escrow center would decrypt the certificate number of the party to the MCH communication whose keys are escrowed with that master escrow center and check whether that user certificate was issued to the investigator⁷ s employer. If so, and if the investigator's request is signed using the employer-owner's signature key (i.e., the investigator has authorization from the employer-owner to investigate), the master escrow center would reveal this information. If the investigator has no authorization, the investigator would then be required to seek a warrant or court order to investigate suspicious activity reflected in MCHs of unknown device owners. It is anticipated that most device owners will not object to being openly named in their user⁷s escrow certificates and MCHs, because in most electronic communications Systems it is impractical to suppress the physical and logical network address information that often strongly identifies the sending and receiving institution of a given message. Thus, little is

011)456 lost by publicizing the unique owner aident if ication numbers, and much is gained by providing the ability to quickly sift and sort messages by sender device owner and récipient device owner names.

The unique owner identification number may, however, still be included within the employée's escrow certificate or within the MCHs of communications without being publicized. The employée's escrow certificate and MCHs would include an Employer Public Encryption Key along with the other keys as described above. These keys would normally be présent in both the sender's and récipient's escrow certificates (assuming that both sender and récipient hâve employers). When the sender's device forms the MCH, it will incorporate into the MCH one or both employer unique identification numbers, each encrypted using the public encryption key of the respective employer so that, in effect, the sender's device uses the MCH to send to each employer-owner a message consisting of that respective employer-owner's own unique ID that only it can decrypt. This method is similar to that discussed above regarding the sender's use of the MCH to send the certificate numbers of both the sender and récipient encrypted under the public encryption keys of their respective escrow centers, and to send the message session key to the récipient (the MCH's normal function) as well as to the sender in order to allow tapping of both parties. This technique allows the employer to readily détermine which MCHs belong to its employées, while avoiding a situation in which ail messages belonging to the owner-employer's employées are readily identifiable in the message traffic flow and in which owner ID numbers are unencrypted and readily obtainable.

Still, this approach has the drawback that the unique employer identification number encrypted using the employer public encryption key will always produce the same, and thus recognizable, value. A better implémentation of this approach would be to encrypt a data block containing a current timestamp (or another random number) along with the employee's escrow certificate number (which the employer

010456 clearly has the right to know) under;the employer⁷s public key, so that the timestamp would give high variability to the encrypted data block. Several bytes of a distinct “eyecatcher” text, such as EMPL” (or possibly the employer⁷s unique ID, space permitting) could also be included inside the encrypted block in order to make successful decryption obvious to an entity that is decrypting the field (in. case the other data items are in binary, in which case one might not know for sure) . In this case, proof of the employer⁷s ownership consists of the employer merely being able to read this field. In addition, yet another random number could be added -to the data block for increased variability, in case the timestamp is not sufficiently trusted to be different each time and to therefore make ail employer MCH data blocks unique.

This improved approach, which would be done for the employers of both the sender and récipient with every message that is sent, would make it possible for employers and other sponsors to détermine which communications were generated or received by their employées without having to submit the encrypted MCH for every communication to the appropriate escrow center for a détermination as to whether or not any of those communications originated from a device owned by that employer, thus probably saving a considérable amount of money. Each employer will still hâve to contact the master escrow center and the escrow agents, as before, in order to obtain its employée⁷s private encryption key, and^- must prove that it is in fact the owner of the employée⁷s device by signing its requests with the private signature key that matches the public signature vérification key contained in its owner certificate as issued by the device manufacturer. At least the employers will be spared the time, effort and expense of any additional requests to those parties regarding the MCHs of communications originating from what later turn out to be non-owned devices. And, as before, if an employer suspects criminal or other improper activity in messages accompanied by MCHs from communications by non-owned devices, the employer can

01Ü45 6 always contact an appropriate law enforcement agency, tell that agency why it suspects criminal activity and hâve that agency go to court to obtain a warrant for interception and/or decoding of those communications, which appear to be originated by third party non-employee criminals or, nore likely, by individuals on the employer's prenises, whether employées or not, who are using encryption devices not owned by and registered to the employer.

This method of placing information in the MCH encrypted so that the information can be read only by the party entitled to read it can obviously be extended to parties in addition to the sender and récipient (each of whom can decrypt the message session key), each party's master escrow center (each of which can decrypt its respective user's certificate number), and each party's employer-owner (each of whom can decrypt its employée's certificate number or its own unique owner identification number, so as to ascertain whether it owns the ccmnunicating device without having to contact anyone else, while avoiding being identified on every message). This can also be extended to other parties such as divisions within a very large company or, for example, local law enforcement in certain foreign nations that hâve no warrant requirements. Of course, ail the information encrypted under these keys could also be shown in the clear, i.e. unencrypted, as discussed earlier, providing that these parties hâve no objections to being openly named and routinely identifiable on every message. This information can also be omitted whenever a party is irrelevant, for example when a user has no employer. The simplistic approach would be to use one MCH format for ail situations, leavina fields blank when inapplicable. Otherwise, the preferred embodiment would be to utilize various different MCH formats within the same system, each format being identified by a unique version number in the first field, such that each device processing a MCH would be able to détermine which fields to expect and parse the MCH accordingly. This method would allow for an indefinite nesting of interested parties in the MCH, which would be the most flexible possible system. The computational overhead would dépend mainly r on how many of those fields actually had to be encrypted under each respective party's public encryption key.

An employer can more easily control the information that is included in the MCH by accompanying each entry with a policy field” or an instructions code containing code instructing the employer's device as to what information to include in the MCH. As before, the instructions code could include éléments of choice giving the employer options of including the following information: (1) the employer's name and unique identification number, either encrypted or using an alias; (2) the word employer” unencrypted, with the employer's unique identification number encrypted inside a MCH field; (3) the user certificate number in an encrypted field; (4) the message session key in an encrypted field; (5) a timestamp in an encrypted field; and (6) a random confounder number within any of the other encrypted fields. Many of these options can be in effect simultaneously. In addition, these policy options would be the same for ail members of the community of interest, including the parties to the communication themselves, thereby allowing the parties to be labeled by their mail or system IDs or simply by using the word sender or receiver” in the relevant clear MCH fields.

Multiple Simultaneous Escrowed Keys

In addition to the above-described features for upgrading device firmware routines and for replacing manufacturer's public keys, the trusted device of the présent invention should also hâve the ability to maintain and manage several sets of escrowed encryption keys simultaneously. Normally, when the device begir.s the cycle of rekeying, i.e., generating and escrowing a new private decryption key, and as a resuit receives an escrow certificate for the corresponding new public encryption key, the device will erase the previous private key in order to force reliance of the device on the newly escrowed

010456 private key. Alternatively, the device could retain the previous private key for only a short time as needed, e.g. for the time needed to recover data encrypted into data storage using the previous private encryption key. However, in an alternate embodiment, the device may also accept and process a re-escrow instruction, either from the user or from the device owner as described above, to create a second valid escrow certificate concerning the same private/public encryption key pair. In this embodiment, the device would proceed with the escrow process using quite possibly a different list of escrow agents and a différent master escrow center, and would receive a different-, equally valid escrow certificate for the same public/private encryption key pair that is signed and issued by the second master escrow center and can be used interchangeably with the first escrow certificate. This second public encryption key certificate can be of use in cases in which the device's user travels internationally or corresponds with parties located in other countries, especially when those other nations may desire to conduct lawful surveillance of communications originating or terminating in that other nation. In such cases, by re-escrowing the same device key in another nation, the user (or the user's employer) could help to satisfy possible legal requirements in that other nation, while still allowing the user or employer the convenience of doing business with the original set of escrow agents in his own nation (lawful owner monitoring, recovery of lost key, etc.). Then, in order to allow the owner to track its employées' MCHs, it may be enough if the sender and récipient owner IDs appeared in each MCH, thus telling the owner that it does indeed hâve the ability to obtain the key. To save time and effort, the owner may then send such an MCH to the foreign master escrow center to obtain the foreign escrow certificate number, the underlying device number and the underlying device certificate, but then apply to its domestic escrow agents who can verify the owner's certificate already in their possession and release the actual private key splits.

0456

This procedure relieves the device owner of any extra legal formalities that might be required in order to obtain the actual key splits from the foreign escrow agents.

National Security Export Safeauards

The current policy of the United States government is to allow unregulated use of encryption within the United States by American citizens but to impose heavy restrictions and penalties for the export of encryption devices, software or know-how. It is possible to modify the présent system to allow relatively free private use of cryptographie devices in the United States while simultaneously imposing restrictions on their international use. Such a system could allow separate inter-operable policy domains that are open to ali software and hardware vendors with minimal or no design changes to the standard message formats used throughout the system. It is further désirable to allow the use of private escrow agents in purely intra-corporate, single country situations, in which the key escrow system is being used solely to allow a particular corporation to monitor and control its own employées' uses of encryption, without any obligation, express or implied, to facilitate law enforcement access to communications that have been encrypted using keys the corporation has escrowed. In particular, such companies might buy the software and hardware for their own use but might décliné to assume any public duty to provide access to private keys in short time frames, as might be desired by law enforcement in hot pursuit of criminals or terrorists.

This can be done by first assuming that ail devices throughout the system are linked directly or indirectly to a system-wide authority (SWA) that (as previously disclosed) issues certificates to escrow agents, master escrow centers and device manufacturers in order to enable each to be recognized by devices within the system as being authentic and trustworthy. A national or global communications system must for practical purposes support the existence of multiple and unrelated master escrow centers and agents,

010456 each of which must be certified by tlie SWA as being authentic. In each certificate issued to a master escrow center or to an escrow agent, the SWA will designate it as either public” or private. A public master escrow center or escrow agent is one that is equipped and committed to respond promptly to national security or law enforcement warrants and subpoenas. Users whose keys are escrowed with such agents may be permitted to engage in transborder communications. A private master escrow center or escrow agent includes those single-company or single-country key centers that hâve installed key escrow system technology for their own use but do not undertake any commitment to a public level of service. The certificate from the SWA to the master escrow center or escrow agent will also include a country code. Then, each user's escrow certificate that is issued and signed by a master escrow center and has the master escrow center SWA certificate attached will also carry the user's country code. Note that, as a matter of convenience, the user's escrow certificate should also state that it originates from either a public or non-public escrow agent, although it may not be possible for the SWA to enforce the correctness of that information. This could allow the device to enforce these rules even more easily than always requiring the master escrow center's SWA certificate.

FIGS. 29 and 30 show the enforcement of the escrow requirement when sending and receiving international cryptographie communications. As shown in FIG. 29, the trusted device 290 of the sender enforces this system by requiring the escrow certificates 291,293 of both the sender and the récipient, and, if the sender and récipient are not escrowed with the same master escrow center, their master escrow center SWA certificates 292,294, prior to sending an international communication. The country codes 295,296 of the récipient user and its master escrow center must match in order for a sending device 290 to send a communication. Furthermore, if the sender and récipient are in different countries 295,297 and if either user is

010456 using a non-public master escrow center 298,299, the sending device will refuse to originate a communication to that récipient. As shown in FIG. 30, the récipient trusted device 300 will also enforce this system by refusing to decrypt a communication, if one is somehow originated, in which the sender and récipient are in different countries and if either user is using a non-public master escrow center. These rules will effectuate the desired policy of disallowing unescrowed international cryptographie communi10 cations, because the master escrow center cannot falsify its public status, which is certified by the SWA, and, even if the master escrow center could falsify the user's country code (to make the' user appear to belong in a foreign domain), the devices will not allow a discrepancy 15 between the user's and the master escrow center's country codes. Although these rules do not prevent a user from improperly transporting his trusted encryption device across national boundaries, they do allow easy compliance with national requirements by permitting him to maintain an 20 escrowed key in each nation and to communicate using only the proper key in each policy domain.

Multi-User Device Versions

Another feature of this invention is the ability to initiate and simultaneously manage several different 25 sessions of communications with different local or remote users using the same device. Many larger computers support multiple users who are often simultaneously logged on via terminal sessions but who may wish to initiate encrypted sessions with other entities around the world. However, 30 because it would be highly inefficient to require a separate trusted device for each user session on a shared computer, the trusted device could track the message session key for each communication by storing it along with a unique message sequence number (MSN) for that session.

Then, when any additional message packets bearing that MSN arrive, they could be decrypted, and responses encrypted, without delay. Furthermore, the device could escrow the

010456 private decryption keys of several users while linxing each user private key with a particular user unique identification number and allowing each key to be used only on présentation of some suitable user authentication, such as 5 a password, Smart card, PIN, biométrie, challenge response, etc. By assigning a user identification number and password or the équivalent to each public/private key pair as it is generated for escrow, the usual controls on passwords, such as length, expiration, retry lockouts and ease 10 of guessing, could then be imposed by the device in order to limit the possibility of unauthorized access.

Thus, a cryptographie system and method with key escrow feature is provided. One skilled in the art will appreciate that the présent invention can be prac~iced by 15 other than the described embodiments, which are presented for purposes of illustration and not limitation, and the présent invention is limited only by the claims that follcw.