Lein Harn*, Hung-Yu Lin** and Guang Gong***

*Department of Computer Networking

University of Missouri – Kansas City

Kansas City, MO 64110

USA

**Computer Science Department

California State University

San Marcos,CA 92096-0001

USA

*** Department of Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario N2L 3G1

CANADA

Cryptographic technologies used today are either symmetric key or public key. Cryptographic keys have become vital parts in modern communications. Key recovery is a technology that allows the owner of encrypted data or a trusted third party to recover a lost or otherwise unavailable session key. Key recovery has emerged as a safe, practical method for recovering encrypted data. In this paper, we propose a key recovery system that combines the functions of public-key certification and key recovery authorities. This key recovery system recovers a user’s private key that is used to generate digital signatures or to encrypt random session keys. This proposed system is easy to implement, scalable, has no single point of vulnerability, and is interoperable. It can be implemented in a large-scale global communication system.

In 1992 Silvio Micali proposed Fair Public Key Cryptosystems (FPKCs) [1], which provide secure escrowing of private keys without relying on special purpose hardware. In FPKCs, each user is allowed to select his/her private and public keys; but each user needs to reveal his/her private key to multiple trustees. In the event of a court order, the private key can be reconstructed by the trustees. In 1993, the United States Government published the Key Escrow System (KES) [2]. KES shares many similar concepts with Micali’s FPKCs. The goal of KES is to provide individual privacy but at the same time allow for court-authorized wiretapping. The Escrowed Encryption Standard (EES) announced by the United States Government in 1994 consists of a symmetric encryption algorithm, SKIPJACK, and a key escrow algorithm packed in a tamper-free chip, CLIPPER. Each encryption chip has a unique ID and a secret key. This secret key is split into two pieces and stored, along with its ID, by two different escrow agencies. Every time the chip encrypts a data file, it first encrypts the session key with this unique secret key. Then it transmits this encrypted session key and its ID over the communication channel. When a law enforcement agency wants to decrypt traffic encrypted with one of these chips, it can recover the session key through the help of the escrow.

Micali’s FPKCs are not perfect. A subliminal channel can be embedded in a FPKC such that criminals can use this subliminal channel to communicate without having to worry about court-authorized wiretapping. A secure Failsafe Key Escrow protocol (FKE) [3] was then proposed to eliminate this subliminal channel. Instead of letting each user select his/her own private and public keys, the fair-safe key escrowing protocol allows a user and the key escrow agency to determine the user’s private and public keys together. Here we would like to point out that FKE couldn’t prevent criminals from abusing the system either. One possible scenario is that two criminals can establish a common secret session key by exchanging Diffie-Hellman public keys [4] signed with private keys deposited at the key escrow agencies. This common secret key won’t be recovered by the key escrow agencies. In addition, due to the fact that there are many unsolved legal issues associated with the key escrow system, the concept of key escrow has been rejected by most civilian and federal agencies.

On October 1, 1996, the US government announced the relaxation of export restrictions on products that implement or use strong encryption (i.e. DES with 56-bit key). This liberalization was predicated upon the computer industry developing a key recovery technology that would balance the need for personal confidentiality with the legitimate security needs of the government. Key recovery is a technology that allows the owner of encrypted data or a trusted third party to recover a lost or otherwise unavailable session key. Key recovery shares most concepts with key escrow except that, instead of designating two government agencies as trusted key escrow agencies as in KES, any trusted third party (i.e. can be either software or hardware) can be used in key recovery.

Cryptographic technologies used today are either symmetric key or public key. Cryptographic keys have become vital parts in modern communications. Key recovery has emerged as a safe, practical method for recovering encrypted data for which a key is lost or unavailable. Various vendors, such as IBM [5] and Cylink [6], have developed commercial key recovery products and these products have been widely used. While designing a key recovery algorithm, we need to consider the following requirements:

• easy to implement
• applicable to all cryptographic algorithms
• scalable
• no single point of vulnerability
• interoperable
• integrity check

In this paper, we propose a global key recovery system (GKRS) that meets all of the above requirements. This key recovery system recovers a user’s private key of public-key technologies. This private key can be then used to produce digital signatures or to encrypt random session keys. We utilize an efficient multisignature algorithm [7] to combine the functions of the certification authority (CA) and the key recovery authority. GKRS can be constructed within the current CA architecture and can be implemented in a large-scale global communication system.

In 1976, Diffie and Hellman [4] proposed the new concept of the "public-key" cryptosystem to solve key distribution problems. In a public-key cryptosystem, the encryption key and decryption key are related in such a manner that an encryption key is separate and distinct from a decryption key. Thus, a "key pair" is formed such that for each encryption key there is a unique corresponding decryption key. Moreover, given the knowledge of one key, it is not computationally feasible to compute the other.

In this type of public-key system, the encryption keys are made public. Anyone desiring to communicate privately over an insecure communication channel simply encrypts a message using the recipient’s public key. Only the recipient knowing the corresponding decryption key is able to decipher the message.

The two most well-known public-key cryptosystems that provide both digital signature and encryption are: (a) the RSA scheme [8], in which the difficulty of breaking the system is based on the difficulty of factoring a large integer into two large prime factors, and (b) the ElGamal scheme [9], in which the difficulty of breaking the system is based on the difficulty of computing a discrete logarithm in a finite field. More recently, the Elliptic Curve Cryptosystem (ECC), in which the difficulty of breaking the system is based on the difficulty of computing a discrete logarithm over an elliptic curve, has also been considered for a standard by the IEEE P1363 project [10]. The ECC shares many similar features with the ElGamal cryptographic system.

To prove the authenticity of a public key, one needs to obtain a public key certificate from a trusted certification authority (CA). Each public-key certificate contains the public-key information of a user and the signature of this information signed with the private key of CA. This public-key certificate is used by all other users to authenticate a user’s public key. X.509 defines a framework for the provision of authentication services by the X.500 directory to its users and the standard does not dictate the use of a specific algorithm. X.509 is used in a variety of contexts. For example, the X.509 certificate format is used in S/MIME [12], IP Security [13], and SSL/TLS [14] and SET^TM [15].

In our proposed algorithm, we suggest combining the CA and key recovery authority into one unit. In other words, users need to deposit their private keys for key recovery purposes while registering their public keys with the CA for obtaining corresponding public-key certificates. Instead of using just one CA, we propose to use multiple CAs to avoid the single point of vulnerability problem. For example, assume that a user has selected two CAs as his/her key recovery authorities. The user needs to split his/her private key into two pieces and then reveal one to each CA to obtain a partial public-key certificate. After obtaining both partial certificates, the user combines them into a public-key certificate. Our GKRS is developed based on the following motivations:

1. Since both the CA and the key recovery authority need to be mutually trusted by all users, combining the functions of these two authorities into one can simplify implementation.
2. Using multiple CAs prevents a single point of vulnerability.
3. Since X.509 has become an important standard in the current Public Key Infrastructure (PKI) for public-key certificates, our GKRS can utilize this existing structure to achieve scalability and interoperability.
4. In order to obtain a valid public-key certificate to be used in global communication, each user needs to properly deposit his private key in CAs. This arrangement provides a positive motivation to encourage all users to implement key recovery.

3. Review of multisignature scheme

In our proposed GKRS, we utilize an efficient multisignature scheme developed in Ref. [4] to combine the functions of the CA and the key recovery authority. Here, we briefly review the multisignature scheme.

Determining the public keys:

A large prime, p, and a primitive element, a, of GF(p) need to be made public. Each signer randomly selects an integer xi from [1, p-1] and computes a corresponding public key as

y_i= a ^xi mod p.

The public key of the signers is equivalent to the product of all individual public keys. We start with the multisignature generating phase.

Generating the multisignature:

Phase 1: Determining the commitment value of r

Without loss of generality, we assume that the message m needs to be signed by two signers, U₁ and U₂. Signer Ui randomly selects a number k_i from [1, p-1] and computes

r_i= a ^ki mod p.

r_i is broadcast to the other signer. Once r₁ and r₂ are available through the broadcast channel, every signer computes the commitment value r as r = r₁r₂ mod p.

Phase 2: Determining the multisignature value of s

Instead of signing the message m directly, all signers should sign the one-way hash result m'=h(m), where h is the one-way hash function. To sign the message m', U_i computes

s_i = x_i m’- k_ir mod p-1,

and transmits (r_i, s_i) to the clerk.

Once the clerk receives the individual signature (r_i, s_i) from U_i, he needs to verify the validity of this individual signature by checking the following equation:

y_i^m’=r_i ^r a ^si mod p.

If both individual signatures are valid, the multisignature of message m is generated as (r, s), where s = s₁ + s₂ mod p-1.

Verifying the multisignature:

Since individual signatures, (r₁, s₁) and (r₂, s₂), satisfy

y₁^m’=r₁ ^r a ^s1 mod p, and

y₂^m’=r₂ ^r a ^s2 mod p.

By multiplying these two equations, we obtain the multisignature verification equation as

y^m’=r ^r a ^s mod p, where y=y₁y₂ mod p.

4. GKRS

In the following discussion, we assume that a user has decided to select two CAs, CA₁ and CA₂, as his/her public-key certification and key recovery authorities.

2. Discrete-logarithm based scheme

2. Discrete-logarithm based scheme

Each CA_i randomly selects an integer x_i from [1, p-1] and computes a the corresponding public key y_i as

y_i= a ^xi mod p.

Following the same steps as described in the previous section, each CAi randomly selects a number ki from [1, p-1] and computes a corresponding integer r_i,

r_i= a ^ki mod p.

ri is broadcast to the other CA. Once r₁ and r₂ are available, each CA_i computes the commitment value r as r = r₁r₂ mod p. Since these values do not depend on the message to be signed, they can be pre-computed off-line.

Once CAi has successfully performed the integrity check of a user’s public key m=( e, n, (pubkey₁, CA₁), (pubkey₂, CA₂)), he uses his secret keys, x_i and k_i, to sign the message m', where m’=h(m) and h is a one-way hash function. CA_i solves the equation

s_i = x_i m’- k_ir mod p-1,

and returns (ri, si) to the user.

Once the user receives the partial signature (ri, si) from CAi, he verifies the validity of this partial signature by checking

If both partial signatures are valid, the final public-key certificate can be generated as (r, s), where s = s₁+ s₂ mod p-1. Each user can use this public-key certificate to achieve global communications.

We would like to point out here that whenever the user improperly splits the private key into two pieces (i.e. may be caused on purpose by a dishonest user), this error will either be detected by the CAs or result in an invalid public-key certificate.

Any verifier can identify the names of authorities who have generated the public-key certificate from users’ public keys, (e, n (pubkey₁, CA₁), (pubkey₂, CA₂)). The validity of the public-key certificate can be verified by checking

y^m’=r ^r a ^s mod p, where y=y₁y₂ mod p.

3. Discussion

1. GKRS can be implemented in the X.509 public key infrastructure and it is scalable and interoperable.
2. GKRS does not depend on any tamper-free device. It can be implemented by either software or hardware.
3. Since GKRS allows users to select multiple authorities for their key recovery and public-key certification, there is no single point of vulnerability. In other words, only when all authorities have been compromised, can an attacker successfully break the system.
4. There is no overhead in verifying public-key certificates signed by multiple authorities. No matter how many authorities a user has selected, the verification time of a public-key certificate is equivalent to the verification time of public-key certificate signed by a single authority.
5. GKRS allows each user to select his own public and private key pair. In addition, each user can decide its own CAs and determine the number of authorities used for key recovery and public-key certification. This user-dominant feature is extremely important when looking for a widely supported GKRS.
6. In GKRS, we have integrated the functions of key recovery into public-key certification authorities. A user needs to properly deposit his/her private key in authorities in order to receive a valid public key. This arrangement will produce a positive motivation for users to participate in GKRS.
7. By examining a user’s public key, anyone can perform the integrity check to see whether the user’s private key has been properly split. In addition, anyone can identify the key recovery authorities that can be used to decrypt the encrypted data.
8. We cannot prevent criminals from abusing the GKRS by establishing subliminal channels. Based on what we have stated in the first section, it seems that this goal can not be achieved in the near future unless laws are changed to restrict the "content" of all communications.

3. Conclusion

In this paper, we have proposed a GKRS that combines the functions of public-key certification and key recovery authorities. Each user can select multiple authorities for depositing his/her private key. The GKRS allows the owner of encrypted data or a trusted third party to recover a lost or otherwise unavailable session key. GKRS can be implemented in the X.509 public key infrastructure.

1. S. Micali, "Fair Public-Key Cryptosystems", Advances in Cryptology – CRYPTO ’92 Proceedings, Springer-Verlag, 1993, pp. 113-138.
2. D. E. Denning, "The US Key Escrow Encryption Technology", Computer Communications, Vol. 17, No. 7, 1994, pp. 453-457.
3. W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, V.IT-22, No. 6, Nov. 1976, pp. 644-654.
4. J. Kilian and T. Leighton, "Fairsafe Key Escrow", MIT/LCS/TR-636, MIT Laboratory for Computer Science, Aug. 1994.
5. IBM Key Recovery Server, http://www.ibm.com/security/html/prod_key.html.
6. P. Bolton, "CyKey: A Key Recovery System for Commercial Environments", http://www.cylink.com/.
7. L. Harn, "Group-Oriented (t, n) Threshold Signature and Multisignature", IEE Proceedings-E, Vol. 141, No. 5, pp. 307-313, Sep. 1994.

9. T. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme based on Discrete Logarithms’, IEEE Trans. Inform. Theory, Vol. IT-31, July, 1985, pp. 469-472.
10. IEEE P1363: Standard Specifications For Public Key Cryptography, http://grouper.ieee.org/groups/1363/index.html.
11. Public-Key Infrastructure (X.509) (pkix), http://www.larc.usp.br/~cmmatayo/ComissaoBrisa/IETF/pkix-charter.html.
12. Enhanced Security Services for S/MIME, http://www.imc.org/draft-ietf-smime-ess.
13. Security Architecture for the Internet Protocol, http://info.internet.isi.edu:80/in-notes/rfc/files/rfc2401.txt.
14. The TLS Protocol Version 1.0, http://www.consensus.com/ietf-tls/tls-protocol-03.txt.
15. SET Secure Electronic Transaction, http://www.setco.org/.