Dorothy E. Denning
Version of February 26, 1997
This document is a companion document to A Taxonomy for Key Escrow Encryption Systems, which was published in Commnunications of the ACM in March, 1996. It contains descriptions of various escrowed encryption systems and approaches. Developers of other approaches are invited to submit descriptions for inclusion in the document. All submissions should be in HTML in the same style as the others and e-mailed to denning@cs.georgetown.edu.
Notation: "E[K](X)" denotes X encrypted under key K. "S[K](X)" is X signed under key K. "x^n" denotes x to the power n.
Systems
Crypto Backup is an AT&T proprietary design for a commercial or private key escrow encryption system. The data encryption key for a document is derived from a public key of an escrow agent and a random number. The latter is inserted into a Backup Recovery Vector in such manner that the escrow agent can recover the data encryption key using its corresponding private key.
User Security Component
Application domain. Files and messages, including real-time voice.
Data encryption algorithm. This is unspecified and could be any single key algorithm.
Stored identifiers and keys. Each user has a unique identifier UID and a public-private key pair (KUpub, KUpriv). In addition, the user keeps a copy of the public component KEApub of an escrow agent master key and an identifier for the master key.
Data recovery field and mechanism. Each document is encrypted under a unique file encryption key K, which is derived from KEApub and a random number R using a one-way function. When K is generated, a Backup Recovery Vector (BRV) is created and placed in the document header along with the user's digital signature. The BRV serves the role of a DRF and contains UID, the identifier for KEApub, and a one-way function of R that enables recovery of K.
Implementation. Software. No special hardware is required.
Key Escrow Component
Escrow agents (Backup Agents). Each document is associated with a backup agent, which could be part of the organization or a separate entity. The system could be extended to support multiple agents and threshold techniques.
Data recovery keys. The only keys that are escrowed are the backup agent's private master keys. If multiple agents are used, the master keys could be split using any method of secret sharing. The master keys could be generated by the backup agents.
Data recovery services. Given a BRV, the backup agent decrypts K using its private master key, and makes K available to the DRC.
Data Recovery Component
Capabilities. The system would support post-processing of communications, but not necessary real-time decryption since the backup agents are needed to decrypt each message.
Data encryption key recovery. For a given document, the BRV is extracted and given to the backup agent, which returns the file encryption key K.
Reference
David P. Maher, "Crypto Backup and Key Escrow," Comm. ACM, Mar. 1996.
SecureKEES^TM is an international commercial key escrow encryption system for secure communications. Employees of a corporation register their encryption devices (e.g., smart card) and private encryption keys with one or more commercial escrow agents selected by the corporation. Data recovery is enabled through a message control header that allows recovery of the session key with the escrowed key of either the sender or receiver.
User Security Component (Trusted Device)
Application domain. Communications.
Data encryption algorithm. This could be any public algorithm.
Stored identifiers and keys. Each device has a permanent unique id and public-private key pair. In addition, each user has a public-private signature key pair and a public-private encryption key pair that is used for key establishment. These keys are also stored in the device, but they can be changed.
Data recovery field and mechanism. The sender creates a Message Control Header (MCH) that contains a randomly generated session KS encrypted under the public encryption key of the sender plus a copy of KS encrypted under the public encryption key of the receiver. In addition, it identifies the sender and receiver and their escrow centers, and it contains encrypted escrow certificate numbers for both the sender and receiver. The MCH serves the dual role of distributing KS to the intended recipient and providing a DRF. The MCH is signed by the sending device.
Implementation. The USC is to be implemented in a single-chip device (e.g., smart card) containing a CPU, crypto co-processor, protected non-volatile memory, trusted clock (optional), and trusted firmware.
Key Escrow Component
Escrow agents. Escrow agents are commercial entities. Users (or their organizations) pick one or more agents from among a set of participating entities. Escrow agents are associated with an escrow center.
Data recovery keys. Users must register their trusted USC's with an escrow center. The USC transmits a device registration request containing the user's public-private encryption key pair and device public signature key. The private encryption key is split and given to the escrow agents. Once registration is complete, the USC receives an escrow certificate identifying the escrow center and providing other information needed for data recovery. Each escrowed certificate has a unique number. The user can change encryption keys.
Data recovery services. The escrow agents make a user's private key components available to the Data Recovery Component.
Data Recovery Component
Capabilities. The system can support both real-time decryption and post-processing of intercepted communications.
Data encryption key recovery The DRC extracts the encrypted session key KS for either the sender or receiver from the MCH. It also extracts the escrow certificate for the party and contacts the escrow center to determine the escrow agents. It acquires the sender's or receiver's key components from the escrow agents and decrypts KS.
References
Frank W. Sudia, "Private Key Escrow System," overheads of presentation, Bankers Trust Co., New York, NY, 1995.
SecureKEES^TM product literature, CertCo, Bankers Trust Company.
[Contributed by Mihir Bellare and Shafi Goldwasser]
Some escrow approaches are potentially vulnerable to large scale abuse of escrowed keys arising from a change in power in the government, or a change in management in a business setting. Verifiable partial key escrow (VPKE) is a means of mitigating the effects of such an event. The idea is that only part of the user's secret key will be escrowed with the trustees, leaving the trustees with a certain computational effort to find the rest of the secret key; this is done so that on one hand the trustees are assured that this effort, and not more, suffices, and on the other hand the user is assured that there is no shortcut for the trustees.
Roughly, the user's receive key is split into two portions: first and second. The first portion is then split amongst n trustees in such a way that a threshold of t+1 of the trustees can recover it, but not fewer, and a protocol is executed to ensure that the second portion of the secret key (which has not been escrowed) is of an appropriate size and can be recovered by an exhautive search, once the trustees recover the first portion. Then the associated user's send key is made public.
Since part of the key is not escrowed, computational effort on the part of the trustees is required to find it; the issue is when this extra effort needs to be invested. Some schemes proposed by others (eg. Micali's guaranteed partial key escrow) have the drawback that this extra effort need not wait until the threshold of t+1 trustees have gathered; it is possible for even a single trustee to jump start the process and compute some information which, when he and t other trustees combine, enables them to at once recover the entire user key. In other words, all the work required of the governement to recover all secret keys can be done by pre-computation before it obtains any escrowed information. This early recovery attack on a partial key escrow system largely negates the advantage of partially escrowing the key and systems subject to it should be viewed with concern.
A scheme is proposed for the Diffie-Hellman cryptosystem which verifiably achieves delayed recovery. Namely, it is assured that the computational effort must be invested after a threshold of t trustees combine. A preliminary delayed recovery scheme for the RSA system is also proposed.
Verifiable partial key escrow extends Shamir's idea of partial escrow of a DES key by raising the issue of verifiability and addressing the problem for public key systems. In related work, Bellare and Goldwasser consider achieving time delayed key escrow via mechanisms called verifiable cryptographic time capsules. These are methods that achieve the same objective as partial key escrow (namely to put a lapse of time in between obtaining of escrowed information and obtaining of the actual secret key of the user) but in a very different way. Time delayed key escrow systems, achieving delayed recovery, are provided for several cryptosystems including RSA, and an alternative scheme for the Diffie-Hellman cryptosystem is also provided.
Below is more information about verifiable partial key escrow.
User Security Component
Application domain. Communications
Data encryption algorithm. An implementation is provided for the Diffie-Hellman (DH) cryptosystem.
Stored identifiers and keys. Each user has private send key KUpriv= S and public receive key KUpub=g^S as in the DH system. Here g is the generator of a group of prime order in which the discrete logarithm problem is hard.
Data recovery field and mechanism. To send an encrypted message to user B, user A first obtains B's public receive key g^{SB}. A then derives the shared key g^{SA*SB} = (g^{SB})^{SA}. This key is then used as the session key or to encrypt the session key.
Implementation. Software or hardware.
Key Escrow Component
Escrow agents. Any number n of them. Assume n>1 in following.
Data recovery keys. A user generates her own public and private keys and then follows a prescribed verifiable partial key escrow protocol. The secret key S is split as S = x+a mod p where a has length 2l if we want the recovery time to be on the order of 2^l. Then a prescribed verifiable partial key escrow protocol is followed. It involves committing to the parts of the keys in an information theoretic way , verifiable secret sharing x also in an information theoretic way, and some efficient zero-knowledge proofs. After this protocol the trustees sign a certificate containing the user's identity and her public key KUpub=g^S.
Data Recovery Component
Data encryption key recovery. After obtaining the escrowed portion x of a user private key KUpriv=S=x+a, the trustees compute g^a = KUpub/g^x. Since a is 2l bits long, it is possible to recover it in time 2^l (using Shank's baby-step giant-step method). Having done this the trustees have the user private key and can obtain the session key.
An important element of the security is that g^a is not revealed in the escrow process. This prevents early recovery attacks.
References
Mihir Bellare and Shafi Goldwasser. " Verifiable Partial Key Escrow," UCSD CSE Dept Technical Report CS95-447.
Mihir Bellare and Shafi Goldwasser. " Verifiable Cryptographic Time Capsules: A New Approach to Key Escrow," Manuscript, April 1996.
[Contributed by Mihir Bellare and Shafi Goldwasser]
In a time delayed key escrow scheme, a time delay is imposed between the act of obtaining the escrowed information of a user and actually obtaining the user secret key. The delay is computational in nature. The escrowed information is not the key, but rather a piece of data whose possession enables the trustees to embark on a computation of some prescribed difficulty whose outcome is the user secret key.
Time delayed key escrow (TDKE) provides a cushion of security against the threat of total breakdown of the system of trust. It protects users from massive and instantaneous key recovery on the part of a goverment or business authority which for some reason has decided to forgo the rules: even if all trustees are corrupt, it will take the authority significant effort to collect a sizeable fraction of the users keys.
TDKE is implemented via a primitive called a verifiable cryptographic time capsule (VCTC). This is a mechanism via which a the capsule is then split amongst all trustee via a secret sharing scheme (if only one trustee exists he gets the capsule). When the trustees are ready to recover the key, they get together, and recover the capsule. Then they must open it, a task which takes a certain prescribed computational effort. Furthermore the capsule creation process is verifiable: the trustees are assured the user really put her secret key in it, and the user is assured that the capsule can't be opened any faster than it should.
Implementations are provided for the RSA system and the Diffie-Hellman cryptosystem. A more general transformation is also provided which applies to any cryptosystem. This is the first solution with delayed recovery for the RSA cryptosystem.
A significant issue in any scheme for TDKE is early versus delayed recovery. The former is said to happen when the extra computational effort that must be invested by the trustees to get the user secret key can be done via pre-computation, prior to obtaining of the escrowed information. Early recovery effectively renders TDKE useless. In contrast, in a delayed recovery scheme, the extra computation can only begin after the escrowed information becomes available. The VCTC-based paradigm achieves delayed recovery in a very clear way: the capsule C, which is the object to open, is simply not available to the trustees before they recover all the escrowed information. Without that, they would not even know what compuation to start.
This approach may be compared with partial key escrow, where one achieves a time delay by escrowing only part of the user secret key, and asking the trustees to find the rest by brute force search. (See Shamir's idea of partial escrow of a DES key, Bellare-Goldwasser verifiable partial key escrow and Micali guaranteed partial key escrow.) TDKE using VCTCs is more flexible and general, allows rigurous security analysis, and allows one to achieve delayed recovery in easier ways. In particular it yields the first solution with delayed recovery for the RSA cryptosystem.
Below is more information about time delayed key escrow via verifiable cryptographic time capsules.
User Security Component
Application domain. Communications
Data encryption algorithm. An implementation is provided for the RSA and Diffie-Hellman (DH) cryptosystem. For illustration purposes the following focuses on the RSA case.
Stored identifiers and keys. Each user has private send key KUpriv which is an RSA modulus N and decryption exponent d, and public receive key KUpub which is the same modulus N and an encryption exponent e.
Data recovery field and mechanism. To send an encrypted message to user B, user A encrypts using it under the receive key of B.
Implementation. Software or hardware.
Key Escrow Component
Escrow agents. Any number n of them. Assume n>1 in following.
Data recovery keys. A user generates her own public and private keys and then follows a prescribed protocol to put the secret key into a verifiable cryptographic time capsule. This protocol involves generating a pair (s0,s1) called a claw so that possession of either half yields no information on the secret key but knowledge of both halves completeley specifies the key. One half of the claw is provided to the trustees; the the other is encrypted under some cipher of pre-determined key length l, where 2^l is the desired recovery time, and the ciphertext is escrowed. A cut and choose protocol is used to ensure compliance with this process.
Data Recovery Component
Data encryption key recovery. After obtaining the escrowed ciphertext the trustees search for the l bit key which will decrypt it, and obtain a half of the claw. Since they already had the other half, they can factor the modulus, and thereby decrypt ciphertexts transmitted to the user.
References
Mihir Bellare and Shafi Goldwasser. " Verifiable Cryptographic Time Capsules: A New Approach to Key Escrow," Manuscript, April 1996.
Mihir Bellare and Shafi Goldwasser. " Verifiable Partial Key Escrow," UCSD CSE Dept Technical Report CS95-447.
The Yaksha system uses a central key server that generates and distributes session keys to communicating parties. The server could provide keys for phone conversations over the public switched network or a computer network and data recovery services to government officials who are authorized to intercept those communications.
User Security Component
Application domain. Communications or stored files.
Data encryption algorithm. Any single-key algorithm.
Stored identifiers and keys. Each user has a unique public key that is used with a variant of the RSA system called RSA multi-signatures. With this scheme, the private exponent d is split into two values du and ds such that du*ds = d mod phi(n), where n is the modulus. The USC contains the public exponent e and private exponent du (ds is kept with the KEC). (Neither du nor ds can be computed from the other without knowing the prime factors of n.)
Data recovery field and mechanism. There is no DRF.
Implementation. Hardware or software.
Key Escrow Component
Escrow agents. A central key server performs the role of the key escrow component and escrow agents. The server could provide services on any communications network.
Data recovery keys. The server keeps a copy of the private exponent ds and public values e and n for each user, which are used for distributing session keys. For each conversation, it generates the session key KS and transmits it to the two parties that want to communicate. KS is transmitted to each party as KS^ds mod n using that party's parameters ds and n. Each party is able to recover KS by computing ((KS^ds)^du)^e mod n.
Data recovery services. The KEC releases individual session keys KS.
Data Recovery Component
Capabilities. If the KEC is part of the public switched network, it could support real-time decryption by automatically transmitting each session key, after receipt of an initial court order, to the DRC along with the communications stream. To support post-processing decryption of recorded communications, it would need to retain the session keys beyond the duration of their use.
Data encryption key recovery. For each communications, the DRC sends a warrant to the KEC requesting the session key. The KEC returns the session key.
References
Ravi Ganesan, "The Yaksha Security System," Comm. ACM, Mar. 1996.
[Contributed by Eric R. Verheul]
The concept of Binding (public-key) Cryptography is an extension of the TIS-CKE concept (see below) that makes fraud by sending false recovery keys in the latter concept publicly detectable by arbitrary third parties (e.g., network operators or (Internet) Service Providers). For this detection, no secret information is either required or gained by these parties, leaving the privacy of users unharmed. If such detection happens regularly, fraud by sending false recovery keys can be properly discouraged and, if desirable, fined. Metaphorically, the solution consists of equipping public-key encryption systems used for confidentiality with a metal detector, as used at boarding gates on airports.
To make this detection possible for a particular public-key encryption system, so-called "binding data" have to be constructed. So far, this has been done for the ElGamal (public-key) system. Where appropriate, some special features of that particular construction will be discussed.
User Security Component
Application. The concept is meant primarily for file transfers, including electronic mail; it could also be used for stored data.
Data encryption algorithm. This could be any symmetric algorithm.
Stored identifiers and keys. Each user has a public-private key pair. Also, if desired or required by law, each user chooses and publicizes a Trusted Recovery Party (TRP) which he trusts. It would be convenient to let the TRPs public key be part of the user's (certified) public key.
Data recovery field and mechanism. The sender (user) generates a session (file) key S and, as with TIS-CKE, forms a data-header which is accompanied (e.g. sent along) with any use of the session key. This data-header includes the following two fields:
As a guarantee that the user does encrypt S in F2 (the Data Recovery Field) and does not fraud by encrypting a different (useless) session key, a third field "binding data" is added.
The idea is that any third party, e.g., a network or (Internet) service provider, or even computer operating systems, who has access to components F1, F2 and F3 (but not to any additional secret information) can:
a. determine that the used session keys in F1 and F2 coincide;
b. not determine any secret information.
On the basis of F2, any of the chosen TRPs can determine S. Within the ElGamal construction, the binding data field is around 320 bit long. Also, one can prove here that encrypting the same session key S with different public keys does not weaken security (as is the case with some RSA based schemes). Moreover, by letting the time/date be one of the parameters in the construction of the binding data, the user effectively sets a publicly verifiable time stamp on the data-header supporting time-bounded data-recovery.
Implementation. Software or hardware.
Key Escrow Component
Escrow agents. Binding Cryptography is meant as a basis to allow cooperating countries to implement different national cryptographic policies on the domestic and international use in an interoperable way. Accordingly, the number (and location) of TRPs as well as their legal status (private or public) depends on the different cryptography policies. With the use of binding data, compliance with these policies can be verified by third parties.
Data recovery keys. The TRPs generate master public-private keys. During the initialization of a User Security Component, it obtains a public key of an appropriate TRP (e.g. in the country of the user); the TRPs public key could be part of the user's certified public key.
Data recovery services. On the basis of the Data Recovery Field (F2), a chosen TRP decrypts and returns the used session key S to legitimate parties. With respect to the binding variant of ElGamal, the secret key of the TRP public key can be shared in a verifiable k out of n secret sharing scheme using a scheme by Pedersen (1991). In this scheme there is no need for a (trusted) dealer (party or device) to know the shared secret for the construction of the shares, or for the recovery of the session key. For instance, a 1 out of 2 construction of this type would allow two national TRPs to construct and share one secret key in a secure and verifiable way.
Data Recovery Component
Capabilities. The system could support post-processing decryption of recorded communications. It might support real-time decryption if the TRP is on-line and can decrypt in real-time.
Data encryption key recovery. For given encrypted information, the Data Recovery Field (F2) is extracted and given to the appropriate TRP. The TRP decrypts this and returns the used session key S (see above). With this session key the plaintext can be easily reconstructed.
Safeguards. The certifying authorities and the trusted recovery parties should preferably be different parties, to prevent accumulation of power. To protect against unauthorized decryption, users should have a flexible choice in TRPs. Also, TRPs should use procedural and technical controls, such as time stamps. Moreover, TRPs should only decrypt session keys and should never hand over secret keys. Finally, the detection quality of the third parties can be checked by an auditor by sending along non-complying messages on a regular basis.
References
E.R. Verheul, B.J. Koops, H.C.A. van Tilborg, "Binding Cryptography. A fraud-detectible alternative to key-escrow solutions", Computer Law and Security Report, January-February 1997, pp. 3-14.
E.R. Verheul, H.C.A. van Tilborg, "Binding ElGamal. A fraud-detectable alternative to key-escrow solutions", will be presented at Eurocrypt97.
See also Binding Cryptography
Matt Blaze has developed a prototype smartcard-based key escrow system for use with his Cryptographic File System (CFS). A user can escrow a file encryption key on a smart card which is entrusted with an escrow agent. The escrow agent can then use the smart card to decrypt files encrypted under that card's key.
User Security Component
Application domain. Stored files.
Data encryption algorithm. CFS uses a combination of DES in electronic codebook (ECB) and pre-computable stream cipher modes with two keys, K1 and K2.
Stored identifiers and keys. There are none. File encryption keys are derived from pass-phrases, which the user must remember by other means.
Data recovery field and mechanism. There is none.
Implementation. Software.
Key Escrow Component
Escrow agents. There is a single escrow agent, which can be any person.
Data recovery keys. Users generate a file encryption key at the time a directory is created. This key is used to encrypt all files in the directory. The user can escrow the key by putting it on an individual smartcard, encrypted under an "escrow key." The smartcard and escrow key are given to a trusted person within the organization. The escrow key could be split among multiple persons if desired.
Data recovery services. The escrow agent uses the smartcard to decrypt encrypted files, thereby performing the function of the DRC. The smartcard does not release its keys.
Safeguards. Using an "audit key," the smartcard records the number of times used. The user can post audit a returned card to determine if it was used.
Data Recovery Component
The DRC is implemented through the smartcard and escrow agent services.
References
Matt Blaze, "Key Management in an Encrypting File System."
The Clipper Chip is a tamper-resistant chip that implements the EES, a government standard for phone communications which combines a key escrow capability with the classified SKIPJACK encryption algorithm. Each chip has a device unique key and transmits a Law Enforcement Access Field (LEAF) with all communications. The LEAF contains the session key encrypted under the device unique key. Components of the device unique key are encrypted and stored in escrow with two separate escrow agents. When a wiretap is authorized, these components are released, decrypted, and combined to form the device unique key, enabling decryption of session keys in intercepted LEAFs.
User Security Component (Product with Clipper Chip)
Application domain. Phone communications.
Data encryption algorithm. The EES specifies the classified SKIPJACK algorithm, which is a single key algorithm.
Stored identifiers and keys. Each Clipper Chip has a unique id (UID) and device unique key (KU). In addition, it contains a family key KF that is shared with the Data Recovery Component.
Data recovery field and mechanism. The Clipper Chip transmits a Law Enforcement Access Field (LEAF) with all encrypted data for the purpose of making the session key KS available for data recovery. The LEAF contains KS encrypted under KU, and the entire LEAF is encrypted under KF:
where EA is a 16-bit escrow authenticator and the encryption functions are classified modes of SKIPJACK. The receiving chip validates the LEAF by checking the EA.
Implementation. The Clipper Chip must be implemented in special tamper-resistant hardware. However, a product using Clipper may include software or firmware elements.
Key Escrow Component
Escrow agents. The EES requires that there be at least two escrow agents. The current system uses the National Institute of Standards and Technology (NIST) and the Automated Systems Division of the Department of Treasury.
Data recovery keys. Each device unique key KU is stored in escrow as two encrypted components, EKC1 and EKC2, such that the XOR of their decryption yields KU. The keys and their components are generated inside a secure programming facility. The keys are programmed onto the chips and the key components given to their respective escrow agents. Currently, escrowed keys are stored on floppy disks in double-locked safes, but in the target system they will be stored on-line on escrow agent workstations.
Data recovery services. The escrow agents make EKC1 and EKC2 available to the Data Recovery Component so that KU can be recovered. They also provide the expiration date for the surveillance. When that date arrives, KU is automatically deleted so that any further traffic cannot be decrypted.
Safeguards. The KEC has extensive safeguards to protect against misuse of keys, including auditing.
Data Recovery Component (Key Escrow Decrypt Processor)
Capabilities. The EES supports post-processing decryption of recorded communications and real-time decryption, at least for two-way simultaneous communications.
Data encryption key recovery. The standard requires that the same KS be used to encrypt information transmitted in both directions for two-way simultaneous communications, so the session key can be acquired from either LEAF. In that case, the decrypt processor extracts and decrypts the LEAF associated with the target of the surveillance; otherwise, it uses the LEAF of the sender. It transmits the UID to the escrow agents along with certification of the electronic surveillance. The escrow agents return the encrypted key components for the device unique key KU. The decrypt processor is then able to reconstruct KU and decrypt the session key transmitted in the LEAF. In addition, it can decrypt the session key in future LEAFs transmitted by the device as long as it holds KU.
References
Dorothy E. Denning and Miles Smid, "Key Escrowing Today," IEEE Communications, Vol. 32, No. 9, Sept. 1994, pp. 58-68.
National Institute for Standards and Technology, "Escrowed Encryption Standard (EES)," Federal Information Processing Standards Publication (FIPS PUB) 185, 1994.
This proposal uses Diffie-Hellman techniques for integrating key escrow services into a public-key infrastructure.
User Security Component
Application domain. Communications, including e-mail, and files.
Data encryption algorithm. Any single-key algorithm.
Stored identifiers and keys. Each user has a private key (Diffie-Hellman exponent) which is not escrowed and one that is. Both have corresponding public keys.
Data recovery field and mechanism. The user's private escrowed key is used for file encrypton. It is also used with Diffie-Hellman techniques to generate and distribute a session key. The information transmitted in the key distribution protocol serves as the data recovery field.
Implementation. Hardware or software is possible.
Key Escrow Component
Escrow agents. There can be one or more agents. They could serve as the certificate authorities in a public key infrastructure.
Data recovery keys. Using the private key that is not escrowed and the escrow agent's public key, the user enters into a Diffie-Hellman exchange with the escrow agent to establish a private escrowed key. This key can be split with multiple agents in a "k out of n" scheme. It could be changed on a regular basis.
Data recovery services. The escrow agents could release the private escrowed key of a user.
Data Recovery Component
Capabilities. The approach could support real-time and post-processing decryption.
Data encryption key recovery. The DRC can recover the data enryption key from the key distribution protocol by acquiring the escrowed key of either the sender or receiver.
References
Jim Omura, "Alternatives to RSA Using Diffie-Hellman with DSS," White Paper, Cylink, Sept. 1995.
Yvo Desmedt shows how a data recovery field can be bound to the ciphertext in such a way that the authorities can determine the identity of the receiver if the receiver can decrypt the DRF in order to obtain the session key. Thus, if the DRF is deleted or tampered with so as to evade authorized government wiretaps, the intended receiver would be unable to decrypt the ciphertext. We describe only the distinguishing features of the binding mechanism.
User Security Component
Stored identifiers and keys. Each user has a public-private key pair.
Data recovery field and mechanism. The sender transmits the session key KS to the receiver in a DRF, which is encrypted under the public key of the receiver. The method of encryption puts redundancy in the data that identifies the receiver. The receiver cannot decrypt the DRF and determine KS if the DRF is omitted or tampered with. Thus, the scheme binds the DRF to the encrypted communications. The encryption methods are derived from the ElGamal scheme.
Data Recovery Component
Data encryption key recovery. If the DRF is properly constructed, the DRC can identify the receiver. This in turn would enable it to acquire the receiver's private key from the escrow agents, which would allow it to decrypt the DRF to obtain KS.
References
Yvo Desmedt, "Securing Traceability of Ciphertexts - Towards a Secure Software Key Escrow System," Proc. Eurocrypt '95, Saint-Malo, France, May 21-25, 1995, pp. 147-157.
Whitfield Diffie has suggested an alternative to Clipper in which the DRF (LEAF) includes a timestamp that is used by on-line escrow agents to enforce the time interval during which data recovery is authorized. Rather than releasing a chip's device unique key, the escrow agents participate in each intercepted communication and decrypt the session key in the LEAF if the timestamp falls within the period of authorized interception. Here we describe only those features that distinguish it from Clipper.
User Security Component
Stored identifiers and keys. Each chip contains a unique identifier UID and two unique keys, KU1 and KU2.
Data recovery field and mechanism. The DRF (LEAF) is computed by splitting the session key KS into two components, KS1 and KS2, such that KS = KS1 XOR KS2. KS1 is then concatenated with a time stamp TS and the result encrypted under KU1. Similarly KS2 is concatenated with TS and encrypted under KU2. Exactly how the rest of the LEAF is computed is left unspecified. Assuming it imitates the EES with inclusion of UID and an escrow authenticator EA, and with encryption under a family key KF, then it might look as follows:
Key Escrow Component
Data recovery keys. For each device, escrow agent 1 holds KU1 and escrow agent 2 hold KU2.
Data recovery services. The escrow agents decrypt the session key components, (KS1 || TS) and (KS2 || TS), respectively for each communication. If the time stamp TS falls within the authorization period for data recovery, then KS1 and KS2 are released to the DRC.
Data Recovery Component
Capabilities. The requirement that the KEC participate in the decryption of each session key may preclude real-time decryption.
Data encryption key recovery. After intercepting the LEAF of a particular communication and decrypting it with the family key KF, the DRC sends E[KU1](KS1 || TS) to escrow agent 1 and E[KU2](KS2 || TS) to escrow agent 2. Assuming TS falls within the data recovery authorization period, the escrow agents return KS1 and KS2. The DRC then constructs KS. This process must be repeated for each communication.
Safeguards. The DRC cannot decrypt any message without assistance from the escrow agents, who enforce the time interval of authorized decryption.
References
Thomas Beth, Hans-Joachim Knobloch, Marcus Otten, Gustavus J. Simmons, and Peer Wichmann, "Clipper Repair Kit - Towards Acceptable Key Escrow Systems," Proc. 2nd ACM Conf. on Communication and Computer Security, 1994.
The Fortezza card is a commercially available PC card which provides confidentiality, authentication, and digital signature services. The card contains a Capstone Chip, which implements the Escrowed Encryption Standard plus algorithms for key establishment, hashing, and digital signatures. A user's private keys are stored on the card and can be escrowed with the user's public-key certificate authority.
User Security Component
Application domain. Electronic mail and files.
Data encryption algorithm. SKIPJACK.
Stored identifiers and keys. In addition to the keys stored on the Capstone chip, the Fortezza card contains a user's private signature keys and private encryption keys. The latter are used for key establishment.
Data recovery field and mechanism. When an electronic mail message is encrypted, the session key is transmitted to all recipients using public-key techniques based on Diffie-Hellman. These techniques allow the recipients to determine the session key using their private keys. The information transmitted for key distribution serves as a DRF.
Implementation. The Fortezza card is a hardware PCMCIA card. The encryption algorithms are implemented on the Capstone chip.
Key Escrow Component
Escrow agents. These are public-key certificate authorities selected by an organization.
Data recovery keys. A user's private keys are given to the user's certificate authority at the time the public-key certificate is issued.
Data recovery services. The certificate authority would release a user's private key.
Data Recovery Component
Capabilities. Real-time decryption is possible.
Data encryption key recovery. A session key can be recovered using the recipient's private key. In addition, because the Capstone chip implements the EES, it can be recovered using the Capstone key of the sender, which would be obtained from the EES's escrow agents.
References
KISS is a key escrow encryption system designed by Fortress U & T Ltd. for communications. Each user has a unique public-private key pair, stored on a tamper-resistant encryption chip. A data recovery field includes a session key encrypted under the user's private key and the user's private key encrypted under two escrow agent public master keys. The escrow agents decrypt the user's private key for the Data Recovery Component, which is then able to decrypt all session keys for that user.
User Security Component
Application domain. Two-party communications, including real-time interactive and electronic mail. General principles could be used with files.
Data encryption algorithm. KISS could be used with DES or any other single-key algorithm.
Stored identifiers and keys. Each chip contains the public components, KEXpub and KEYpub, of the escrow agent master keys. It also contains a long-term user identifier and public-private key pair, which can be changed with certification by either of the escrow agents. For user A, we denote A's key pair by (KApub, KApriv). KApriv is generated on the chip and never leaves it.
Data recovery field and mechanism. A session key KS is made available to the DRC through a DRF that consists of several parts, some of which are used for key establishment. For a two-way conversation between parties A and B, A transmits KS and a timestamp TA encrypted under B's public key; that is, A transmits E[KBpub](KS, TA). In addition, A transmits its credentials which consist of its identifier, its public key, its private key successively encrypted under the public keys of the two escrow agencies: E[KEXpub](E[KEYpub](KApriv), a National Crossover (NCR), a Valid Until Date (VUD), timestamp TA, and an Escrow Verification String (EVS). The NCR lists the countries whose crypto laws A has agreed to abide by. The EVS includes a hash of A's identifier, public key, encrypted private key, NCR, and VUD, all signed by a National Commissioner. Similarly, B transmits E[KApub](KS, TB) and its credentials. A and B validate each other's credentials.
For e-mail, A transmits KS encrypted under both KApub and KBpub. A validates B's credentials and transmits B's credentials along with its own.
Implementation. The USC is implemented in a public key crypto chip that includes the cryptographic functions, a pure random number generator, safe EEPROM and memories with controlled access, and provisions for system regeneration and system upgrade.
Key Escrow Component
Escrow agents. The design is described in terms of two national escrow agents, but there could be more.
Data recovery keys. The only escrowed keys are the private key components of the master keys of the two escrow agents, KEXpriv and KEYpriv. The escrow agents generate their public-private key pairs at the time the KEC is initialized. There can be multiple keys so that they can be changed at regular predefined ("device valid until") intervals. The public keys, KEXpub and KEYpub, are inserted into the ROM or controlled access EEPROM of all crypto chips.
Data recovery services. The KEC decrypts a user's encrypted private key using its private master key. The services are available to the authorities in countries whose crypto laws the subject has agreed to abide by.
Data Recovery Component
Capabilities. KISS can support both real-time decryption and post-processing of previously intercepted communications. Decryption is possible using the private key of either the sender or the receiver, both for one-way and for two-way communications.
Data encryption key recovery. After intercepting the DRF of a particular communication involving subject A (either the sender or receiver), the decryption device sends E[KEXpub](E[KEYpub](KApriv) to an archive agent X along with a signed warrant request. If the warrant is valid, then a record is made and the package is forwarded to archive agent Y and to escrow agent X. Archive agent Y similarly validates the package, creates an archive record, and sends it to escrow agent Y. Escrow agent X then decrypts the package using KEXpriv and sends E[KEYpub](KApriv) to escrow agent Y. Escrow agent Y decrypts using KEYpriv and transmits KApriv to the decryption device. The DRC is then able to decrypt the session key KS that had been encrypted under KApub. For future communications initiated or received by A, the DRC is able to obtain KS without assistance from the escrow agents.
Safeguards. To protect against unauthorized decryption, KISS uses procedural controls and technical safeguards, including timestamps, signatures, digital warrants, and archiving.
References
Carmi Gressel, Ran Granot, and Itai Dror, "International Cryptographic Communication without Key Escrow. KISS: Keep the Invaders (of Privacy) Socially Sane," International Cryptography Institute 1995: Global Challenges; Fortress U & T Ltd., POB 844, Beer Sheva 84106, Israel, 1994.
Failsafe key escrow was proposed by Joseph Kilian and Tom Leighton to avoid a potential problem systems such as fair cryptography in which the user generates a public-private key pair and gives the private key to the escrow agents. With failsafe key escrow, a user's keys are generated jointly by the user and key escrow agents. This prevents the user from hiding a "shadow key" in the escrowed key, and then using the shadow key instead of the escrowed key in order to circumvent the key escrow function. The main features of the approach are as follows:
Key Escrow Component
Data recovery keys. The private key of a user's public-private key pair is stored in escrow and can be split among several agents. The public-private key is generated jointly by the user and the escrow agents, with each generating a component of the key pair. Verifiable secret sharing and secure commitment protocols based on the discrete log problem are used for exchanging components between the user and escrow agents.
References
Joseph Kilian and Tom Leighton, "Fair Cryptosystems, Revisited," Proc. CRYPTO 95, pp. 208-221.
Otto Leiberich has outlined an enhancement to Clipper that would provide time-bounded data recovery. The enhancement involves placing a clock on the Clipper Chip and using date-dependent unit keys to encrypt the session key in the LEAF. For an authorized surveillance, the escrow agents release their components of the unit keys corresponding to each date within the authorized period of surveillance. Here we describe only those features that would distinguish it from Clipper.
User Security Component
Stored identifiers and keys. Each device has a unique id (UID) and two unique keys, KU1 and KU2.
Data recovery field and mechanism. A LEAF is transmitted as with Clipper, except that the session key KS is encrypted under a time-dependent unit key KU(t) that is derived from KU1 and KU2 as follows:
where t is the current date. Thus, the LEAF is:
Implementation. Each chip must have a reliable clock.
Key Escrow Component
Data recovery keys. For each UID, escrow agent 1 holds KU1 and escrow agent 2 holds KU2. The key components KU1 and KU2 could be generated and escrowed as for Clipper, except that the XOR of KU1 and KU2 is irrelevant.
Data recovery services. For a given interval of time [t1, ..., tn], escrow agent 1 computes a series of keys derived from U1:
Similarly, escrow agent 2 computes a series of keys derived from U2. These keys are released to the DRC.
Data Recovery Component
Data encryption key recovery. The DRC extracts the LEAF and sends the UID to both escrow agents along with certification of the authority to conduct the surveillance. The escrow agents then compute and release their respective series of keys, (KU1(t1), ..., KU1(tn)) and (KU2(t1), ..., KU2(tn)), where [t1, ..., tn] is the period of authorized surveillance. For each pair, KU1(ti) and KU2(ti), the DRC computes KU(ti) = KU1(ti) XOR KU2(ti). The decryptor is then able to obtain any session key KS encrypted on day ti by decrypting EKU(ti)(KS) in the LEAF.
Safeguards. The time-dependent unit keys prevent the DRC from decrypting data encrypted before t1 or after tn, assuming the escrow agents do not release key components falling outside the period from t1 to tn.
References
Otto Leiberich, private communication, June 1994.
Tom Leighton and Silvio Micali show how a key escrow system could be modified to include a built-in method for key establishment. Each user has a private key, and any two users can compute a shared secret key from their own private key and the identifier of the other. This shared key can be used as the session key or to establish a key that is unique to the session. The private keys are stored in escrow, and the escrow agents could release either the shared key of two users or the private key of one user, which would enable access to all session keys used by that user. Here we describe only those features that are peculiar to their scheme.
User Security Component
Stored identifiers and keys. Each USC has a unique identifier and private key. The device unique key is used to generate session keys for communicating with other users. Any two USCs can compute a shared secret session key using only their own private keys and the identifier of the other USC. No information needs to be exchanged other than the identifiers.
Data recovery field and mechanism. There is none.
Key Escrow Component
Data recovery keys. The escrow agent(s) generate the identifiers and private keys with the built-in key agreement mechanism. The private keys and identifiers are distributed to the USCs.
Data recovery services. The escrow agents could release either a private key of a particular USC or the key that is shared between two USC's.
Data Recovery Component
Data encryption key recovery. The DRC could obtain from the KEC either the session key used between two parties or the private key for the party under investigation. The latter would enable it to determine all session keys used by that party and, therefore, decrypt in real time.
References
Tom Leighton and Silvio Micali, "Secret-Key Agreement without Public-Key Cryptography," Proc. Crypto '93, pp. 208-221.
This proposal allows the escrow agents to release keys that restrict decryption to the communications of a particular user or pair of users during a specific interval of time.
User Security Component
Application domain. Two-way interactive communications.
Data encryption algorithm. This could be any algorithm.
Stored identifiers and keys. Each user A has a permanent public-private key pair denoted by P(A) and S(A).
Data recovery field and mechanism. The sender (A) and receiver (B) first agree upon a session key K which is computed from their personal keys and the date d using Diffie-Hellman techniques and hashing. Then A computes and transmits a DRF which contains K encrypted under a key S(a, b, d) derived from S(a), P(b), and d. Similarly, B computes and transmits K encrypted under a key S(b, a, d).
Implementation. Hardware or software is possible.
Key Escrow Component
Escrow agents. These would be the public-key certificate authorities.
Data recovery keys. A user's private key is escrowed. Keys could be split using an "n out of n" or "k out of n" method of secret sharing.
Data recovery services. The escrow agents can release three types of keys for a given user A: 1) the user's private key S(a), which allows computation of S(a, b, d) for all b and d and, therefore, decryption of all messages sent to and from the user; 2) a key S(a, d) derived from S(a) and a date d, which allows derivation of all S(a, b, d) for date d and, therefore, decryption of all messages sent to and from the user on d (the escrow agents can release a set of such keys for all days within a period authorized by a court order); and 3) the key S(a, b, d) for a particular b and d, which allows decryption only of messages transmitted between A and B on date d (again, a set of such keys can be released). The third category is mainly of theoretical interest as it does not correspond to actual or practical bounds on court orders.
Data Recovery Component
Capabilities. The scheme would support real-time decryption.
Data encryption key recovery. Once keys are obtained from the escrow agents, the DRC can determine the key needed to decrypt the DRF and obtain the session key.
References
Arjen K. Lenstra, Peter Winkler, and Yacov Yacobi, "A Key Escrow System with Warrant Bounds," Proc. Crypto '95, pp. 197-207.
This version of Lotus Notes uses differential workfactor cryptography. Data are encrypted with 64-bit keys. 24 of these bits are encrypted under a public key of the U.S. government and transmitted with the data. The government can determine the full key by searching over the remaining 40 bits, however, any other party must search the full 64-bit key space.
User Security Component
Application domain. Groupware application.
Data encryption algorithm.. The algorithm uses 64-bit data encryption keys.
Stored identifiers and keys. Each product is loaded with a public RSA key of the U.S. government.
Data recovery field and mechanism. Whenever data are encrypted, they are bound to a Workfactor Reduction Field. The WRF contains 24 bits of the data encryption key encrypted under the government's public key. The receiver verifies that the WRF is attached to the data and correct by recomputing it.
Implementation. Software.
Key Escrow Component
Escrow agents. This is a U.S. government agency.
Data recovery keys. The government has a global private RSA data recovery key.
Data recovery services. The government escrow agent would decrypt and release the 24 bits in the WRF.
Data Recovery Component
Capabilities. The scheme would not support real-time decryption because of the need to brute-force 40 bits.
Data encryption key recovery. After the 24-bits are obtained through the WRF, the remaining 40 bits are obtained by brute force search.
References
Lotus Backgrounder, "Differential Workfactor Cryptography," Lotus Development Corp.; distributed at RSA Data Security Conference, Jan. 17, 1996.
Silvio Micali has proposed various techniques for implementing key escrow encryption with optional time-bounded data recovery. His techniques apply to systems that use public key cryptography for key establishment or data encryption. Users must escrow their private keys in order to put their public keys in the public key infrastructure, thereby preventing someone from taking advantage of the public key infrastructure to distribute keys that could be used to preclude authorized government access. Keys can be split and escrowed using an "n out of n" or "k out of n" verifiable secret sharing scheme.
User Security Component
Application. Some of the techniques could be applied both to communications and to files.
Data encryption algorithm. The techniques apply to the RSA public key cryptosystem or to any single-key cryptosystem when the keys are established using the Diffie-Hellman public key distribution scheme or the RSA cryptosystem.
Stored identifiers and keys. Each user has a unique identifier and unique public-private key pair (KUpub, KUpriv), denoted as (E, D). In a time-bounded variant, each user also has an additional secret value which we denote by KUTpriv. All of these keys could be changed.
Data recovery field and mechanism. The user's public-private key pair is used either to establish a session key (e.g., using Diffie-Hellman or RSA) for use with a single-key cryptosystem or for data encryption (e.g., using RSA). The time-bounded variant follows the former approach, and derives the session key from KUTpriv and the date. The session key is made available through the key establishment protocols, which serve the role of a DRF.
Implementation. Software or hardware.
Key Escrow Component
Escrow agents. There can be any number of escrow agents. His examples use 5.
Data recovery keys. Users generate their own (KUpub, KUpriv) pairs and escrow the KUpriv component with escrow agents of their choice. The splitting is done using verifiable secret sharing techniques that enable the escrow agents to check the validity of their individual components without knowing the original key. The splitting can be done with an "n out of n" scheme or with a "k out of n" threshold scheme. After KUpriv is successfully registered with the escrow agents, the escrow agents sign a public key certificate containing KUpub. The certificate is placed in the public key infrastructure. KUpub cannot be placed in the infrastructure without this certificate. In the time bounded variant, KUTpriv also is split and stored in escrow.
Data recovery services. The escrow agents combine their components to form KUpriv, which is released to the DRC. In the time bounded variant, the escrow agents do not release KUpriv, but rather a derivative of KUTpriv, which allows the DRC to compute the session key during a specific period of time.
Data Recovery Component
Capabilities. The schemes could support post-processing decryption of recorded communications, but not necessarily real time decryption, depending on whether the key establishment protocols allow a session key to be recovered using the private key of the sender or receiver.
Data encryption key recovery. After obtaining KUpriv for a given user from the escrow agents, the DRC is able to extract the session key KS from any key establishment protocol data that enables recovery of KS with KUpriv. This can be done without further communication with the escrow agents.
Safeguards. In the time bounded variant, the DRC is able only to compute the session key between the specified dates.
References
Silvio Micali, "Fair Cryptosystems," MIT/LCS/TR-579.c, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 1994.
Silvio Micali has extended his concept of fair cryptography to include partially escrowed keys. The private keys of users are escrowed in such manner that the escrow agents can verify that the bits in their possession are correct and that only a relatively small number of bits are unescrowed. Here we describe only those features that distinguish it from Micali's general approach.
Key Escrow Component
Data recovery keys. A user's private key is partially escrowed in such manner that the escrow agents can verify that the bits in their possession are correct and that only a relatively small number of bits are unescrowed. This is done through a zero-knowledge proof that the bits withheld are suitably short with respect to those that are escrowed. Micali gives protocols based on Diffie-Hellman and on RSA.
Data Recovery Component
Data encryption key recovery. After obtaining the escrowed portion of a user's private key from the escrow agents, the DRC obtains the remaining bits by computing the discrete log (in the case of Diffie-Hellman) or factoring (in the case of RSA).
References
Silvio Micali, "Guaranteed Partial Key-Escrow," MIT/LCS/TM-537, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1995.
Silvio Micali and Ray Sidney propose a method for key escrow that could be used with a Clipper-like key escrow system, where separate components of a device unique key are escrowed with different escrow agents. Their method allows some of the escrow agents to "gossip" (compromise their key components) and some to "withhold" (fail to produce their key components). Here we describe only those aspects of their scheme that are substantially different from Clipper.
Key Escrow Component
Escrow agents. There are n key escrow agents. Subsets (possibly overlapping) of agents are formed into a combinatorial object called an (n, t, u)-resilient collection, where t is an upper bound on the number of "gossipy" escrow agents (agents who might compromise their keys), (n-u) is an upper bound on the number of "withholding" escrow agents (agents who might refuse to cooperate with the authorities), and t < u n.
Data recovery keys. Each subset of escrow agents has a unique seed that is generated by the subset and shared by all its members. This seed is used with the unique identifier of a chip to compute that subset's key component for the device unique key of the chip. To initialize the key for a particular chip, each escrow agent generates the chip's key component for all subsets that the agent belongs to and transmits these to the chip. The chip XORs a key component from each subset to form the device unique key.
Data recovery services. The escrow agents compute and release the key components for a particular chip (as for Clipper).
References
Silvio Micali and Ray Sidney,"A Simple Method for Generating and Sharing Pseudo-Random Functions, with Applications to Clipper-Like Key Escrow Systems," Crypto '95, pp. 185-196.
Commercial Automated Key Escrow (CAKE) is an implementation of the TIS Commercial Key Escrow (CKE) system using the National Semiconductor PersonaCard^TM. The goal is an exportable product that combines a strong encryption algorithm with a data recovery capability. The PersonaCard is a PCMCIA card with cryptographic functions for encryption and authentication.
References
W. B. Sweet, "Commercial Automated Key Escrow (CAKE): An Exportable Strong Encryption Proposal," National Semiconductor, iPower Business Unit, June 4, 1995.
James Nechvatal at NIST has proposed a key escrow system which uses public key techniques based on Diffie-Hellman for escrowing keys and generating a Law Enforcement Access Field. Keys are escrowed using verifiable secret sharing techniques and can be changed. The proposal can accommodate unclassified algorithms and hardware or software implementations.
User Security Component
Application. Communications, but the techniques could be applied to stored files.
Data encryption algorithm. Any single-key algorithm.
Stored identifiers and keys. Each USC has a unique identifier UID and a unique public-private key pair (KUpub, KUpriv). The public key is stored in the USC. The program also contains the public family key, KFpub, and the public key, KEFpub, of the Key Escrow Facility.
Data Recovery Field. The DRF, which is called a Law Enforcement Access Field (LEAF), contains the session key KS encrypted under KUpub and KFpub. The receiver validates the LEAF by recomputing it. To facilitate this, the sender also transmits a certificate for KUpub signed by the Key Escrow Facility with KEFpriv.
Implementation. Software or hardware.
Key Escrow Component
Escrow agents. There can be any number of escrow agents.
Data recovery keys. The user's key KU can be generated by the user, the USC, or the escrow agents. KU is split among the agents using an "n out of n" verifiable secret sharing technique based on Diffie-Hellman (a "k out of n" approach is also possible). The method, which is similar to one of Micali, enables the escrow agents to check the validity of their individual components without knowing KUpriv. In fact, KUpriv need not be generated at all until it is needed for data recovery. After the components of KUpriv are successfully registered with the escrow agents, the Key Escrow Facility signs a public key certificate containing UID and KUpub. Escrowed keys can be changed.
Data recovery services. The escrowed key components are combined to form KUpriv, which is released to the DRC.
Data Recovery Component
Capabilities. Since data recovery requires access to the private key of tbe sender, real-time decryption is possible only for communications from the subject and for two-way interactive communications where the same session key is used in both directions.
Data encryption key recovery. After obtaining KUpriv for a given user from the escrow agents, the DRC acquires the session key by decrypting the LEAF using KUpriv and KFpriv.
Safeguards. Keys can be changed following the end of a period of authorized surveillance. This might be done by downloading a new key into the subject's USC.
References
James Nechvatal, "A Public-Key Based Key Escrow System," J. of Systems and Software, to appear Oct. 1996.
This commercial product supports enterprise-wide encryption and digital signatures through a high level application programming interface. User's private encryption keys are archived as part of the certificate authority function and public-key infrastructure.
User Security Component
Application domain. Files and electronic mail.
Data encryption algorithm. The product supports DES and Nortel's proprietary CAST. CAST can operate with different key lengths.
Stored identifiers and keys. Users have public-private keys for encryption and digital signatures.
Data recovery field and mechanism. Whenever data are encrypted, the data encryption key is encrypted under the public key of all recipients (the sender is an implied recipient) and attached to the data. The DRF serves a dual role of key distribution and data recovery.
Implementation. The system can be used with optional hardware tokens.
Key Escrow Component
Escrow agents. Entrust key managers serve as public-key certificate authorities and escrow agents.
Data recovery keys. The key manager generates the user's private encryption key, transfers it to the client, and keeps a backup copy. (Digital signature keys are generated by the clients and are not escrowed).
Data recovery services. A user's private encryption key can be released.
Data Recovery Component
Capabilities. The system could support real-time decryption.
Data encryption key recovery. Once a particular user's key has been obtained, the key can be used to decrypt the data encryption key in the DRF of any document sent or received by the user.
References
Warwick Ford, "Entrust Technical Overview," White Paper, Nortel Secure Networks, Oct. 1994.
This is a commercial product that provides a range of security services, including boot protection, access controls, audit trail, anti-virus and piracy protection, single sign-on, trusted processes, and encryption. Key escrow is a built-in feature of the key management infrastructure.
User Security Component
Application domain. Communications and files.
Data encryption algorithm. The product uses proprietary algorithms.
Stored identifiers and keys. The system uses two types of keys: 1) for local storage, network storage, and exchange; and 2) for use with user roles.
Data recovery field and mechanism. There is no DRF.
Implementation. Can support both hardware (smart cards) and software.
Key Escrow Component
Escrow agents. A key generating and issuing center is responsible for generating and distributing keys. The center keeps a copy of all keys in an escrow database. The escrowed database can be split.
Data recovery keys. These are the keys generated by the center.
Data recovery services. The key center can regenerate and release a key when needed.
Safeguards. The escrow database is protected by access controls and authentication mechanisms.
References
Stoplock Press, PC Security, Ltd., Marlow, Buckinghamshire, UK, Issue 3, Nov. 1995.
Nigel Jefferies, Chris Mitchell, and MIchael Walker of Royal Holloway, University of London, propose an architecture for Trusted Third Party Services with key escrow which allows messages sent from or received by a user to be decrypted using the user's private keys. The architecture uses a Diffie-Hellman key exchange and requires that the TTPs associated with pairs of communicating users have common parameters and a secret key.
User Security Component
Application domain. Communications.
Data encryption algorithm. Any encryption algorithm can be used
Stored identifiers and keys. Each user is registered with a Trusted Third Party (TTP). For user A, this is denoted TA. User A has a unique public-private send key and a unique public-private receive key for each TB such that A communicates with some user B registered with TB. TA and TB share a prime p, an element g, and a secret key K(TA,TB). A's private send key is a random value x where 1< x < p-1; A's public send key is g^x mod p. A's private receive key is a value 1 < a < p-1 which is derived deterministically from A's name and K(TA,TB); A's public receive key is g^a mod p. A's USC contains these keys as well as keys for other functions, for example, digital signatures. In addition, it contains TA's verification key and the verification keys of all TBs that have registered users who communicate with A.
Data recovery field and mechanism. To send an encrypted message to user B, user A first obtains B's public receive key from TA. (TA can compute B's private receive key from B's name and K(TA,TB)). A then derives a shared key from A's private send key and B's public receive key: (g^b mod p)^x mod p = g^xb mod p. This key is then used as the session key or to encrypt the session key. A transmits its public send key signed by TA and the public receive key of B to B. This information serves the dual role of a DRF and of distributing the shared key to B. (Upon receipt, B verifies A's public send key and computes the shared key from A's public send key and B's private receive key.)
Implementation. Hardware or software is possible.
Key Escrow Component
Escrow agents. The Trusted Third Parties serve the role of escrow agents.
Data recovery keys. Each pair of TTPs TA and TB with potentially communicating users generates shared values p, g, and K(TA,TB) (p and g could be shared among multiple TTPs. The private send keys of registered users are generated and retained by the users' TTP or else generated by the users and escrowed with their TTPs. The receive private keys need not be escrowed as the TTPs can generate them on demand through the deterministic process.
Data recovery services. The TTP releases the private send and receive keys of a registered user.
Data Recovery Component
Capabilities. Real-time decryption and post-processing decryption of recorded communications are possible.
Data encryption key recovery. An authorized person would contact the TTP of a particular user in order to acquire that user's private send and receive keys. Then, all communications transmitted or received by that user can be decrypted using the key establishment data (i.e., DRF).
Safeguards. Keys could be split among multiple TTPs using some method of secret sharing.
References
Nigel Jefferies, Chris Mitchell, and Michael Walker, "A Proposed Architecture for Trusted Third Party Services," Royal Holloway, University of London, 1995.
Ben Laurie, "A Supplementary Analysis of the Royal Holloway TTP-based Key Escrow Scheme", A. L. Group, 16 Nov 1996, http://www.algroup.co.uk/crypto/rh.html.
RSA Secure is a file encryption product of RSA Data Security, Inc. The file encryption key is stored in a file header encrypted under an escrowed master publc key. The master key can be split among up to 8 trustees using a threshold scheme.
User Security Component
Application domain. Files.
Data encryption algorithm. RC4 with 80 bit keys.
Stored identifiers and keys. Each program copy is loaded with the public master key of the organization.
Data Recover Field. The file encrytion key K is encrypted under the organization's public master key using the RSA algorithm. This field is attached to the file.
Implementation. Software.
Key Escrow Component
Escrow agents. There can be up to 8 trustees. These are selected by the organization.
Data recovery keys. The private master key is generated by the system administrator and stored in escrow. It can be split with a "k out of n" threshold scheme using Bloom-Shamir secret sharing techniques.
Data recover services. The escrow agents enter their components, sequentially, in order to decrypt a key K.
Data Recovery Component
Data encryption key recovery. The escrow agents can be given the DRF in order to decrypt the session key.
References
RSA Secure^TM, product literature from RSA Data Security, Inc.
Adi Shamir proposes to escrow all but 48 bits of a long (256-bit) key. These 48 bits are generated randomly for each session or file, while the escrowed bits remain fixed. For data encryption, the entire 256-bit key is hashed down to the key length of the encryption algorithm. For data recovery, the 48 random bits are determined by brute force.
User Security Component
Application domain. Communications or files.
Data encryption algorithm. Any single-key algorithm.
Stored identifiers and keys. Each USC has a secret 208-bit key. Users can choose their own keys or use the key supplied by a product. Whenever data are encrypted, a random 48-bit value is appended to this key. The resulting 256 bits is hashed to the key length used by the encryption algorithm. The numbers 208 and 48 are somewhat arbitrary. They could be user or product dependent and could change over time. The objective is to make a brute force attack impossible without the escrowed key and difficult, but not impossible, when the key is known.
Data recovery field and mechanism. This is unspecified, but would include information identifying the user and/or product. The USC does not generate a random 48-bit key and encrypt data unless presented with a certificate for the 208-bit value signed by the escrow agent.
Implementation. Unspecified, but could be software or hardware.
Key Escrow Component
Escrow agents. These could be any trusted entities.
Data recovery keys. The secret 208-bit keys are escrowed. These keys are generated by users or product manufacturers and escrowed through a request that specifies a program ID, a user ID, a 208-bit random value, and 48 *'s. The escrow agent returns a signed receipt for the request consisting of a DSS signature of the escrowed information.
Data recovery services. The KEC releases the 208-bit value.
Data Recovery Component
Data encryption key recovery. After obtaining the 208-bit key, the DRC does a brute force attack over the remaining 48 bits. This is estimated to take 1 minute on special purpose hardware.
References
Adi Shamir, "Partial Key Escrow: A New Approach to Software Key Escrow," The Weizmann Institute, presentation at NIST Key Escrow Standards meeting, Sept. 15, 1995.
VEIL^TM is a cryptographic product of TECSEC, Inc. which provides file (and object) encryption with a private key escrow capability. All file encryption keys are derived from a set of "sub-key splits" that are managed by the organization. When a file is encrypted, a header is attached to the file. The header contains pointers to the sub-key splits and serves both as a mechanism for distributing the key to persons authorized to access the file and as a data recovery field. The key can be recovered only if one has all of the sub-key splits used to create the key.
User Security Component
Application domain. Stored files and objects, including messages within an organization.
Data encryption algorithm. Up to ten different encryption algorithms can be used with VEIL at a given time. The product ships with four modes of DES (including triple DES) and TECSEC proprietary P2. Users can add their own algorithms.
Stored identifiers and keys. Each file is encrypted with a key that is derived from ten "sub-key splits" provided by the USC. Four of these are "pre-positioned," 2 in VEIL and 2 in the user's workstation, and are common throughout an organization. Another four are associated with the four labels "codeword," "subject," "to," and "location," and are taken from label sets defined by the organization (e.g., an organization may define 100 different "subject" labels and a "to" label for each employee and work unit). Each user has read and write subsets of the sub-key splits for each label set, which are stored on an encrypted "key disk" belonging to the user. The final two sub-key splits are derived from the file name and a day-time stamp, so that all keys are unique. All keys and sub-key splits are 64 bytes long.
Data recovery field and mechanism. The key used to encrypt a particular file is made available through a 1024-byte header that is attached to the file and serves as a DRF. The header contains pointers to the appropriate sub-key splits and is used by the intended recipient to obtain the key. The key can be recovered only if one has all of the sub-key splits used to create the key.
Implementation. VEIL is a stand alone Windows application which can be interfaced into Windows applications. It works with both hardware and software implementations of encryption algorithms.
Key Escrow Component
Escrow agents. An organization serves as its own internal escrow agent. The system could be used with up to four outside agencies.
Data recovery keys. The organization has copies of all the sub-key splits used to derive file encryption keys. Some of these splits can be held by separate entities within an organization or by outside agencies in an "n out of n" scheme. The organization generates its labels and seeds with a "label maker" product. It then uses a "key disk" product to build a particular user's key disk with a subset of the label sub-key splits, depending on the user's access privileges. It also uses a "workstation setup" product to set up the pre-positioned sub-key splits on a particular workstation. Different employees in the organization could perform each of these tasks so that no one person would have access to all of the sub-key splits.
Data recovery services. The KEC could take a given DRF (file header) and use the information in the header to re-generate the key using its own sub-key splits. In the case where a user's key disk is lost or damaged, it could generate a new disk for the user.
Safeguards. The system has auditing capabilities.
Data Recovery Component
Capabilities. VEIL could support post-processing of messages, but probably could not support real-time decryption of intercepted communications since law enforcement officials would have to go through the KEC to recover each key.
Data encryption key recovery. To obtain the key for a particular file, the DRF would be extracted and given to the KEC, which would return the key.
Safeguards. The KEC controls which objects are decrypted.
References
Edward M. Scheidt and Jon L. Roberts, "Private Escrow Key Management," TECSEC Inc., Vienna, VA. See also TECSEC VEIL product literature. Additional information was provided by Edward Scheidt and Graig Shanton of TECSEC.
The Exponential Security System (TESS) is a toolkit of cryptographic mechanisms and functions based on discrete exponentiation developed at the University of Karlsruhe. The private keys of users are split and escrowed in a global access structure. The DRC obtains a particular session key by participating in the key establishment protocol between the sender and receiver during a period of authorized surveillance.
User Security Component
Application domain. Although TESS applies both to stored files and communications, the data recovery capability described here is designed for interactive two-party communications.
Data encryption algorithm. The design allows for different encryption algorithms.
Stored identifiers and keys. A user's USC contains several global system parameters, the user's identifier (UID), a public-private key pair (KUpub, KUpriv), which is used for key establishment, and a private value KUTpriv, which is used during key establishment to enable data recovery. (For a user A, these values are denoted (pA, sA) and tA respectively).
Data recovery field and mechanism. There is none.
Implementation. Smart cards (for user keys) plus software.
Key Escrow Component
Escrow agents. The design leaves unspecified the number of escrow agents. A monotone access structure is used for the escrowed keys so that arbitrary subsets of escrow agents can be specified for recovering keys.
Data recovery keys. The private key component KUpriv of a user's key establishment key is stored in escrow along with a value KUTesc, which is the result of a one-way function of KUTpriv. KUpriv is generated interactively between two smart cards, one belonging to the user and the other to a certificate center. The certificate center does not know KUpriv. KUTesc is generated on the user's card. The user's card puts the keys into escrow. Keys are escrowed into a monotone access structure using verifiable secret sharing techniques based on computational geometry.
Data recovery services. For a given user, the KEC makes the private key KUpriv available to the DRC along with two values derived from KUTesc by a one-way function. This need be done only once for each user.
Data Recovery Component
Capabilities. The system would support real-time decryption, but is designed to prohibit post-processing decryption of recorded communications.
Data encryption key recovery. Whenever two parties want to communicate, they establish a session key through a protocol that requires participation by a third party. The third party provides parameters that are used by the sender and receiver to generate a shared session key KS. Normally, the third party is a network service, which is unable to determine what session key is established. When data recovery is authorized, the DRC acquires KUpriv and the values derived from KUesc for the subject of an investigation from the escrow agents and then participates in the key establishment protocol. With these values, it can compute KS. The protocol uses public key techniques with modular exponentiations in a field GF(p) for prime p.
Safeguards. The DRC is allowed to participate in network key establishment protocols only during the period of authorized surveillance. If this is enforced, then it will be unable to decrypt any other communications.
References
Thomas Beth, Hans-Joachim Knobloch, and Marcus Otten, "Verifiable Secret Sharing for Monotone Access Structures," Proc. 1st ACM Conf. on Communication and Computer Security, 1993.
Thomas Beth, Fritz Bauspieß, Hans-Joachim Knobloch, and Steffen Stempel, "TESS: A security system based on discrete exponentiation," Computer Communications, Vol. 17, No. 7, July, 1994, pp. 466-475.
Thomas Beth, Hans-Joachim Knobloch, Marcus Otten, Gustavus J. Simmons, and Peer Wichmann, "Towards Acceptable Key Escrow Systems," Proc. 2nd ACM Conf. on Communication and Computer Security, 1994, pp. 51-58.
With threshold decryption, a secret key can be shared by a group of escrow agents in such a way that through collaboration of the agents, information can be decrypted without the agents releasing their individual key components. However, the escrow agents must participate in the decryption of each session key.
User Security Component
Application domain. Communications, but concepts could be used with stored data.
Data encryption algorithm. The method could be used with any single-key cryptosystem.
Stored identifiers and keys. Each user has a unique identifier (UID) and public-private key pair (KUpub, KUpriv), which is used for key establishment.
Data recovery field and mechanism. The sender generates a session key and transmits it to the receiver encrypted under the receiver's public key using a variant of El Gamal that provides threshold decryption. In addition, the sender transmits a DRF which includes the UID encrypted under a common family key and a value R, which is used by the DRC to recover the encrypted session key. The method can be used with a variant of RSA, but it is less practical.
Key Escrow Component
Escrow agents. The method assumes at least two escrow agents.
Data recovery keys. Each user generates a public-private key pair and splits and escrows a component of KUpriv with each escrow agent using a "k out of n" secret sharing scheme. The escrow agents verify that the components are correct either by running a test threshold decryption or by using verifiable secret sharing.
Data recovery services. The escrow agents do not release their key components, but rather use them to compute a function of the value R passed in the DRF. They must do this for each session key.
Implementation. This could be software.
Data Recovery Component
Capabilities. The approach could support post-processing decryption of recorded communications, but may not support real time decryption because of the need for the escrow agents to participate in each decryption.
Data encryption key recovery. After extracting the DRF and encrypted session key KS from the communications stream, the DRC decrypts the UID in the DRF with the family key. It then transmits UID and R to the escrow agents. Each escrow agent computes a one-way function of R using its private key component for that UID. The results are transmitted back to the DRC, which combines them to produce a value R'. The DRC multiples R' by the encrypted session key to get the session key KS. The escrow agents never know KS.
Safeguards. Since the escrow agents must participate in each decryption, they can limit decryption to a period of authorized surveillance.
References
Yvo Desmedt, Yair Frankel, and Moti Yung, "A Scientific Statement on the Clipper Chip Technology and Alternatives," 1993.
The concept of threshold decryption was introduced by Desmedt at Crypto '87.
CKE is a commercial key escrow system for stored data and file transfers. The functions performed by the Key Escrow Component are performed by an entity called a Data Recovery Center. Each time information is encrypted, a data recovery field is created and attached to the encrypted data. The DRF contains the data encryption key (or any other data) encrypted under a master public key belonging to the Center. The Center decrypts this key (or data) for each authorized data recovery operation. TIS will license CKE and Date Recovery Centers.
User Security Component
Application. Stored data and file transfers, including electronic mail.
Data encryption algorithm. This could be anything, but TIS is using DES in current products.
Stored identifiers and keys. Each USC registers with a Data Recovery Center by sending the Center user authentication information. Upon registration, it receives the identifier CI of the Data Recovery Center and the Center's public key, DRCpub. This key could be changed. It also is assigned a unique user index, UI.
Data recovery field and mechanism. A session (file) key KS is made available through a DRF. KS and the user index UI are encrypted under the public key of the Center and appended to the Center Identifier CI.
The system could put out a DRF associated with both the sender's and receiver's Data Recovery Center if access from both ends is desired.
Implementation. Software or hardware. TIS has applied for export licenses for TrusteMail^TM using DES/RSA in software and in the National Semiconductor Persona 201 card (see CAKE).
Key Escrow Component (Data Retrieval Center)
Escrow agents. There is a single escrow agent called a Data Recovery Center. This is a commercial entity. The center could be licensed and bonded
Data recovery keys. The Center generates a master public-private key pair at the time it is initialized. The private key, DRCpriv, is the only key held in escrow. The public key DRCpub is transmitted to a User Security Component at the time it initializes itself with the Center or re-initializes itself to get a new DRCpub. The Center's master key can be changed. The DRCs use RSA public-key cryptography.
Data recovery services. The Center decrypts a DRF and returns the decrypted data. Although this is typically a session key, it could be a password, passphrase, PIN, user private key, etc.
Data Recovery Component
Capabilities. The system could support post-processing decryption of recorded communications. It might support real-time decryption if the Center is on-line and can decrypt the DRFs in real-time.
Data encryption key recovery. An individual user presents a DRF to the Center. After authenticating the user, the DRC decrypts the DRF and returns the session key (or other data). Communications between the user and DRC are encrypted.
Safeguards. The Center controls emergency decryption of each document or message that is encrypted under a unique session key.
References
Stephen T. Walker, Stephen B. Lipner, Carl M. Ellison, and David M. Balenson, "Commercial Key Recovery," Comm. ACM, Mar. 1996.
The Trusted Information Systems software key escrow system is similar to Clipper, but uses software rather than hardware. Like Clipper, it is LEAF based and assigns a unique key to each User Security Component (program instance). However, in order to avoid putting either secret algorithms or secret keys in software, it uses unclassified algorithms and public key cryptography for key escrow functions. TIS has built a prototype of their design that runs on a Sun workstation and handles interactive communications.
User Security Component
Application. Communications, but the techniques could be applied to stored files.
Data encryption algorithm. The design is based on a single key, unclassified algorithm. The prototype uses triple DES.
Stored identifiers and keys. Each program instance has a unique identifier UIP and a unique public-private key pair (KUpub, KUpriv). The public key is stored in the program. The program also contains the public family key, KFpub, and a public key, KEPFpub, of the Key Escrow Programming Facility.
Data recovery field and mechanism. A session key KS is made available through a DRF called a Law Enforcement Access Field (LEAF) as for Clipper. The LEAF is computed using only public keys:
Unlike the EES, the LEAF does not contain an escrow authenticator. This is because the receiver can validate the LEAF by recomputing it. To facilitate this, the sender also transmits an Escrow Verification String (EVS) which contains UIP, KUpub, and a certificate for KUpub signed under the private key component of the Key Escrow Program Facility (KEPF). All this in encrypted under the session key KS:
Implementation. Software.
Key Escrow Component
Escrow agents. Like Clipper, the design allows for any number of agents in an "n out of n" scheme. The prototype uses two escrow agents. The escrow agents could be authorized government agencies as for Clipper or they could be commercial key escrow centers.
Data recovery keys. The private key component KUpriv of a program instance is stored in escrow as a split key, KUpriv1 and KUpriv2, where KUpriv = KUpriv1 XOR KUpriv2. Keys are generated at a Key Escrow Programming Facility (KEPF). For each program instance, the facility generates a UIP, KUpub, KUpriv, KUpriv1, and KUpriv2. The KEPF then places the following items in the software: KEPFpub, KFpub, UIP, KUpub, and a signed certificate S[KEPFpriv](UIP | KUpub) and gives KUpriv1 and KUpriv2 to the escrow agents. The general approach could accommodate the generation and escrowing of keys at program installation time. In that case, the program would dial-up the KEPF and receive its keys online. A program would not be operable unless it was "key escrow enabled." With online distribution of keys, the KEPF might also provide a capability for changing keys.
Data recovery services. For a given UIP, the KEC makes the private key components, KUpriv1 and Kupriv2, available to the DRC in much the same way as with Clipper. This need be done only once for each UIP.
Data Recovery Component
Capabilities. Like Clipper, the system could support real-time decryption, at least for two-way simultaneous communications when the same session key is used in both directions, and post-processing decryption of recorded communications.
Data encryption key recovery. The DRC closely imitates that of Clipper.
Safeguards. If users are allowed to change their program unit keys, then decryption could be limited to the time when a particular key was in use.
References
Stephen T. Walker, Stephen B. Lipner, Carl M. Ellison, and David M. Balenson, "Commercial Key Recovery," Comm. ACM, Mar. 1996.
David M. Balenson, Carl M. Ellison, Steven B. Lipner, and Stephen T. Walker, "A New Approach to Software Key Escrow Encryption," Trusted Information Systems, 3060 Washington Rd., Glenwood, MD, draft of August 15, 1994.
This system is similar to the TIS system paralleling Clipper except that it uses escrowed master keys rather than individual program keys and requires that the escrow agents be online and participate in each authorized data recovery operation. Here we identify only those characteristics that are inherently different from the TIS software Clipper-like approach.
User Security Component
Stored identifiers and keys. Each program instance contains the public keys, KEA1pub and KEA2pub, of public-private master keys belonging to the escrow agents. It does not have any unique values of its own, at least for use with the Data Recovery Component.
Data recovery field and mechanism. The session key KS is split into two components, KS1 and KS2, such that KS = KS1 XOR KS2. The LEAF is then computed as:
The receiver validates the LEAF by recomputing it. To facilitate this, the sender also transmits an Escrow Verification String (EVS) which contains KS1 and KS2 encrypted under KS:
Key Escrow Component
Data recovery keys. The escrow agents generate master public-private key pairs at the time the KEC is initialized and respectively hold KEA1priv and KEA2priv in escrow. The public keys, KEA1pub and KEA2pub, are inserted into all copies of the software implementing the User Security Component.
Data recovery services. The KEC makes the session key components KS1 and KS2 available to the DRC. It must do this for each communication.
Data Recovery Component
Capabilities. The need to involve the KEC in the decryption of each session key may preclude real-time decryption.
Data encryption key recovery. After intercepting the LEAF of a particular communication, the DRC sends E[KEA1pub](KS1) to escrow agent 1 and E[KEA2pub](KS2) to escrow agent 2. The escrow agents return KS1 and KS2 respectively. The DRC then constructs KS. This process must be repeated for each communication.
References
David M. Balenson, Carl M. Ellison, Steven B. Lipner, and Stephen T. Walker, "A New Approach to Software Key Escrow Encryption," Trusted Information Systems, 3060 Washington Rd., Glenwood, MD, draft of August 15, 1994.