Dorothy E. Denning, Georgetown University
Dennis K. Branstad, Trusted Information Systems
May 11, 1997
A key recovery encryption system (or recoverable encryption system) is an encryption system with a backup decryption capability that allows authorized persons (users, officers of an organization, and government officials), under certain prescribed conditions, to obtain the keys needed to decrypt ciphertext. Access to a decryption key is facilitated by information held by one or more trusted parties plus information attached to the ciphertext. The information held by the trusted parties typically includes special recovery keys. The term key escrow is sometimes used to refer to systems in which the recovery keys are the private keys of users; it is also used synonymously with key recovery. Other terms used include key archive, key backup, and data recovery.
This paper presents a taxonomy for key recovery encryption. The taxonomy is intended to provide a structure for describing and categorizing the recovery mechanisms of complete systems as well as various design options. Table 1 applies the taxonomy to several key recovery products or proposals. The paper is a revision of "A Taxonomy of Key Escrow Encryption," Communications of the ACM, Vol. 39, No. 3, March 1996, pp 34-40.
A recoverable encryption system can be divided logically into three main components:
User Security Component (USC). This is a hardware device or software program that provides data encryption and decryption capabilities as well as support for the key recovery function. This support typically includes attaching a data recovery field (DRF) to encrypted data. The DRF may be part of the normal key distribution mechanism.
Recovery Agent Component (RAC). This component, which is operated by key recovery agents, manages the storage and release or use of recovery keys and other information that facilitates decryption. It may be part of a public-key certificate management system or part of a general key management infrastructure.
Data Recovery Component (DRC). This consists of the algorithms, protocols, and equipment needed to obtain the plaintext from the ciphertext plus information in the DRF and provided by the RAC. It is active only as needed to perform a specific authorized data recovery.
These logical components are highly interrelated, and the design choices for one affect the others.
Figure 1 illustrates the interaction of the components. A USC encrypts plaintext data with a key K and attaches a DRF to the ciphertext. The DRC recovers the plaintext using information contained in the DRF plus information provided by the RAC.
Each of these components is described in the following sections.
The USC encrypts and decrypts data and performs functions that support the data recovery process. It is characterized by:
Application Domain. A USC can support either or both of the following:
Stored Identifiers and Keys. The USC stores identifiers and keys that are used for emergency decryption:
Recovery field and Mechanism. When data are encrypted with a key K, the USC must bind the ciphertext and K to recovery information, normally by attaching a data recovery field (DRF) to the encrypted data. The binding is characterized by:
Interoperability. A USC may be designed to interoperate only with correctly functioning USCs and not with USCs that have been tampered with or that do not support key recovery.
Implementation. A USC may be implemented in hardware, software, firmware, or some combination thereof. Hardware is generally more secure and less vulnerable to modification than software. If classified algorithms are used, they must be implemented in tamper resistant hardware. Hardware implementations may include special purpose crypto processors, random number generators, and/or a high-integrity clock.
Products that implement a USC are sometimes called recoverable encryption products (or devices). They have also been called escrow-enhanced or escrow-enabled products.
Assurance . The USC may provide assurance that users cannot circumvent or disable the key recovery mechanisms or other features. A USC that can be used or modified to "cheat" is called a rogue USC. The possibility of rogue USCs is strongly dependent on the recovery mechanism and implementation. We distinguish between single rogues, which can interoperate with non-rogues, and dual rogues, which interoperate only with other rogues. Single rogues present the greatest threat to emergency data recovery because they require no collaboration on the part of the receiver.
The RAC is responsible for storing recovery keys and other information needed for key recovery, and for assisting the Data Recovery Component by providing required data or services. It has the following elements:
Role in Key Management Infrastructure. The RAC could be a component of the key management infrastructure, which could be a single key infrastructure (e.g., key distribution center) or public-key infrastructure. With the latter, the recovery agents could serve as the public-key certificate authorities, or they could be distinct entities.
Key Recovery Agents. The recovery agents, also called trusted parties, are responsible for operating the RAC. They may be registered with a key recovery center that coordinates their operation or serves as a point of contact for the USC or DRC. Recovery agents are characterized by:
Data Recovery Services. The RAC provides services, including release of information, to the DRC. It is characterized by:
The DRC supports recovery of plaintext from encrypted data using information supplied by the RAC and in the DRF. It is characterized by:
Capabilities. These include:
Data Encryption Key Recovery. To decrypt data, the DRC must acquire the data encryption key K.
Safeguards on Decryption. The DRC can use technical, procedural, and legal safeguards to control what can be decrypted. For example, data recovery may be restricted to a particular time period (as authorized by a court order). These safeguards supplement restrictions imposed by the RAC in its release of keys. Authentication mechanisms could be used to prevent the DRC from using the keys it acquires to create and substitute bogus messages.
We wish to thank Matt Blaze, Yvo Desmedt, Carl Ellison, Ravi Ganesan, Carmi Gressel, Hans-Joachim Knobloch, David Maher, Silvio Micali, Edward Scheidt, Greg Shanton, and Peer Wichmann for helpful comments on an earlier version of this taxonomy.
AT&T Crypto Backup. This is a proprietary design for a commercial system which backs up document keys through an archived master key. David P. Maher, "Crypto Backup and Key Escrow," Communications of the ACM, Vol. 39, No. 3, March 1996, pp. 48-53.
Bankers Trust Secure Key Escrow Encryption System (SecureKEES). Employees of a corporation register their encryption devices (e.g., smart card) and private encryption keys with one or more commercial recovery agents selected by the corporation. SecureKEES product literature, CertCo, Bankers Trust Company.
Bell Atlantic Yaksha System. An on-line key security server generates and distributes session keys and file keys using a variant of the RSA algorithm. The server transmits the keys to authorized parties for data recovery purposes. Ravi Ganesan, "The Yaksha Security System," Communications of the ACM, Vol. 39, No. 3, Mar. 1996, pp. 55-60.
Binding Cryptography. This approach allows a third party to validate whether the data encryption key is recoverable from the DRF. E. R. Verheul, B. J. Koops, and H. C. A. van Tilborg, "Binding Cryptography: A Fraud-Detectable Alternative to Key-Escrow Solutions," Computer Law and Security Report, January-February 1997, pp. 3-14.
Blaze's Smartcard-Based Key Recovery File System. This is a prototype smartcard-based key recovery system for use with the Cryptographic File System. A user entrusts a smart card with a file encryption key to a trusted party. Matt Blaze, "Key Management in an Encrypting File System," AT&T Bell Labs.
The Clipper/Capstone Chips. These tamper-resistant chips implement the Escrowed Encryption Standard (EES), which uses the classified Skipjack algorithm. Unique recovery keys, programmed onto each chip, are split between two government agencies and restricted to government use. Dorothy E. Denning and Miles Smid, "Key Escrowing Today," IEEE Communications, Vol. 32, No. 9, Sept. 1994, pp. 58-68. Click here for text version.
Cylink Key Recovery. This proposal uses Diffie-Hellman techniques for integrating key recovery services into a public-key infrastructure. Jim Omura, "Alternatives to RSA Using Diffie-Hellman with DSS," White Paper, Cylink, Sept. 1995.
Desmedt Traceable Ciphertexts. This proposal binds the DRF to ciphertext in such a way that the identity of the receiver can be determined if the receiver can determine the session key. 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.
Fortezza Card. This commercially available PC card contains a Capstone chip. A user's public-private encryption keys are stored on the card and can be escrowed with the user's public-key certificate authority.
Fortress KISS: Keep the Invaders (of Privacy) Socially Sane. This proposed system uses tamper-resistant encryption chips and master recovery keys. 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.
IBM SecureWay Key Recovery. Random numbers are encrypted under master public keys of the recovery agents and stored in the DRF. These are decrypted for key recovery; information derived from them is then used to decrypt the session key in the DRF. Partial key recovery is possible. "IBM SecureWay Key Recovery Technology," 1997.
Kilian and Leighton Failsafe Key Recovery. With this proposal, a user's keys are generated jointly by the user and key recovery agents so the user cannot circumvent key recovery. Joseph Kilian and Tom Leighton, "Fair Cryptosystems, Revisited," Proc. CRYPTO '95, pp. 208-221.
Leiberich Time-Bounded Clipper with a Clock. This proposed enhancement to Clipper offers time-bounded data recovery through a clock and date-dependent device unique keys. Otto Leiberich, private communication, June 1994.
Leighton and Micali Key Escrow with Key Agreement. With this proposal, each user has an escrowed private key. Any two users can compute a shared secret key from their own private key and the identifier of the other. Tom Leighton and Silvio Micali, "Secret-Key Agreement without Public-Key Cryptography," Proc. Crypto '93, pp. 208-221.
Lenstra, Winkler, and Yacobi Key Escrow with Warrant Bounds. 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. Arjen K. Lenstra, Peter Winkler, and Yacov Yacobi, "A Key Escrow System with Warrant Bounds," Proc. Crypto '95, pp. 197-207.
Lotus Notes International Edition (Differential Workfactor Cryptography). Data are encrypted with 64-bit keys, 24 of which are encrypted under a public key of the government and transmitted with the data. The government can obtain the remaining 40 bits through brute force. Lotus Backgrounder, "Differential Workfactor Cryptography," Lotus Development Corp. 1996.
Micali Fair Public Key Cryptosystems. Verifiable secret sharing techniques are proposed whereby users generate, split, and escrow their private keys with escrow agents of their choice as a prerequisite to putting their public keys in the public key infrastructure. Silvio Micali, "Fair Cryptosystems," MIT/LCS/TR-579.c, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 1994.
Micali Guaranteed Partial Key-Escrow. Under this proposal, the private keys of users are partially escrowed. The escrow agents verify that the bits in their possession are correct and that only a relatively small number of bits are unescrowed. Silvio Micali, "Guaranteed Partial Key-Escrow," MIT/LCS/TM-537, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1995.
Micali and Sidney Resilient Clipper-Like Key Escrow. This proposal allows keys to be split so that recovery is possible even if some of the escrow agents compromise or fail to produce their key components. Silvio Micali and Ray Sidney, "A Simple Method for Generating and Sharing Pseudo-Random Functions, with Applications to Clipper-Like Key Escrow Systems," Proc. Crypto '95, pp. 185-196.
National Semiconductor CAKE. This proposal combines a TIS key recovery system with National's PersonaCardTM. W. B. Sweet, "Commercial Automated Key Escrow (CAKE): An Exportable Strong Encryption Proposal," National Semiconductor, iPower Business Unit, June 4, 1995.
Nechvatal Public-Key Based Key Escrow System. This proposal uses Diffie-Hellman public-key techniques for escrowing keys and for data recovery. James Nechvatal, "A Public-Key Based Key Escrow System," J. of Systems and Software, to appear Oct. 1996.
Nortel Entrust. This commercial product archives user's private encryption keys as part of the certificate authority function and public-key infrastructure support. Warwick Ford, "Entrust Technical Overview," White Paper, Nortel Secure Networks, Oct. 1994.
PC Security Stoplock KE. This is a commercial product that integrates private key recovery into the key management infrastructure. Stoplock Press, PC Security, Ltd., Marlow, Buckinghamshire, UK, Issue 3, Nov. 1995.
Royal Holloway Trusted Third Party Services. This proposed architecture for a public key infrastructure requires that the TTPs associated with pairs of communicating users share parameters and a secret key. Nigel Jefferies, Chris Mitchell, and Michael Walker, "A Proposed Architecture for Trusted Third Party Services," Royal Holloway, University of London, 1995.
RSA SecureTM. This file encryption product provides data recovery through an archived master public key, which can be split among up to 8 trustees using a threshold scheme. RSA SecureTM, product literature from RSA Data Security, Inc.
Shamir Partial Key Escrow. This is a proposal to escrow all but 48 bits of a long (256-bit) key. These 48 bits, which are generated randomly for each session or file, are determined by brute force during data recovery. 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.
TECSEC VEILTM. This commercial product provides file (and object) encryption. Key recovery is built into the key management infrastructure. Edward M. Scheidt and Jon L. Roberts, "Private Escrow Key Management," TECSEC Inc., Vienna, VA. See also TECSEC VEILTM, product literature.
TESS with Key Escrow. The Exponential Security System supports a general access structure for key recovery. The DRC obtains a particular session key by participating in the key establishment protocol and acquiring the sender's or receiver's private key. 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, 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.
Threshold Decryption. With threshold decryption, a secret key can be shared by a group of recovery agents in such a way that through collaboration of the agents, information can be decrypted without the agents releasing their individual key components. Yvo Desmedt, Yair Frankel, and Moti Yung, "A Scientific Statement on the Clipper Chip Technology and Alternatives," 1993.
TIS RecoverKey. This is a commercial key recovery system. Key recovery is enabled through master keys held by a Data Recovery Center. Stephen T. Walker, Stephen B. Lipner, Carl M. Ellison, and David M. Balenson, "Commercial Key Recovery," Communications of the ACM, Vol. 39, No. 3, Mar. 1996, pp. 41-47.
For more detailed descriptions of these systems, see also Dorothy E. Denning, "Descriptions of Key Escrow Systems," http://www.cs.georgetown.edu/~denning/crypto/Appendix.html.
|Key Recovery System or Approach (* is commercial product)||USC - User Security Component||
|AT&T Crypto Backup||f,c||Ur||pub||pub||S||-||C||master||1,k/n||dec K||S||K|
|Bankers SecureKEES*||c||U||priv||pub,k||H||-||C||user||k/n||rel KU||S/R||S/R|
|Bell Atlantic Yaksha||c,f||U||priv||na||-||KMI||C||session||1||rel K||-||K|
|Binding Crypto||f,c||U||pub||pub||S||-||-||master||k/n||dec K||S/R||K|
|Blaze File Crypto||f||U||none||na||H||-||C||dir||1||dec file||S||K|
|Clipper Chip (EES)*||c||C||priv||priv||H||-||G||prod||2/2||rel KU/exp||S||S|
|Cylink Key Recovery||c,f||U||priv||pub,k||-||PKI||C||user||1,k/n||rel KU||S/R||S/R|
|Fortezza Card*||c,f||C||priv||pub||H||PKI||C||user||1||rel KU||R||R|
|Fortress KISS||c||U||priv||pub,k||H||-||G||master||2/2||dec KU||S/R||S/R|
|IBM SecureWay.*||f,c||U||pub||pub||-||-||C||master||k/n||dec g/part K||S/R||K|
|Kilian/Leighton F-safe||c||U||priv||pub,k||-||-||-||user||k/n||rel KU||-||-|
|Leiberich TB-Clipper||c||C||priv||priv||H/c||-||G||prod||2/2||rel KU/tb||S||S|
|Lotus Notes Int'l*||c||U||pub||pub||S||-||G||master||-||dec part K||S||K|
|Micali Fair Crypto||c||U||priv||pub,k||-||PKI||-||user||k/n||rel KU/tb||R||R|
|Micali Partial Escrow||-||-||-||-||-||-||-||partial||-||-||-||-|
|Micali/Sidney Esc.||-||U||priv||priv||-||-||-||user||t/u/n||rel KU||-||-|
|National CAKE||f,c||U||pub||pub||H||-||C||master||1||dec K||S||S|
|Nechvatal Public-Key||c||-||pub||pub||-||-||-||prod||n/n||rel KU||S||S|
|Nortel Entrust*||c,f||Ur||priv||pub,k||H,S||PKI||C||user||1||rel KU||S/R||S/R|
|PC Sec. Stoplock KE*||c,f||Ur||priv||-||S||KMI||C||system||-||-||-||-|
|Royal Holloway TTPs||c||U||priv||priv,k||-||PKI||C||user||-||rel KU||S/R||S/R|
|RSA Secure*||f||Ur||pub||pub||S||-||C||master||k/n||dec K||S||K|
|Shamir Partial Escrow||-||-||priv||-||-||-||-||partial||-||rel||brute||-|
|TECSEC VEIL*||f||U||priv||priv,k||S||KMI||C||system||n/n||rel K||S/R||K|
|TESS w Key Escrow||c||U||priv||na||H||PKI||C||user||any||rel KU||S/R||S/R|
|TIS RecoverKey.*||f,c||U||pub||pub||-||-||C||master||1||dec K||S/R||K|
Key to Table 1.
User Security Component (USC)
Data Recovery Component (DRC)
A dash "-" in table denote an open or unspecified element.